Redis中的hash结构和扩容机制

1.rehash原理

hash包含两个数据结构为字典数组ht[0]和ht[1]。其中ht[0]用来存放数据，ht[1]在rehash时使用。

扩容时，ht[1]的大小为第一个大于等于ht[0].used*2的2的幂次方的数；

收缩时，ht[1]的大小为第一个大于等于ht[0].used的2的幂次方的数；

将ht[0]中的所有键值对rehash到ht[1]中：rehash指重新计算键的hash值和存放的索引位置。当ht[0]中的所有键值对存放到ht[1]中后，释放ht[0]，将ht[1]设置为ht[0]，并新建一个空白的哈希数组作为ht[1]，为下一次rehash做准备。

2.渐进式hash

在扩容或者收缩时，如果哈希数组中有很多元素，一次性rehash会占用服务器资源，所以采用渐进式rehash。

hash初始容量为4，当元素个数和hash长度一致时扩容，hash变为原来的两倍。

hash结构内一个游标rehashindex，当rehashindex为0时，代表开始rehash。

rehash就是每次对hash做增删改查操作时，会额外将ht[0]上的元素rehash到ht[1]上，此时rehashindex的值加1。

当ht[0]上的元素rehash完成后，rehash的值设为-1，表示rehash结束。

在渐进式rehash时，如果有增删改查操作，当要操作的元素的下标大于rehashindex时访问ht[0]，否则访问ht[1]。

3.渐进式rehash特点

分而治之，每次对hash进行一次操作才rehash一个元素，避免集中式rehash导致占用系统资源，redis是单线程，阻塞其他线程。