Redis中使用哈希表作为底层实现的是叫做字典的数据结构,字典又称为符号表、关联数组或映射(map)。是一种保存键值对的抽象数据结构。
ht 属性是一个包含两个项的数组,数组中的每个项都是一个dictht哈希表,一般情况下使用的都是ht[0]的哈希表,而ht[1]的哈希表只会在rehash的时候使用。
随着操作的进行,哈希表中的键值对会逐渐增多或减少,这时为了让哈希表负载因子位置在一个合理的范围之内就会对哈希表大小进行扩展或收缩即rehash。
Redis中hash扩容过程
redis字典(hash表)当数据越来越多的时候,就会发生扩容,也就是rehash,redis中的hash表采用的是渐进式。 redis字典(hash表)底层有两个数组,还有一个rehashidx用来控制rehash,初始默认hash长度为4,当元素个数与hash表长度一致时,就发生扩容,hash长度变为原来的二倍。
redis中的hash则是渐进式rehash的过程,详细步骤如下:
- 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。
- 将rehashindex的值设置为0,表示rehash工作正式开始。
- 在rehash期间,每次对字典执行增删改查操作以外,还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1],然后rehashindex的值+1。
- 随着字典操作的不断执行,最终会在某一时间段上ht[0]被完全rehash到ht[1],这时将rehashindex的值设置为-1,表示rehash操作结束。
需要注意的是在渐进式rehash的过程,如果有增删改查操作时,如果index大于rehashindex,访问ht[0],否则访问ht[1]。