dict 的结构大致如上，接下来分析一下其中最重要的几个数据成员：

• dictht::table ：哈希表内部的 table 结构使用了 链地址法 来解决哈希冲突，刚开始看的时候我很奇怪，这怎么是个二维数组？这其实是一个指向数组的指针，数组中的每一项都是 entry 链表的头结点。
• dictht ht[2] ：在 dict 的内部，维护了两张哈希表，作用等同于是一对滚动数组，一张表是旧表，一张表是新表，当 hashtable 的大小需要动态改变的时候，旧表中的元素就往新开辟的新表中迁移，当下一次变动大小，当前的新表又变成了旧表，以此达到资源的复用和效率的提升。
• rehashidx ：因为是 渐进式 的哈希，数据的迁移并不是一步完成的，所以需要有一个索引来指示当前的 rehash 进度。当 rehashidx 为 -1 时，代表没有哈希操作。

接下来我们来看 rehash 的主体部分（直接取自github的最新版本）：

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            uint64_t h;
            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    /* More to rehash... */
    return 1;
了解一个函数功能最好的入口就是它的注释。我们可以大致了解到：
 
 
rehash是以bucket(桶)为基本单位进行渐进式的数据迁移的，每步完成一个bucket的迁移，直至所有数据迁移完毕。一个bucket对应哈希表数组中的一条entry链表。新版本的dictRehash()还加入了一个最大访问空桶数(empty_visits)的限制来进一步减小可能引起阻塞的时间。
 
接下来我们深扒一下这个函数的具体实现。
 
判断dict是否正在rehashing，只有是，才能继续往下进行，否则已经结束哈希过程，直接返回。
接着是分n步进行的渐进式哈希主体部分（n由函数参数传入），在while的条件里面加入对.used旧表中剩余元素数目的观察，增加安全性。
一个runtime的断言保证一下渐进式哈希的索引没有越界。
接下来一个小while是为了跳过空桶，同时更新剩余可以访问的空桶数，empty_visits这个变量的作用之前已经说过了。
现在我们来到了当前的bucket，在下一个while(de)中把其中的所有元素都迁移到ht[1]中，索引值是辅助了哈希表的大小掩码计算出来的，可以保证不会越界。同时更新了两张表的当前元素数目。
每一步rehash结束，都要增加索引值，并且把旧表中已经迁移完毕的bucket置为空指针。
最后判断一下旧表是否全部迁移完毕，若是，则回收空间，重置旧表，重置渐进式哈希的索引，否则用返回值告诉调用方，dict内仍然有数据未迁移。 
 

 渐进式哈希的精髓在于：数据的迁移不是一次性完成的，而是可以通过dictRehash()这个函数分步规划的，并且调用方可以及时知道是否需要继续进行渐进式哈希操作。如果dict数据结构中存储了海量的数据，那么一次性迁移势必带来redis性能的下降，别忘了redis是单线程模型，在实时性要求高的场景下这可能是致命的。而渐进式哈希则将这种代价可控地分摊了，调用方可以在dict做插入，删除，更新的时候执行dictRehash()，最小化数据迁移的代价。 
 在迁移的过程中，数据是在新表还是旧表中并不是一个非常急迫的需求，迁移的过程并不会丢失数据，在旧表中找不到再到新表中寻找就是了。
 
所以在后面的dict相关的函数里，会大量的看到
 
if(dictIsRehashing(d))
   _dictRehashStep(d);  // 单步rehash
 
这样的代码。
 
最后是从《Redis设计与实现》中copy来的图解，可以帮助大家更形象地理解整个incremental rehash的过程： 
  
  
  
  
  
 
 
redis高性能的保障采取了各式各样的措施，不乏很多优雅惊艳的工程技巧，非常值得我们学习。在阅读源码的过程中，还给我留下深刻印象的一点就是：redis对于内存的管理到了精细的程度，也可能是我太久没看pure c的项目了吧，收获还是颇丰的。希望能和大家一起共同进步。
HashMap的内部实现机制
HashMap的内部实现机制是对数据结构中哈希表（Hash Table）的实现,Hash表又叫散列表。
Hash表是根据关键码Key来访问其对应的值Value的数据结构，他是通过一个映射函数把关键码映射到表中一个位置
来访问该位置的值，从而加快查找
   Redis 的字典使用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。
   哈希表中的键值对随着不断进行的操作增加或减少，为了将哈希表的负载因子维持在较为合理的范围内，程序需对哈希表的大小进行相应的扩展或者收缩，而rehash(重新散列)操作就可以完成这项工作。
Redis 对字典的哈希表执行 reha...
				
rehash
随着操作的不断执行， 哈希表保存的键值对会逐渐地增多或者减少， 为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。
扩展和收缩哈希表的工作可以通过执行 rehash （重新散列）操作来完成， Redis 对字典的哈希表执行 rehash 的步骤如下：
为字典...
				
HashMap中的hash与rehash我们知道HashMap中经常用到hash（）方法。比如：put（）方法中public V put(K key, V value){
        if(key==null)
            return putForNullKey(value) ;
        int hash=hash(key.hashCode());   
				
在Redis中，键值对（Key-Value Pair）存储方式是由字典（Dict）保存的，而字典底层是通过哈希表来实现的。通过哈希表中的节点保存字典中的键值对。我们知道当HashMap中由于Hash冲突（负载因子）超过某个阈值时，出于链表性能的考虑，会进行Resize的操作。Redis也一样。
在redis的具体实现中，使用了一种叫做渐进式哈希(rehashing)的机制来提高字典的缩放效率，避...