hash地址_redis中的hash扩容、渐进式rehash过程

背景： redis字典（hash表）当数据越来越多的时候，就会发生扩容，也就是rehash 对比：java中的hashmap，当数据数量达到阈值的时候(0.75)，就会发生rehash，hash表长度变为原来的二倍，将原hash表数据全部重新计算hash地址，重新分配位置，达到rehash目的

redis中的hash表采用的是渐进式hash的方式：

1、redis字典（hash表）底层有两个数组，还有一个rehashidx用来控制rehash

2、初始默认hash长度为4，当元素个数与hash表长度一致时，就发生扩容，hash长度变为原来的二倍

3、redis中的hash则是执行的单步rehash的过程：

每次的增删改查，rehashidx+1，然后执行对应原hash表rehashidx索引位置的rehash

总结：

在扩容和收缩的时候，如果哈希字典中有很多元素，一次性将这些键全部rehash到

ht[1]

的话，可能会导致服务器在一段时间内停止服务。所以，采用渐进式rehash的方式，详细步骤如下：

1. 为

   ht[1]

   分配空间，让字典同时持有

   ht[0]

   和

   ht[1]

   两个哈希表
2. 将

   rehashindex

   的值设置为 ，表示rehash工作正式开始
3. 在rehash期间，每次对字典执行增删改查操作是，程序除了执行指定的操作以外，还会顺带将

   ht[0]

   哈希表在

   rehashindex

   索引上的所有键值对rehash到

   ht[1]

   ，当rehash工作完成以后，

   rehashindex

   的值

   +1

4. 随着字典操作的不断执行，最终会在某一时间段上

   ht[0]

   的所有键值对都会被rehash到

   ht[1]

   ，这时将

   rehashindex

   的值设置为

   -1

   ，表示rehash操作结束

渐进式rehash采用的是一种分而治之的方式，将rehash的操作分摊在每一个的访问中，避免集中式rehash而带来的庞大计算量。 需要注意的是在渐进式rehash的过程，如果有增删改查操作时，如果

index

大于

rehashindex

，访问

ht[0]

，否则访问

ht[1]。