hashtable的实现有很多，redis的dict.c 是其中之一。

    dict 包含了2个dictht hashtable ht[0], ht[1]。

     client版本的dict是没有dictht的概念。加入dictht的概念存在2个ht的目的是为了在rehash的时候可以平滑的迁移bucket里的数据，而不像client的dict要把老的hash table里的一次性的全部数据迁移到新的hash table，这在造成一个密集型的操作，在业务高峰期不可取。

    ht是hashtable的简称，实际上是一个指针数组，数组的个数由dictht->size决定，是DICT_HT_INITIAL_SIZE的整数倍。每个元素(bucket)指向一个dictEntry的单链表来解决hash的conflict。查询某个key，需要先hash，定位到bucket,再通过链表遍历。

    key经过hash函数后，与dictht->sizemask求与均分到ht的每个bucket上。dictht->used表示这个ht里包含的key的个数，也就是dictEntry的个数，每次dictAdd成功+1。链表的加入为头指针的方法加入，这样dictAdd更加的方便。

    随着key不断的添加，bucket下的单链表越来越长，查找、删除效率越来越低，需要对ht进行expand，增加bucket个数，让链表的长度减少。bucket数量的增多，原有bucket的key需要迁移到新的bucket上，于是有了rehash的这个过程。

    ht[1]就是为了rehash而产生，新的ht size是ht[0]的两倍2， 随着dictAdd，dictFind函数的调用，ht[0]的每个bucket会rehash加入到ht[1]里。dict->rehashidx 是ht[0] 需要rehash就是迁移到ht[1]的bucket的索引，从0开始直到ht->used==0。

     rehash除了每次伴随dictAdd，dcitFind而迁移一个bucket的所有dictEntry，还有一种一次hash100个bucket，直到消耗了某个时间点为止的做法。

    rehash的步骤：

     拿到一个bucket， 遍历这个链表的每个kv，对key进行hash然后于sizemask求与，定位ht[1]的新bucket位置，

     加入到链表，迁移后ht[0].used-，ht[1].used++。

     直到ht[0].used=0，释放ht[0]的table，再赋值ht[0]= ht[1]，再把则ht[1]reset。

    rehash的期间：

     由于ht[1]是ht[0]size的2倍，每次dictAdd的时候都会rehash一次，不会出现后ht[1] 满了，而ht[0]还有数据的事情。

     查询会先查ht[0]再查询ht[1]，在rehash的过程中，不会出现再次expand。

     新的key加到ht[1]。

    expand的条件：

     table的位置已经满了，糟糕的hash函数造成的skrew导致永远不会expand。

     key的个数除以table的大小，超过了dict_force_resize_ratio。

建议继续学习：

1. redis源代码分析 - persistence    (阅读：31141)
2. HashMap解决hash冲突的方法    (阅读：11246)
3. 关于memcache分布式一致性hash    (阅读：10694)
4. Redis消息队列的若干实现方式    (阅读：10704)
5. 基于Redis构建系统的经验和教训    (阅读：9284)
6. 浅谈redis数据库的键值设计    (阅读：8286)
7. redis在大数据量下的压测表现    (阅读：7379)
8. redis运维的一些知识点    (阅读：7418)
9. Redis和Memcached的区别    (阅读：6776)
10. Redis作者谈Redis应用场景    (阅读：6565)