Redis之字典(hashtable)

客官°小女子只卖身不卖艺 2022-05-23 10:24 255阅读 0赞

# 1、介绍 #

字典采用hashtable实现，碰撞采用拉链法，也就是通过链表联结key的hash值相同的节点。看过STL内部hash实现，这个就很容易，重新造了个轮子。套路，指针数组+多条链表。

# 2、实现 #

## **1、结构体之道** ##

写任何代码，都需要有一个大框架，那么定义好对应的结构体就是实现优秀代码的第一步。从作者定义的结构体可以看出，作者真的很细心，绝对在写之前，认真思考了整个内存结构模型，才可以写出这种代码。  
以下4个结构体是Redis的Hashtable实现的基础。

//hash节点
    typedef struct dictEntry {
       //hash节点
        void *key;//键，一半是sds
        union {
       //联合体牛逼，导致值可以多用途，可以存储指针或存储整数或浮点数。必定可以存储上面类型之前，通过不同的引用，告诉编译器如何解释对应的内存块。
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
        struct dictEntry *next;//下一个节点，解决碰撞冲突
    } dictEntry;
    
    //定义hash需要使用的函数
    typedef struct dictType {
       //定义函数指针，例如使用的hash函数
        uint64_t (*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;//定义对应的函数指针，例如定义hash函数
    
    /* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. */
    //定义一个hash桶，用来管理hashtable
    typedef struct dictht {
       //管理hashtable
        dictEntry **table;//指针数组，这个hash的桶
        unsigned long size;//元素个数
        unsigned long sizemask;//
        unsigned long used;//
    } dictht;
    
    //字典，管理两个dicht，为什么需要定义两个，为了在扩容的时候使用。
    typedef struct dict {
       //管理两个dictht，主要用于动态扩容。
        dictType *type;//函数管理
        void *privdata;
        dictht ht[2];
        long rehashidx; /* 扩容标志rehashing not in progress if rehashidx == -1 */
        unsigned long iterators; /* number of iterators currently running */
    } dict;
    
    /* If safe is set to 1 this is a safe iterator, that means, you can call * dictAdd, dictFind, and other functions against the dictionary even while * iterating. Otherwise it is a non safe iterator, and only dictNext() * should be called while iterating. */
    typedef struct dictIterator {
       //简单的迭代器封装，STL内部也是这么实现
        dict *d;//字典
        long index;//索引
        int table, safe;
        dictEntry *entry, *nextEntry;//当前元素，下一个元素
        /* unsafe iterator fingerprint for misuse detection. */
        long long fingerprint;
    } dictIterator;

外部调用hash表，直接使用dict以及其对应的函数，就可以实现hashtable的基本功能，节点中可以存储整数、浮点、指针(可以指向其他数据结构，包括再次指向一个dict的hash表，这就是Redis整个对象系统实现的根本基础)。所以的代码就在于如何组织内存，通过何种数据结构，可以使得我们将值放到合适的位置，并且在寻找对应值的时候，速度很快。这就是数据结构的强大之处，所以的代码都为了在内存上面快速的存数据，找数据。这就是绝对数据结构之道。  
说了这么多，还不如来一个内存模型直接，作者必然先有了这种内存模型，才写对应的代码。  
![这里写图片描述][70]

## **2、hash算法** ##

Redis的作者使用的`siphash`算法，而memcached作者使用`jenkins_hash`或者`murmur3_hash`。衡量一个hash算法好坏的依据就是，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。当然这种复杂的hash算法属于数学问题，不该Redis作者本人研究，通常使用现成的开源，就和一致性hash算法一样，通常使用现成的。

## **3、hash扩容** ##

为什么需要扩容。因为当hashtable存储的元素过多，可能由于碰撞也过多，导致其中某天链表很长，最后致使查找和插入时间复杂度很大。因此当元素超多一定得时候就需要扩容。当元素比较小的时候就需要缩容以节约不必要的内存。Redis的作者定义这个操作叫做rehash操作，通过rehashidx索引完成。

Redis对哈希表的rehash操作步骤如下：  
1、为字符ht\[1\]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht\[0\]当前包含的键值对的数量。

*  扩展：ht\[1\]的大小为第一个大于等于ht\[0\].used\*2。
 *  收缩：ht\[1\]的大小为第一个大于等于ht\[0\].used/2 。

2、将所有的ht\[0\]上的节点rehash到ht\[1\]上，重新计算hash值和索引，然后放入指定的位置。  
3、当ht\[0\]全部迁移到了ht\[1\]之后，释放ht\[0\]，将ht\[1\]设置为ht\[0\]表，并创建新的ht\[1\]，为下次rehash做准备。

static int dict_can_resize = 1;
    static unsigned int dict_force_resize_ratio = 5;//负载因子。
    
        if (d->ht[0].used >= d->ht[0].size &&
            (dict_can_resize ||
             d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
        {
            return dictExpand(d, d->ht[0].used*2);
        }

当负载因子大于1或5的时候扩容，当负载因子小于0.1的时候收缩。这是几句空话，后面咱们代码鑫鑫分析。

## **4、渐进式hash** ##

如果哈希表里保存的键值对数量是四百万、四千万甚至四亿个键值对，那么要一次性将这些键值对全部rehash到ht\[1\]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。因此，为了避免rehash对服务器性能造成影响，服务器不是一次性将 ht\[0\]里面的所有键值对全部rehash到ht\[1\]，而是分多次、渐进式地将ht\[0\]里面的键值对慢慢地rehash到ht\[1\]。  
以下是晗希表渐进式 rehash 的详细步骤：

*  为ht\[1\]分配空间，让字典同时持有ht\[0\]和ht\[1\]两个哈希表。
 *  在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash  
    工作正式开始。
 *  在rehash进行期间，\*\*每次对字典执行添加、删除、查找或者更新操作时，程序除  
    了执行指定的操作以外，\*\*还会顺带将ht\[0\]哈希表在rehashidx索引上的所有键值对  
    rehash到ht\[1\]，当rehash工作完成之后，程序将rehashidx+1(表示下次将rehash下一个桶)。
 *  随着字典操作的不断执行，最终在某个时间点上，ht\[0\]的所有键值对都会被rehash至ht\[1\]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

**渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash 而带来的庞大计算量。**而memcached通过也需要rehash，但是它是另外单独开一个线程，专门执行rehash操作。这就是区别与Redis的做法，个人任何Redis的作者方法更胜一筹。因为这种分治算法，将全部负载，均摊到了每次的操作过程中，在单个线程中实现。这个就是迁移线程，[memcached中的迁移线程。][memcached]

## **5、上代码了** ##

基本上仔细分析下面4个函数，那么这个dict的整个管理过程就一清二楚了，基本也如同前面描述一样。Redis的作者写的代码真的很容易看懂，将每一步条件判断都写出来，没有像memcached作者一样，将许多逻辑判断写在了一些，很难理清思绪。  
再次表白以下antirez大神。写代码合乎常人思维。

**1、dictCreate**

**2、dictAdd**

**3、dictReplace**

**4、dictDelete**

[70]: /images/20220523/90680cdc4553469fb4e486bbdcb85f33.png
[memcached]: https://blog.csdn.net/luotuo44/article/details/42773231#t5