博客

一、什么是散列表 ？

散列表用的是数组支持下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

举个例子，我们将参赛选手设置一个编号，比如051167，表示 5 年级 11 班 67 号选手，然后在数组索引下标对应 67 的位置存储该选手，这就是典型的散列思想，我们将参赛选手的编号叫

做键（key）或者关键字

，用它来标识一个选手，把参赛编号转化为数组下标的映射方法就叫作

散列函数（或哈希函数）

，而散列函数计算得倒的值就叫作

散列值

。

总之，散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是O（1）的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化为数组下标，从对应的数组下标的位置取数据。

二、散列函数

我们可以把它定义成hash（key），key 表示元素的键值，hash（key）的值表示经过散列函数计算得到的散列值。

想要构造一个散列函数，需要满足以下三种基本要求：

• 散列函数计算得倒的散列值是一个非负整数
• 如果key1 = key2，那hash（key1）= hash（key2）
• 如果key1≠ key2，那hash（key1）≠ hash（key2）

第一个，数组下标时从0开始的，所以散列值也是非负整数的；第二个，相同的key经过散列函数得倒的散列值页应该是相同的；

第三个就有点复杂了，要想找到一个不同key对应的散列值不同的散列函数，基本上是不可能的，就像业界的MD5、SHA等哈希算法，页无法完全避免散列冲突，而且因为数组的存储空间有限，也会加大散列冲突的概率。

如何设计散列函数 ？


散列函数的好坏，决定了散列表冲突的概率大小，也直接决定了散列表的性能。首先散列函数的设计不能太复杂，过于复杂的散列函数，势必会消耗很多计算时间，也就间接的影响到散列表的性能。其次散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突。而且即便出现冲突，每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况。

三、散列冲突

处理散列冲突经常用的两种方法：开放寻址法和链表法。

开放寻址法

，核心思想是：如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。

那么具体是如何进行探测的呢？

第 1 种、线性探测：

• 插入：假设散列表大小为 10，当插入 x 元素，已经有 6 个元素插入到散列表，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以产生了冲突，然后我们就按照顺序往后一个一个找，如果到尾部都没有空闲位置，就从表头开始找，知道找到空闲位置，将x插入到这个位置。
• 查找：首先通过散列函数求出要查找的 x 元素的键值对应的散列值，然后比较数组下标为散列值的元素和 x 是否相同，如果相同就是我们要找的，如果不同，就继续按顺序往后依次查找，如果遍历到空闲位置（注意此处不是遍历整个散列表，并且遍历到被标记为 deleted 时，不是停止，而是继续遍历），还没有找到，就说明元素 x 不在散列表中。
• 删除：将删除的元素特殊标记为 deleted，而不是设置为空。
  
  线性探测分析：其实存在很大问题，当散列表中数据越来越多时，散列冲突的可能性就会越来越大，空闲位置也会越来越少，线性探测的时间就会越来越久，极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度是O（n），同理在删除和查找的时候，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。

第 2 种、二次探测：

二次探测和线性探测很像，线性探测每次探测的步长时1，那它探测的下标序列就是hash（key）+0，hash（key）+1，hash（key）+2。。。而二次探测的步长就变成了原来的二次方，它探测的下标序列是hash(key)+0，hash(key)+1的平方，hash(key)+2的平方。

第 3 种、双重散列：

意思是不仅仅是用一个散列函数，而是使用一组散列函数，如果用第一个散列函数得倒存储位置已经被占用，那么再使用第二个散列函数，依次类推，直到找到空闲的存储空间。

不管使用哪种探测方法，当散列表中空闲位置不多时，散列冲突的概率就会大大提高。为了尽可能的保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位，我们用装载因子来表示空位的多少：散列表的装载因子 = 填入表中的元素个数 / 散列表的长度。装载因子越大，填入表中的元素个数作为分子，一定是相对越多的，于是空闲位置就越少，冲突也就越多，散列表的性能会下降。

链表法

，是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多，在散列表中，每个桶（bucket）或者槽（slot）会对应一条链表所有散列值相同的元素都会放到相同槽位对应的链表中。

当插入元素时，通过散列函数计算出对应的散列草味，将其插入到对应链表中即可，时间复杂度时O（1），当查找或删除一个元素时，同样通过散列函数计算出对应的槽，然后便利链表查找或删除，实际上时间复杂度和链表的长度成正比。另外如果有n个数据，占用了m个槽位，那么k = n / m。

如何选择冲突解决办法？


1、开放寻址法的优缺点：数据都存储在数组中，可以有效的利用CPU缓存加快查询速度，而且，序列化起来比较简单；缺点是删除数据的时候比较麻烦，需要特殊标记已删除数据为deleted，另外，冲突代价也更高，所以使用开放寻址法解决冲突的散列表，装载因子的上限不能太大，这也导致比链表法更浪费内存空间。

总结：当数据量较小，装载因子小的时候，适合用开放寻址法。比如Java中的ThreadLocalMap使用开发寻址法解决散列冲突。

2、链表法的优缺点：对内存的利用率比开放寻址法更高，散列函数只要随机均匀，即便装载因子达到10，也就是链表的长度变长了而已，不像开放寻址法，会导致过多冲突以及大量的探测、再散列等性能会下降很多。缺点是链表要存指针，对于比较小对象，还是比较消耗内存的，很有可能让内存翻倍，而且链表中节点零散分布在内存中，不是连续的，对CPU缓存也不太友好。

总结：基于链表的散列冲突处理方法适合存储大对象（在大对象面前指针内存很小，可以忽略）、大数据量的散列表，而且，比起开放寻址法，它更灵活，支持更多的优化策略，比如用红黑树替换链表。Java中的LinkedHashMap就是采用了链表法解决冲突。

四、Word文档中单词拼写检查功能如何实现 ？

常用的英文档次有20万左右，假设单词的平均长度时10个字母，平均一个单词占用10个字节的内存空间，20万给我单词占用大约2MB的存储空间，就算放大10倍，也就是20MB，对于现在的计算机来说，完全可以放在内存里，用散列表来存储整个英文单词词典。

当输入某个英文单词的时候，就拿用户输入的单词去散列表中查找，如果找到，则拼写正确，没有查到，则拼写错误。

五、装载因子过大怎么办 ？

之前提到过，

装载因子越大，说明散列表中元素越多，空闲位置越少，散列冲突的概率越大

，不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会变得很慢。

针对散列表，当装载因子过大时，我们可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到这个新的散列表中。假设每次扩容我们都申请一个原来两倍的空间。如果原来的散列表的装载因子时0.8，那么扩容之后，新散列表的装载因子就下降为原来的一半，就变成了0.4。扩容时，因为散列表的大小变了，数据的存储位置也变了，所以我们需要通过散列函数重新计算每个数据的存储位置。

对于支持动态扩容的散列表，插入一个数据，最好情况下，不需要扩容，

最好时间复杂度是O（1）

，最坏情况下，散列表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以最坏时间复杂度是O（n）

加粗样式

，用均摊分析法，均摊情况下，时间复杂度接近最好情况，

均摊时间复杂度就是O（1）

。

删除操作时，如果对空间比较敏感，当装载因子小于某个值时，可以进行动态所容，当然，如果更在意执行效率，能够容忍一点内存空间，也就不用费劲来缩容了。

装载因子的设置要权衡

时间，空间复杂度

。如果空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值。

总之一定要相对合适，如果太大，导致冲突过多，如果太小，导致内存浪费严重。

六、如何避免低效的扩容 ？

为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表里，当有新数据插入时，我们将新数据插入到散列表中，并且从老的散列表中拿出一个数据放入到新散列表中，经过多次操作，数据就一点一点的全部搬移到新的散列表中了。这期间的查询操作，为了兼容新老散列表，先从新的查找，如果没找到，再去老的查找。通过均摊的方法，将一次扩容的代价，均摊到多次插入操作，就避免了一次性扩容耗时过多的情况，这种实现方式，在任何情况下，插入一个数据的时间复杂度都是O（1）。

七、工业级散列表举例分析 – HashMap

• 初始大小是16（capacity），默认值可以设置的，如果实现知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，大大提高HashMap的性能
• 最大装载因子是0.75，当HashMap的元素个数超过0.75*capacity的时候就会启动动态扩容，每次扩容为原来两倍。
• HashMap底层使用链表法来解决冲突，即使负载因子和散列函数设计的再合理，页免不了出现拉链过长的情况，一旦出现拉链过长，就会严重影响HashMap的性能。于是在JDK1.8版本中，对HashMap做进一步优化，引入了红黑树，当链表长度（默认是8）过长时，链表就会转换成红黑树，我么就可以利用红黑树快速增删改查的特点。当红黑树节电少于8时，又会将红黑树转化为链表，因为红黑树需要维护平衡，比起链表来，性能上的优势并不明显。
• 散列函数设计的并不复杂，追求的是简单高效，均匀分布
  
  如何设计一个工业级别的散列表？
• 支持快速的查询、删除、插入操作
• 内存占用合理，不能浪费过多的内存空间
• 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。

八、工业级散列表举例分析 – LinkedHashMap

LinkedHashMap也是通过散列表+双向链表组合在一起实现的，它不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据。每次调用put函数时，都会将数据添加到链表的尾部。如果插入元素的key在原来的链表中已存在，会将原来的删除，将新的元素插入到链表尾部，除此之外，当数据被访问时，会将数据移动到链表尾部。由此可以看出，按照访问时间排序的LinkedHashMap本身就是一个支持LRU缓存淘汰策略的缓存系统，实现原理也是一摸一样。