Redis学习笔记：字典rehash底层实现与Java区别

本文主要是介绍Redis学习笔记：字典rehash底层实现与Java区别，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

环境

Java：11
Redis设计与实现

前言

今天在看Redis的字典rehash时，发现其与Java不一样；
并由此产生了如下思考：
① Redis既然采用的是渐进式rehash，那么Java的HashMap采用的是什么？
② 集中式重新rehash是非常耗性能的，hashMap中rehash的优化点在哪里？

扩容

以前下面这段代码我没有重点看，只知道这是在扩容；
今天重点看了下，不过红黑树没看：

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;// 原哈希表的长度int oldCap = (oldTab == null) ? 0 : oldTab.length;// 触发扩容的临界值int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {// 1<<30 2^30 最大值if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 左移1位相当于乘2, newCap就变成了原来的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {// 关键变量 e 每次遍历的当前元素// for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)// 无链表的情况newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order 有链表的情况// 高位为0的头节点、高位为0的尾节点Node<K,V> loHead = null, loTail = null;// 高位为1的头结点、高位为1的尾节点Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {// 链表当前节点next = e.next;// 因为原数组的长度都是2^n,// 所以最高位是1，低位都是0// e.hash & oldCap 就可以得出e.hash的高位是0 or 1if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;} else {// 数据高位为1的情况if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;// 原索引没变情况newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;// 因为扩容导致索引变化的情况newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

这段代码整体理解起来不算难，需要注意地方：
① 移位： <<n 左移n位就是乘以2ⁿ
② 因为原数组的长度都是2^n,所以最高位是1，低位都是0，e.hash & oldCap 就可以得出e.hash的高位是0 or 1；

`newTab[j + oldCap] = hiHead;` 的理解

可以看到这段代码中数组扩容后，当原hash的高位为1时，新索引的位置是j + oldCap；

为什么时这样的呢？

现在我们假设HashMap初始容量是8；
现在需要存入key为13这么一个数字；
那么它的索引位置在哪呢？

索引位置：key & (length - 1)
13 &（8-1）= 13 & 7
13 转成二进制：1101
7 转成二进制：0111

做&运算后：0101 = 5
如下图所示：
在这里插入图片描述

假设现在扩容了，容量变为了16，即原来的一倍；

我们再来计算下新的索引位置：
13 转成二进制：1101
15 转成二进制：1111

做&运算后：1101 = 13，这个位置正好是 5 + 8 = 13，
即旧索引位置 + 扩容前的容量：newTab[j + oldCap] = hiHead

在这里插入图片描述
所以Java在扩容时，在重新计算hash值这一块是很快的；

Redis

Redis的扩容和收缩，是利用两个哈希表来完成。在设计上就和Java有区别；

typedef struct dict {dictType *type;void * privdata;// 哈希表dictht ht[2];// rehash索引，当rehash不在进行时，值为-1int rehashidx;
} dict;

从上面的结构中就可以看出，Redis字典创建时就有两个哈希表，不rehash的情况下，只使用ht[0]这个哈希表，当发生扩容和收缩时，才会用到ht[1]哈希表和rehashidx这个属性；

Redis采用的是渐进式过程，其重新计算hash和数据搬运的过程是发生在增删改查的操作中的，而不是集中一次性完成的。

rehash的过程：

① 为ht[1]分配空间，空间大小为旧空间的2ⁿ;
② 将字典中维持的索引计数器rehashidx设置0，表示rehash工作正式开始；
③ 在rehash期间，每次对字典的增、删、改、查，操作，程序除了执行指定的操作之外，还会顺带将ht[0]哈希表在rehashidex索引上的所有键值对rehash到ht[1]，当完成后，程序将rehashidex的值加一。
④ 随着字典操作的不断进行，ht[0]表中的所有键值对都会被rehash到ht[1]，这时会将rehashidx属性值设置为-1，表示rehash操作结束。