什么是散列表
散列表的本质是数组，利用了数组随机存取的特点，在存储位置的选择上用了哈希函数来寻找元素对应位置。
哈希的核心思想就是映射，将元素唯一标识映射为数组下标，实现这一功能的函数叫做哈希函数。唯一标识就是元素的key，通过哈希函数求解出来的值为哈希值，可以对数组容量取模后当作数组下标。hash(key)
如何构造哈希函数
- 哈希函数的值应该是个非负整数（数组下标索引）
- 相同的key计算得到的值是相同的
- 不同的key计算得到的值是不同的（避免哈希冲突）
第3点要求哈希函数在作用域绝对单调，这一要求通常过于严格。因此找到一个没有哈希冲突的函数往往比较困难，所以需要借助其他方式来解决哈希冲突。
如何解决哈希冲突
哈希冲突就是不同的key计算出的哈希值相同，导致原本应该存在不同位置的两个元素需要存在相同的地方。
解决思路可以有两个方向：
- 第一、将存储位置扩充起来。哈希值相同的元素以链表的形式存在相同位置，这种方式结合了数组和链表的特点，先按照key计算得到哈希值，再从对应位置的链表中遍历得到需要的值。
- 第二、将有哈希冲突时后加入的元素存入其他位置。开放寻址寻找下一个空闲的内存地址，或者二次哈希寻找新的位置。
开放寻址法当哈希表接近满时寻找空闲内存空间的操作会非常耗时，可能达到O(n)，所以这种方式对哈希表的装载因子有一定要求，哈希表的装载因子表示已经存放元素的位置站总可用位置的比例。
工业级哈希表的基本要求
1.哈希函数的要求
- 哈希函数要求计算时间不能过长，这直接决定了哈希表的性能。
- 哈希函数的值要尽量随机且分布均匀，尽量减少哈希冲突发生。
2. 装载因子的要求
装载因子不能太大也不能太小。
- 装载因子太大哈希冲突发生的概率就大，查找操作耗时增加，性能恶化。
- 装载因子太小存在内存空间浪费。
- 装载因子阈值的设置需要综合考虑时间和空间复杂度决定，如果空间不紧张，对时间要求高，装载因子阈值可以选的小一些。如果对空间要求高，时间操作要求宽松，装载因子阈值可以选的大一些，甚至大于1。
- 装载因子超过最大阈值需要进行扩容，低于最小阈值需要缩容，扩容和缩容操作都要对现有所有元素重新哈希。
- 避免扩容操作重哈希带来的巨大时间开销--渐进式重哈希
- 每次插入到新表，并将旧表中一个元素插入到新表
- 查询时先从旧表查，查不到再到新表查
3. 哈希冲突解决方式的选择
-
开放寻址法
优点：所有数据都存放在数组中，可以利用CPU缓存加速。便于序列化。
缺点：处理冲突的代价更高，装载因子不能过高。
适用场景：数据量小，装载因子小的情况下。 -
链表法
优点：内存利用率高，装载因子容忍度高。
缺点：无法利用CPU缓存加速，链表查找操作耗时。（可通过链表改为红黑树或跳表等结构改进）
适用场景：数据量大、存储对象大。
哈希表和链表的结合
LRU缓存淘汰队列、redis有序集合、Java LinkedHashMap等都适用了哈希表和链表结合的方式。
哈希表用来实现快速的查找，但是由于哈希表的存储是离散的，需要支持按顺序输出的操作时需要先进行排序，所以将它与链表进行结合，通过链表可以方便实现按顺序输出。
网友评论