HASH table 2 - wyc902/redis GitHub Wiki

redis 的字典定义在dict.h文件中，比较重要的结构有三个

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    ........
} dict;

如上所示，下面从底层到上层逐一说明。

dictEntry就是最终存储的每个键值对。看到next指针，真是亲切，链表方式解决哈希冲突。union用来节省空间。

dictht就是hash表结构，table指向一片连续的存储空间（hash桶的首地址），size 哈希桶的长度（永远是2的n次幂），sizemask永远是size-1，看了我上篇wiki你就明白这样设计的好处。used 当前存储的键值对数量。

dict 就是字典，type和privdata是为不同类型的key做哈希操作的时候用到的，主要就是hash函数。数学水平有限没搞懂为什么redis用的hash算法足够随机，austin大神的数学能力果然不白给。

ht数组就是hash表结构，为啥有两个？再看rehashidx变量，恍然大悟，这就是为了rehash。

hash因子为 ht[0].used/ht[0].size 这个值太小，浪费存储空间，太大，hash表查询时间复杂度最小的优势就不存在。

如果是扩展操作，新的hash表大小是第一个>=ht[0].used两倍的2的n次幂

如果是收缩操作，新的hash表大小是第一个>=ht[0].used的2的n次幂

对ht[0]执行rehash，ht[0]上的所有键都rehash到ht[1]时，释放ht[0]的哈希表，ht[0].table=ht[1].table，为ht[1]建个空白的表，为下次rehash做准备。

这里不禁会想，要是ht[0]存储的键值对过多，rehash不是要持续很长时间。变忘了还有个变量rehashidx呢。

下一节：渐进式rehash。