如何设计散列函数
散列函数的设计的好坏，决定了散列冲突的概率大小，也直接决定了散列表的性能。
好的散列函数，应该有以下特点
- 散列函数的设计不能太过复杂。
过于复杂的散列函数，会消耗过多的计算时间，也就间接影响到散列表的性能。
- 散列函数生成的值应该尽可能随机且均匀分布
这样才能避免或者最小化散列冲突。即便是出现冲突，散列到每个槽的数据也会分布得比较均匀，不会出现某个槽内的数据特别多的情况。
- 实际工作中还需要综合考虑各种因素。
这些因素有关键字的长度、特点、分布、还有散列表的大小等。
常用、简单的散列函数设计方法
- 数据分析法
通过分析传入散列函数的 key 的特征规律，设计相应的专用散列函数。比如处理使用散列函数处理手机号码，考虑到手机号码前几位重复性很大，后几位比较随机，我们就可以取手机号码后几位作为散列值。
- 进位相加
比如对字符串进行散列，可以将字符串中每个字母的 ASCII 值进行“进位”相加，然后再跟散列表的大小求余、取模，作为散列值。比如，对因为单词 nice 进行散列：
hash("nice")=(("n" - "a") * 26*26*26 + ("i" - "a")*26*26 + ("c" - "a")*26+ ("e"-"a")) / 78978
- 直接寻址法、平方取中法、折叠法、随机数法等
装载因子过大了怎么办
装载因子的定义为 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度，根据这个公式，可以推出，装载因子越大且散列表的长度不变，则散列表中的元素越多，空闲位置越少，散列冲突的概率会变大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。
对没有频繁插入和删除的静态数据集合来说，我们很容易根据数据的特点、分布等，设计出完美的、极少冲突的散列函数。
对于动态散列表来说，数据集合频繁变动，负载因子可能随着时间不断变大。这时就要动态扩容。
动态扩容的过程，简单来说，就是申请一个新的散列表，然后把原来的数据搬运到新的散列表中，但是不是简单的搬运，而是每个元素都要根据新的散列表重新存储位置。
这个过程，运用平摊分析法，每个插入操作的时间复杂度仍是 O(1)。
扩展一下，当散列表的装载因子小于某个阈值时，我们也可以依样画葫芦，进行动态缩容。
如何避免低效扩容
大部分情况下，动态扩容的散列表插入一个数据都很快，但在特殊情况下，装载因子达到扩容的阈值，此时，再插入数据，就会触发漫长的扩容过程，在特定的场合，这样漫长的等待过程是不可接受的。
举个直观的例子，假设原来散列表有 1GB 的数据，现在进行扩容，就需要对这 1GB 的数据进行再散列，这个扩容的时间，看起来就很耗时。
在这种情况下，“一次性”扩容的机制就不适合了。此时，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子达到扩容的阈值后，我们只申请新空间，但不立即将老的数据全部搬移到新的散列表中。
当有新的数据插入时，我们就将新数据插入新散列表中，同时从旧散列表中拿出一个数据放入到新的散列表。每次插入一个数据到散列表，我们都重复以上的过程。经过多次操作后，老的散列表中的数据就一点一点全部搬移到新的散列表中了。没有了一次性全部搬移，插入操作就不会出现一次很慢的情况了。
这期间的插入操作，可以先从新的散列表中查，查不到再去旧的散列表中查。甚至，可以在每次查询操作中也穿插一条数据搬移。
如何选择散列冲突的解决方法
上节讲了两种主要的散列冲突的解决办法，开放寻址法和链表法。这两种冲突的解决办法在实际的软件开发中很常用。比如， Java 中的 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。
- 开放寻址法
这种实现方式，散列表中的数据都存放在数组中，可以有效利用 CPU 的缓存加快查询速度。序列化过程比较简单。链表法包含指针，序列化就比较麻烦。
缺点是，删除数据比较麻烦，需要使用特殊标记。所有数据都存在一个数组中，冲突的代价很大。
总结，数据量小、装载因子小，适合开放寻址法。这也是 ThreadLocalMap 采用开放寻址法解决散列冲突的原因。
- 链表法
链表法的优点是内存利用率高。链表节点可以在需要的时候再创建，并不需要想开放寻址法那样实现申请好。
链表法对冲突的容忍性更高，装在因子可以大于 1，甚至再散列冲突很平均的情况下，即使装载因子达到 10，查找效率也不会大幅度衰退。更进一步，对链表法进行改造，使用红黑树或者跳表解决散列冲突，那即使是极端情况下，所有数据都存放在一个槽内，查询时间也是衰退到 O(logn) 的数量级。
缺点是，需要维持链表的指针引用，若是存放小对象，那么指针占用的内存就会对比起来挺多，而且链表法也容易造成内存碎片。
总结起来就是，基于链表法的散列冲突方法适合存储大对象、大数据量的散列表，而且比起开放寻址法，它更加灵活，支持更多的优化策略。
工业级散列表举例分析
分析 HashMap
- 初始大小
HashMap 的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量多少，就可以依此设置合适的初始容量。
- 装载因子和动态扩容
最大装载因子默认是 0.75。当 HashMap 中元素个数超过 0.75 * capacity 时，就会启动扩容，每次扩容后的容量是原来的两倍。
关于 0.75 这个数字的由来，可以查看这篇文章 https://blog.csdn.net/reliveIT/article/details/82960063。
- 散列冲突解决办法
HashMap 底层采用链表法解决冲突。在 JDK 1.8 之前，冲突的元素插入链表首端，在 JDK 1.8 之后，插入尾端。
另外，在 JDK 1.8 之后，当链表长度超过 8 时，会启动树化，当树中元素少于 6 个时，会退化回链表。
- 散列函数
HashMap 的二次哈希，使用的是除留余数法。
因为 A % B = A & (B - 1)，所以，(h ^ (h >>> 16)) & (capitity -1) = (h ^ (h >>> 16)) % capitity。
工业级散列表应该具有的特征
- 支持快速的查询、插入、删除操作
- 内存占用合理，不能浪费过多内存
- 性能稳定，极端情况下也不会性能退化到无法接受
设计这样的散列表应该从三个方面考虑
- 设计合适的散列函数
- 定义合适的装载因子
- 合适的动态扩容策略
- 合适的散列冲突解决办法
网友评论