一、HashMap

1、关于1.7的源码

HashMap 数据结构是什么？

https://blog.csdn.net/P_Doraemon/article/details/80353579
https://www.cnblogs.com/zhuoqingsen/p/8577646.html

3、hash

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
image.pngimage.png
图1为空的字典，现在有一个的键值对要插入，首先对k0值计算哈希值和索引值。计算hash值一般使用MurmurHash2、MurmurHash3算法。

针对哈希冲突💥，使用链地址法来解决冲突，结构是单链表或者红黑树结构。
image.png

4、rehash

随着增加或删除的操作变化，哈希表里存的键值对会逐渐地增多或减少，为了让哈希表的负载因子(load factor)维持在一个合理的范围之内(一般默认0.1~0.75)。当哈希表保存的键值对数太多或太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。扩展和收缩哈希表的工作可以通过执行 rehash(重新散列)操作来完成，Redis对字典的哈希表执行 rehash的步骤如下:
1、为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量(就是ht[0].used属性的值)。如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used*2 的2(2的n次方幂)；如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的2。
2、将保存在 ht[0] 中的所有键值对 rehash到 ht[1] 上面：rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上。
3、当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后(ht[0]变为空表)，释放 ht[0]，将 ht[1] 设置为 ht[0]，并在ht[1] 新创建一个空白哈希表，为下一次 rehash做准备。

示例：
image.png

  • ht[0].used 当前的值为4，4*2=8，而8恰好是第一个大于等于4的2次方,所以程序会将 ht[1] 哈希表的大小设置为8，下图为 ht[1] 在分配空间之后字典的样子。

image.png

  • 将ht[0]包含的四个键值对都rehash到ht[1]。

image.png

  • 释放ht[0]，并将ht[1]设置为ht[0]，然后为ht[1]分配一个空白哈希表。至此对哈希表的扩展操作执行完毕，程序成功将哈希表的大小从原来的容量为4改为了现在的容量为8。

image.png

5、渐进式rehash

在扩展或收缩哈希表时，需要将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面，但是这个 rehash 过程并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。当 ht[0]里只保存着四个键值对，那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht[1]；但如果哈希表里保存的键值对数量不是四个，而是四百万、四千万甚至四亿个键值对，那么要一次性将这些键值对全部 rehash 到 ht[1] 的话，庞大的计算量可能会导致服务器在一段时间内停止服务。因此，为了避免 rehash 对服务器性能造成影响，服务器不是一次性将 h[0] 里面的所有键值对全部 rehash 到ht[1]，而是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到ht[1]。

详细步骤：

  • 为 ht[1] 分配空间，让字典同时持有ht[0]和ht[1]两个哈希表；

image.png

  • 在字典中维持一个索引计数器变量 rehashidx，并将它的值设置为0，表示 rehash工作正式开始；在 rehash 进行期间，每次对字典执行添加、删除、查找或更新操作时，然后还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]上，之后rehashidx++。这样当执行足够的crud操作次数时，rehashidx 便可以遍历完 ht[0] 所以的位置。

image.png

  • 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被 rehash 至 ht[1]，这时程序将 rehashidx 属性的值设为-1，表示 rehash 操作已完成。

image.png image.png

渐进式 rehash的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。
在进行渐进式rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在渐进式rehash 进行期间，字典的删除D、查找R、更新U等操作会在两个哈希表上进行。例如：要在字典里面查找一个键的话，程序会先在 ht[0] 里面进行查找，如果没找到的话，就会继续到 ht[1] 里面进行查找。对于新添加到字典的键值对，则一律会被保存到 ht[1] 里面，而 ht[0] 则不再进行任何添加操作，这一措施保证了 ht[0] 中键值对的数量会只减不增，并随着 rehash 操作的执行而最终变成空表。