【数据结构之哈希表（二）】 哈希表的扩容实现机制

哈希表的扩容实现机制

• • 导语
  • 哈希表
  • • 什么是哈希表
    • 装载因子
    • Hashcode
    • 哈希冲突
  • 扩容方案
  • • Java中的实现
    • Redis中的实现
  • 结束语

导语

哈希表是实际开发中非常常用的数据结构，也很重要。了解其底层实现细节也是非常重要的。

我这篇主要是想记录一下自己的学习结果，是关于不同应用情形下实现哈希表扩容的不同方案。

哈希表

什么是哈希表

哈希表是一个散列表，里面存储的是键值对（key-value）映射。它是一种根据关键码key来寻找值value的数据映射结构。

装载因子

装载因子，也叫负载因子（load factor），它表示散列表的装满程度。

装载因子α=元素个数/散列表长度。

当当前表的实际装载因子达到默认的负载因子值（负载极限）时，就会触发哈希表的扩容。

一般情况下，默认的负载因子值不能太大，因为其虽然减少了空间开销，但是增加了查询的时间成本；也不能太小，因为这样还会增加rehash的次数，性能较低。

Hashcode

哈希码是一种算法，尽量为不同的对象生成不同的哈希码。（但不代表不同对象的哈希码一定不同。）它可以作为相同对象判断的依据。同一对象如果没有经过修改，前后不同时刻生成的哈希码应该是一致的。

不过我们知道，判断是否相同已经有了equals()方法，那为什么还需要Hashcode()方法呢？

这是因为equals()方法的效率远不如Hashcode()方法。

同样的问题，既然Hashcode()性能那么高，那为什么还需要equals()方法呢？

这是因为equals()方法是完全可靠的，而仅仅基于哈希码比较是不完全可靠的。

也就是说：

如果两个对象相同，hashcode一定相同。

但是hashcode相同的两个对象不一定相同。

而如果两个对象相同，equals()方法得到的一定为true。

所以说Java中的HashMap既提供对equals()的重写，也提供对Hashcode()的重写。

于是，对于这种有着大量且快速的对象对比需求的hash容器，我们将两种方法结合起来用。

先使用Hashcode()方法，如果两个对象产生的哈希码不相同，那么这两个对象一定不同，不再进行后续比较；

而如果两个对象产生的哈希码相同，那么这两个对象有可能相同，于是再使用equals()方法进行比较。

哈希冲突

哈希冲突是指，不同的key经由哈希函数，映射到了相同的位置上，造成的冲突。

哈希冲突是不可避免的，但是如果冲突较严重就会影响哈希表的性能。

我们一般采用四种方式来解决哈希冲突：开放定址法、链地址法、再哈希法、建立公共溢出区。我在之前的一篇博文里有过详细介绍和举例说明。解决哈希冲突的几种办法（举例推演）。

扩容方案

当当前哈希表的装载因子过大，哈希冲突一般较严重，其增删改查的性能也随之降低。

这个时候，我们会采取扩容机制，增大哈希表的容量。

Java中的实现

我们以HashMap为例，来探究一下Java中关于哈希表扩容的实现。

首先是，每次扩容时，哈希表的容量增加为原先的两倍。

于是在扩容被触发时（实际装载因子达到默认装载因子时），需要对原先的表进行rehash。所以这时增加一个元素的性能是比较差的，因为要等待原先的表rehash之后才能增加该元素。

其冲突解决的方式是链地址法。

当某个箱子的链表长度大于8时，Java的处理方案是将其转化为红黑树。当链表长度小于6时，从红黑树转换为链表。

这是因为初始默认的箱子个数（哈希表容量）为16，而根据泊松分布，当负载因子达到0.75时，某个箱子的链表长度为8的概率为0.00000006，这种可能性是小到可以忽略的。我们甚至可以断言，如果有了这种情况的出现，那一定是哈希函数设计的不合理所导致的。

而红黑树的插入删除、查询的性能都比较良好。所以Java的这种转化机制一定程度上避免了不恰当的哈希函数导致的性能问题。

Redis中的实现

Redis 是一个高效的 key-value 缓存系统，也可以理解为基于键值对的数据库。

Redis也是采取链地址法解决哈希冲突。

我们知道，Java发生扩容的瞬间，是需要先将原哈希表中所有键值对都转移到新的哈希表中，这个过程是比较慢的，此时插入该元素的性能相当低。

而Redis对于这一部分，采取的是分摊转移的方式。即当插入一个新元素x触发了扩容时，先转移第一个不为空的桶到新的哈希表，然后将该元素插入。而下一次再次插入时，继续转移旧哈希表中第一个不为空的桶，再插入元素。直至旧哈希表为空为止。这样一来，理想情况下，插入的时间复杂度是O(1)。

在Redis的实现中，新插入的键值对会放在箱子中链表的头部，而不是在尾部继续插入。

这种方案是基于两点考虑：

一是由于找到链表尾部的时间复杂度为O(n)，且需要额外的内存地址来保存链表的尾部位置，而头插法的时间复杂度为O(1)。

二是处于Redis的实际应用场景来考虑。对于一个数据库系统来说，最新插入的数据往往更可能频繁地被获取，所以这样也能节省查找的耗时。

结束语

这次仅仅是简单介绍了一下Java、Redis中哈希表的不同扩容方案。

在学习过程中，有看到有一句话，感觉获益匪浅。即

没有完美的架构，只有满足需求的架构。

这种感受来自于：比如Java和Objective-C提供对isEqual()方法和hash()方法的重写，而没有提供一个通用的、默认的哈希函数，是考虑到了isEqual()方法可能会被重写。理由是，两个内存数据不同的对象，可能在语义上被视为相同的，而使用默认哈希函数得到的却是不同的哈希值，不符合我们的预期。

而Redis不支持重写哈希方法，因为它本身就是基于键值对的数据库，它的key值一般是可以唯一标识一个对象的。它不存在对象等同性的考虑，于是提供默认的哈希函数就可以了。