redis内部数据结构详解之字典dict

小咪咪 2022-06-15 01:44 253阅读 0赞

**redis内部数据结构详解之字典dict**

对于redis的Dict(字典)，虽说算法上跟市面上一般的Dict实现没有什么区别，但是redis的Dict有2个特殊的地方那就是它的rehash（重新散列）和它的字典节点单向链表。

以下是dict用到的结构：

typedef struct dictEntry {//字典的节点  
        void *key;  
        union {//使用的联合体  
            void *val;  
            uint64_t u64;//这两个参数很有用  
            int64_t s64;  
        } v;  
        struct dictEntry *next;//下一个节点指针  
    } dictEntry;  
      
    typedef struct dictType {  
        unsigned int (*hashFunction)(const void *key); //hash函数指针  
        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 { //字典hash table  
        dictEntry **table;//可以看做字典数组，俗称桶bucket  
        unsigned long size; //指针数组的大小，即桶的层数  
        unsigned long sizemask;  
        unsigned long used; //字典中当前的节点数目  
    } dictht;  
      
    typedef struct dict {  
        dictType *type;  
        void *privdata; //私有数据  
        dictht ht[2];   //两个hash table  
        int rehashidx; /* rehashing not in progress if rehashidx == -1 */ //rehash 索引  
        int iterators; /* number of iterators currently running */ //当前该字典迭代器个数  
    } dict;

当运用哈希算法计算出 k0的索引 ，redis就会插入到指定的位置：

![Center][]

当k2和k1出现计算出键索引相同的情况下，这时候redis的dictEntry(字典节点)有一个next属性（单项链表），redis会把冲突键索引的元素排到后插入数据的前面，从而解决了这个问题：

![Center 1][]

现在如果在插入2条元素，此时数据量已经超过dict的负载了，redis就会启用rehash，虽然是rehash操作但是redis是采用了渐进式操作，并不是一下子内存不够用了 就直接操作内存，然后全部转移数据，这样会导致操作很耗时，redis考虑到了这一点，然后

先把ht\[1\]另一张dict结构中扩容一个数量为ht\[0\].used\*2的dictEntry数组，然后把2条数据通过哈希算法加入到这个数组中。

![Center 2][]

然后把上面的元素一个个异步渐渐移动到下面的数组中，在这个过程中如果客户端去操作元素时，如果在ht\[0\]中检查找不到建，就会去检查ht\[1\]中是否有指定的键，从而不影响数据的使用，而且可以避免一次性操作rehash带来的耗时问题，最后reshash完成了，就直接把ht\[1\]和ht\[0\]切换位置并且清空弃用的哈希节点数组，从而完成所有操作。

![Center 3][]

![Center 4][]

[Center]: /images/20220615/404dfb22940140519fc962563002f608.png
[Center 1]: /images/20220615/e0cc70c1bdf44fc1978d49e2e392af4d.png
[Center 2]: /images/20220615/b325b37761004453ad577fa64625d03f.png
[Center 3]: /images/20220615/101fdbd124794f9ca9b030828073d99f.png
[Center 4]: /images/20220615/5445ae8026084e11a245ada970601b90.png