数据结构与算法之美-散列表(上)

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

1. 什么是散列表？

散列技术：
散列技术是在记录的存储位置和它对应的关键字之间建立一个确定的对应关系，比如f，使得每个关键字 key对应一个存储位置 f(key)。
在查找时可以通过给定的关键值key找到对应的映射f(key)，如果集合中存在这个记录，那么这个记录就在f(key)的位置上。

散列函数：
上面提到的关键值key 和存储位置f(key)的对应关系f 称为散列函数（哈希 Hash 函数）。

散列表：
采用散列技术将记录存储在一块连续的存储空间中，这一块连续的存储空间称为散列表。

散列表用的是数组支持通过下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。简单来说，散列表就是把 key 通过 hash 函数求得 hash 值之后，对数组容量求余，得到存放在数组的位置下标值。

2. 散列函数的构造方法

一个好的散列函数有两个标准：

• 计算简单
  对于频繁的查找来说，复杂的计算会耗费很多的时间

• 散列地址分布均匀
  让散列地址均匀的分布在存储空间中，这样可以对存储空间有效利用，减少散列冲突

2.1 直接定址法

取关键字的某个线性函数值为散列地址，比如：

f(key) = a * key + b

• 优点：
  简单、均匀，不会产生冲突，适合查找表较小且连续

• 缺点：
  过于简单，对于较大表来说并不常用

2.2 数字分析法

比如将手机号作为关键字，抽取手机号关键字的一部分来计算散列存储位置。

• 优点：
  适合处理关键字位数比较大的情况

• 缺点：
  需要事先知道关键字的分布，并且分布较均匀

2.3 折叠法

将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，然后按照散列表表长，取后几位作为散列地址。

比如关键字为 9876543210，散列表表长 3 位，将它分为 4 组：987|654|321|0，叠加求和为 1962，再取后 3 位得到散列地址为 962。

• 优点：
  适合关键字位数较多，不需要事先知道关键字的分布

2.4 除留余数法（最为常用）

就是对关键字 key，求余数

f(key) = key mod p (p <= m)

注意：如果散列表表长为m，通常p为小于或等于表长（最好接近 m）的最小质数或不包含小于 20 质因子的合数。

2.5 随机数

取关键字的随机函数值为它的散列地址，即：

f(key) = random(key)

• 优点：
  适用于关键字的长度不等时

在选用合适的散列函数时，需要考虑一些因素，比如：计算散列地址的时间、关键字的长度、散列表的大小、关键字的分布情况、查找的频率等。

3. 散列冲突

散列表的查找很简单，就是通过散列函数通过给定的 key 值去找对应的存储位置，所以散列技术最适合求解的问题是查找与给定值相等的记录。

理想情况下，每一个 key 值，通过散列函数计算出来的地址都是不一样的，实际上，我们会经常碰到两个关键字不同，但是通过散列函数计算出来的值是一样的，即 f(key1) = f(key2)，这种现象就是散列冲突。

下面列举了几种方法来处理散列冲突。

3.1 开放定址法

一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址就一定能找到。

比如散列函数为 : f(key) = key % m ，也就是上面提到的除留余数法。
当有冲突时，就将 f(key) + 1 再对 m 取余数，如果还不行，f(key) + 2 ，一直到 f(key) + n (n < 表长)。

这种解决冲突的开放定址法称为线性探测法。

但是这种方法在解决冲突的时候，也会碰到本来不是同义词，却要争夺一个地址的情况，这种情况就是堆积。这使得我们需要不断处理冲突，无论是存入还是查找效率都会大大降低。

比如后面没有位置，前面有位置的情况，我们可以将 n 改为，1 的平方，-1 的平方，2 的平方，-2 的平方等等，这样就等于是可以双向寻找到可能的空位置。这种增加平方运算的目的是为了不让关键字都集中在某一块区域，称为二次探测法。

3.2 再散列函数法

就是准备多个散列函数，然后每当发生散列冲突时，就换另一个散列函数计算。

比如想要买房时钱不够，买不了市中心，可以买郊区的啊。

3.3 链地址法

就是将所有关键字为同义词（key 值不等，但散列函数计算后的值相等）的记录存储在一个单链表中（同义词子表），在散列表中只存储同义词子表的头指针。

如下图所示：

截屏2021-04-06 下午9.03.47.png

3.4 公共溢出区法

对于有冲突的关键字建立一个公共的溢出区来存放。在查找时对给定值通过散列函数计算出散列地址后，先和基本表的相应位置进行比对，如果相等则查找成功，如果不相等，则到溢出表去进行顺序查找。
对于基本表而言，有冲突的数据很少的情况下，这种方法的查找性能还是比较高的。

如下图所示，37 和 48 与之前的关键字有冲突，那么就把它们存储到溢出表中：

截屏2021-04-06 下午9.07.11.png

4. 相关问题

4.1 word 文档中单词拼写检查功能

我们在 Word 里输入一个错误的英文单词，它就会用标红的方式提示“拼写错误”。Word 的这个单词拼写检查功能是如何实现的呢？

就是构建了一个散列表存储整个英文单词词典，当用户输入某个英文单词时，就去散列表中查找，如果找到，说明正确，否则拼写可能有误。

4.2 假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？

• 遍历 10 万条数据，以 URL 为 key，访问次数为 value（初始值为 0），存入散列表
• 如果产生散列冲突，同时 key 相同，标明是同一个 URL，那么将对应的 value++，如果不同，则存入下一个位置
• 获取到相同 URL 出现次数的范围 0 - K，根据 K 的大小选取相应的算法，如果 K 不是很大，使用桶排序，时间复杂度为 O(n)，如果 K 很大，使用快排，时间复杂度为 O(nlogn)

4.3 有两个字符串数组，每个数组大约有10万条字符串，如何快速找出两个数组中相同的字符串？

以第一个字符串数组构建散列表，key为字符串，value为出现的次数。再遍历第二个字符串数组，以字符串为key在散列表中查找，如果value大于零，说明存在相同字符串，时间复杂度为O(n)。