散列表

布满荆棘的人生 2023-06-25 06:28 20阅读 0赞

## 散列表 ##

散列表又称为哈希表，英文“Hash Table”。  
散列表思想利用的是数组支持按照下标随机访问数据的特性。  
**散列函数**：  
通过key，计算出value，value就是表示将数据放入数组的那个位置。  
**哈希冲突**：  
不同的key，可能会得到相同的value，这是就产生了哈希冲突。  
解决哈希冲突可以使用开放寻址法（线性探测、二次探测、双散列等）或者链地址法来解决。  
**装载因子**：  
装载因子 = 散列表中存储的数据个数/散列表的大小

装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。

## 散列表的设计 ##

#### 散列函数 ####

*  散列函数不能太复杂，否则计算哈希值的消耗太大
 *  散列函数生成的值要尽可能随机且均匀分布，这样才能避免或者减小散列冲突
 *  散列函数的设计还要考虑key的特性（长度、分布等），比如手机号，前几位重复率很高，后几位重复率较低，那么就可以取后几位作为value

Redis中采用的散列函数有：times33和siphash算法，PHP中也采用了times33作为散列函数，还使用了或运算。

#### 装载因子和动态扩容 ####

当装载因子超过设置的阈值（一般是0.75）的时候，就需要对散列表重新扩容，这样就会导致所有数据的重新散列。如果当前散列表中的数据很大，需要把散列表扩容为原大小的2倍，则之前的数据都需要重新扩容，这个过程很消耗时间，因此扩容操作不能一次性完成。  
Redis中的底层数据结构字典就使用了散列表结构，它的扩容方式是：

1.  redis维护了两个哈希表ht\[0\]和ht\[1\]和一个rehashidx变量，初始值为-1
2.  当ht\[0\]中的数据超过阈值，则为ht\[1\]分配扩容后的空间大小，并将rehashidx值设置为0表示开始重新计算哈希值（称为rehash）
3.  在rehash期间，对字典执行添加、删除、查找或者操作时，程序除了执行这些操作外，还会顺带将ht\[0\]哈希表在rehashidx索引上的所有键值对rehash到ht\[1\]上，然后rehashidx加1
4.  随着字典执行增删改查操作，ht\[0\]中的所有键值对最终会被rehash到ht\[1\]上，这时将rehashidx设置为-1，表示rehash完成

#### 解决哈希冲突 ####

**开放寻址法**

优点：

*  采用开放寻址法，数据最终还是存储在散列表数组中的，可以有效利用CPU缓存加速查询
 *  对数据进行序列化时简单

缺点：

*  删除数据很麻烦，因为不能直接删除，而是对需要删除的元素做删除标记，这也会导致冲突的概率更大，也会浪费空间
 *  装载因子过大，导致查询效率低

适用性：

*  适用于数据量小，装载因子小的情况下

**链表法**

优点：

*  需要内存的时候再去开辟，而不是预先定义好一个能存放所有数据的数组，节约了空间
 *  对哈希冲突的容忍度更高，因为链表法解决哈希冲突采用的是链表，哈希冲突只是导致链表的长度增加

缺点：

*  由于数据是零散分布在内存中的，因此对CPU缓存利用率不好
 *  需要额外的内存来存储指针，如果要存储的数据很小，那4字节的指针就会显得很浪费空间
 *  对数据序列化比较麻烦
 *  极端情况下，所有的数据散列到一个slot内，那么查询的时间复杂度就会变为O(logn)

适用性：

*  数据量大，并且单个数据占用的内存较大的情况下

**链表法解决哈希冲突的优化**

在Java8中，HashMap底层实现就用了散列表，解决冲突的办法是链地址法+红黑树，当链表长度超过8的时候，链表就会转换为红黑树，当红黑树节点小于6的时候，红黑树又会装换为链表。

#### 小结 ####

总之，散列表的设计要满足的要求为：

*  能够实现快速增、删、查操作
 *  内存占用合理
 *  性能稳定，不能再极端情况下，查询时间复杂度严重退化  
    这就需要我们设计优秀的：
 *  散列函数
 *  转载因子阈值
 *  解决冲突的方法
 *  rehash的方法

## 元素的有序性 ##

有些时候，我们需要维护元素的有序性，即元素取出时按照插入的顺序有序，而散列表中的元素是经过散列函数打乱顺序的。  
使用散列表和链表的组合方式维护元素输出的有序性，大概就像下面这样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]  
在PHP的数组底层实现中，由于要保证元素的增、删性能，因此也用了哈希表数据结构来实现。下图中显示的是映射表（类似哈希表的作用）的-2号位置指向了数组的0号位置：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]  
当再插入一个元素的时候，如果该元素的哈希值也是哈希表中的-2号位置，由于新元素要存入数组的1号位置（保证了数组的地址连续性和有序性），因此将哈希表-2号位置的值由0变成1，然后数组1号位置的数据的next指针指向数组0号位置，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 2]  
这样既解决了哈希冲突，又解决了元素的有序性，还是挺巧妙的。

## 附录 ##

哈希表在Redis底层数据结构中的应用：[《Redis源码解析（3）字典》][Redis_3]  
哈希表在PHP底层数据结构中的应用：[《PHP数组源码解读和底层实现分析》][PHP]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191226214714200.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191226214806979.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191226214826932.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[Redis_3]: https://blog.csdn.net/IT_10/article/details/101797398
[PHP]: https://blog.csdn.net/IT_10/article/details/94665305