环境Java:11
Redis的设计与实现
首先，今天看了Redis的词典rehash，发现和Java不一样；
于是我想：
既然 Redis采用渐进式rehash，Java的HashMap采用什么？
集中重新刷新会非常消耗性能。 hashMap中rehash的优化点在哪里？
容量扩展之前的以下代码我没有重点看，只知道这是容量扩展；
今天重点看了，没有看到红黑树：
final NodeK，V[] resize ()，V[] oldTab=table； //原始散列表的长度intoldcap=(oldtab==null )？ 0 : oldTab.length； //诱发扩大的阈值int oldThr=threshold； int newCap，newThr=0； if(oldcap0) { //130 2^30最大值if ) old cap=maximum _ capacity } { threshold=integer.max _ value； 返回old tab； () ) ) ) ) ) ) ) ) 000000000000000000000005//double threshold } else if (old thr0)//else {//zeroinitialthresholdsignifiesusingdefaultsnewcap=default _ initial _ capacity； Newthr=(int ) ) default _ load _ factor * default _ initial _ capacity； (if ) Newthr==0) floatft=) float ) newCap * loadFactor； newthr=(newcapmaximum_capacity ft ) float ) maximum _ capacity？ (int ) ft : Integer.MAX_VALUE； } threshold=newThr； @suppresswarnings((rawtypes )，() unchecked'} ) ) NodeK，v ) ) new tab=(nodek，v ) ) newnode ) newcap； table=newTab； if(oldtab！=null(/键变量e每次遍历的当前元素)//for(intj=0； j oldCap； j () { NodeK，V e； if () e=oldtab[j]！=null}{oldtab[j]=null； if(e.next==null ) /没有链表时newtab[e.hash(newcap-1 ) ]=e； elseif(einstanceoftreenode ) ) (TreeNodeK，v ) e ).split ) this，newTab，j，oldCap )； 如果else { //preserve order中有链表//前0个头节点、前0个尾节点NodeK、V loHead=null、loTail=null； //高位1的首节点、高位1的尾节点NodeK、V hiHead=null、hiTail=null； NodeK，V next； do {
// 链表当前节点 next = e.next; // 因为原数组的长度都是2^n, // 所以最高位是1，低位都是0 // e.hash & oldCap 就可以得出e.hash的高位是0 or 1 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 数据高位为1的情况 if (hiTail == null) hiHead = e; else hiTail.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位就是 乘以2n
② 因为原数组的长度都是2^n,所以最高位是1，低位都是0，e.hash & oldCap 就可以得出e.hash的高位是0 or 1；
可以看到这段代码中数组扩容后，当原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的扩容和收缩，是利用两个哈希表来完成。在设计上就和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]分配空间，空间大小为旧空间的2n;
② 将字典中维持的索引计数器rehashidx设置0，表示rehash工作正式开始；
③ 在rehash期间，每次对字典的增、删、改、查，操作，程序除了执行指定的操作之外，还会顺带将ht[0]哈希表在rehashidex索引上的所有键值对rehash到ht[1]，当完成后，程序将rehashidex的值加一。
④ 随着字典操作的不断进行，ht[0]表中的所有键值对都会被rehash到ht[1]，这时会将rehashidx属性值设置为-1，表示rehash操作结束。
换种说法：Java 扩容类似股票暴跌，一天跌到位，Redis扩容类似阴跌，跌它一个月，跌到位。
Q：Java为什么不支持收缩？
A：Java是以空间换时间，支持收缩不符合它的理念
Q：Java采用集中式扩容有没有性能问题？
A：有
个人注意的细节：
我发现Java的hashMap和Redis哈希表中的next指针，都是用来解决哈希冲突时，形成链表用的。
参考地址：
深入分析 JDK8 中 HashMap 的原理、实现和优化