hash table是一种高效的数据结构，广泛应用于key-value存储。 Redis的dict是典型的哈希表实现。
hash是一种扩展的hash table操作，hash table的大小无法满足需要，并且在发生过多的hash冲突后必须执行此操作。实际上，hash table是通过将原始hash table数据重新输入新数据来完成的
redis的rehash包括两种方式： lazy rehashing和active rehashing
lazy rehashing :每次操作dict时执行一个slot的rehashactive rehashing :每100ms用1ms的时间进行rehash。
dict安装中主要使用以下结构体，但实际上是典型的链式hash。
一个dict有两个hash table，由dictht结构管理，号码为0和1。
使用时优先使用0号hash table，空间不足时调用dictExpand扩展hash table。 此时，将1号hash table准备用于增量的rehash中使用。 rehash完成后释放0号，将1号保存到0号。
rehashidx是下一个需要rehash的项在ht[0]中的索引，不需要rehash时置为-1。也就是说-1时，表示不进行rehash。
迭代器在存在迭代器时执行rehash，并记录当前dict的迭代器数量，以避免在存在迭代器时rehash可能会导致值丢失或重复。
dictht的table是数组指针形式的hash表，size表的hash数组(桶)的大小，used表示hash表的元素数。 这两个值与rehash、resize进程密切相关。 sizemask与size-1相同。 这是为了便于将hash值映射到数组。
typedefstructdictentry { void * key； void *val； 直接条目* next； (} dictEntry； typedefstructdictht { dict entry * * table； unsigned long size； //hash桶的个数unsigned long sizemask； //hash取型的unsigned long used； //元素个数(} dictht； typedefstructdict { dict type * type； void *privdata； dictht ht[2]； int rehashidx；/* rehashingnotinprogressifrehashidx==-1 */int iterators；/* numberofiteratorscurrentlyrunning */} dict； typedefstructdictiterator { dict * d； int table； 索引； dictEntry *entry，*nextEntry； } dictIterator；
什么时候dict做扩容
在插入数据时调用dictKeyIndex，在该方法中调用_dictExpandIfNeeded，判断dict是否需要rehash，在dict的要素大于桶的数量的情况下调用dictExpand
/* expandthehashtableifneeded */static int _ dictexpandifneeded (dict * d )/* ifthehashtableisemptyexpanditttotheial if(d-ht[0].size==0) return dictExpand(d ) d，DICT_HT_INITIAL_SIZE )； if(d-ht(0).used=d-ht)0).sizedict _ can _ resize (return dict expand (d ) d，) ) ((d-ht (0) ) ) ) ) ) ) ) ) 返回dict _ ok； } dictExpand的工作主要是初始化hash表，缺省放大两倍，然后为ht[1]赋值，将状态更改为rehashing。 此时，该dict开始重置
扩容过程如何进行
rehash主要在dictRehash中进行。 看看什么时候进行rehash。
http://www.Sina.com/:在server cron中，如果没有后台子线程，则会调用incrementallyRehash，最终调用dictRehashMilliseconds。 incrementallyRehash的时间长，rehash的数量也多。 在此处每次执行1 millisecond rehash操作； 如果rehash未完成，请在下一个loop中继续运行。
/* rehashforanamountoftimebetweenmsmillisecondsandms1milliseconds */intdictrehashmilliseconds (dict * d，int ms )长整型wile(dictrehash(d，100 ) ) { rehashes =100； 临时开始密码(-start ms ) break； } return rehashes； () ) ) ) )。
33558 www.Sina.com/: _dictRehashStep还调用dictrehash，但在_ dictrehashstep中，一次只有一个值从ht[0]变为ht[1] 但是，_dictRehashStep由dictGetRandomKey、dictFind、dictGenericDelete、dictAdd调用，因此在每次dict的追加、删除、变更时被调用，rehashstep被调用
让我们看看rehash的制作方法。 每次dictRehash都会增加rehash的n个要素，自动调整大小时已经设定了ht[1]的大小，因此rehash的主要进程是遍历ht[0]并获取key，然后将该key暴露在ht[1]中在这个过程中active rehashing非常重要，它表示上次rehash时ht[0]下标的位置。
您可以看到，redis对dict的rehash是批量完成的，并且设计得很优雅，不会阻塞请求。
但是，调用dictFind时，可能需要对两个dict表进行查询。 唯一的优化判断是，如果key不存在于ht[0]中且不处于rehashing状态，则将速度恢复为空。 在rehashing状态下，如果ht[0]没有值，则还需要通过ht[1]进行查找。
在dictAdd的情况下，如果状态为rehashing，则将值插入ht[1]，否则插入ht[0]