redis3.0.7源码阅读(五)redis字典

深藏阁楼爱情的钟 2022-07-13 11:58 277阅读 0赞

版本：3.0.7

1.源文件

dict.h

dict.c

2.字典数据结构

/*
     * 哈希表节点
     */
    typedef struct dictEntry {
        // 键
        void *key;
        
        // 值
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
    
        // 下一个hash节点，形成链表
        struct dictEntry *next;
    } dictEntry;
    
    /*
     * 字典类型特定函数
     */
    typedef struct dictType {
        // 计算哈希值的函数
        unsigned int (*hashFunction)(const void *key);
    
        // 复制键的函数
        void *(*keyDup)(void *privdata, const void *key);
    
        // 复制值的函数
        void *(*valDup)(void *privdata, const void *obj);
    
        // 比较键的函数
        int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    
        // 销毁键的函数
        void (*keyDestructor)(void *privdata, void *key);
    
        // 销毁值的函数
        void (*valDestructor)(void *privdata, void *obj);
    } dictType;
    
    /*
     * 哈希表
     * 每个字典都使用两个哈希表，用于扩容
     */
    /* This is our hash table structure. Every dictionary has two of this as we
     * implement incremental rehashing, for the old to the new table. */
    typedef struct dictht {
        // 哈希表数组,值是指向哈希节点的指针
        dictEntry **table;
    
        // 哈希表大小
        unsigned long size;
    
        // 哈希表大小掩码，用于计算索引值
        // 总是等于 size - 1
        unsigned long sizemask;
    
        // 哈希表已有节点的数量(链表也计算在内)
        unsigned long used;
    } dictht;
    
    /*
     * 字典
     */
    typedef struct dict {
        // 类型特定函数
        dictType *type;
    
        // 私有数据
        void *privdata;
    
        // hash表
        dictht ht[2];
    
        // rehash索引，当rehash不进行时，值为-1
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    
        // 目前正在运行的安全迭代器的数量
        int iterators; /* number of iterators currently running */
    } dict;

3.空间分布

![SouthEast][]

4.一些特性

4.1 add键值时会触发rehash检查，hash表used/size>=1时，会发生rehash重置hash表大小，当redis在执行bgsave时，如果used/size<5，则可以暂时先不rehash，有益于copy-on-write(减少内存的写)，当used/size>5，则会强制rehash，rehash的大小是2倍(3.2版本还是)。

4.2 hash表ht\[1\]用于rehash，当正在rehash时，add只会插入ht\[1\]。find则先查找ht\[0\]，再查找ht\[1\]，而没有rehash时，只会查找ht\[0\]。

4.3 redis的rehash不是一次性完成的，避免海量数据一次操作带来的阻塞，redis通过分批rehash来完成hash表的扩容。

4.4 关于索引冲突问题，redis通过链表法解决，把最新插入的key放在链表头，效率相比放在链表尾更高。

5.5 redis使用MurmurHash2算法计算hash键

原文出自： [http://blog.csdn.net/daiyudong2020/article/details/54236570][http_blog.csdn.net_daiyudong2020_article_details_54236570]

End;

[SouthEast]: /images/20220713/74eb424568e3439588939c287a77f9ab.png
[http_blog.csdn.net_daiyudong2020_article_details_54236570]: http://blog.csdn.net/daiyudong2020/article/details/54236570