redis源码学习之字典

灰太狼 2022-07-11 05:49 237阅读 0赞

## 数据结构 ##

几个重要的数据结构：  
`dict`、`dictht`、`dictEntry`分别表示字典，hash表，hash桶。  
字典结构体，主要包含了hash表数组（有两个hash表，其中一个备用做rehash用）。

typedef struct dict {
        // 类型特定函数
        dictType *type;//函数指针
        // 私有数据
        void *privdata;
        // 哈希表
        dictht ht[2];
        // rehash 索引
        // 当 rehash 不在进行时，值为 -1
        int rehashidx; /* rehashing not in progress if rehashidx == -1 */
        // 目前正在运行的安全迭代器的数量
        int iterators; /* number of iterators currently running */
    } dict;

hash表结构，除了hash表数组存储hash桶外，里面包含了hash表的信息，比如大小、掩码等。

typedef struct dictht {
    
        // 哈希表数组
        dictEntry **table;
    
        // 哈希表大小
        unsigned long size;
    
        // 哈希表大小掩码，用于计算索引值
        // 总是等于 size - 1
        unsigned long sizemask;
    
        // 该哈希表已有节点的数量
        unsigned long used;
    
    } dictht;

用来保存key-value对

typedef struct dictEntry {
    
        // 键
        void *key;
    
        // 值
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
        } v;
    
        // 指向下个哈希表节点，形成链表
        struct dictEntry *next;
    
    } dictEntry;

## 计算hash和索引 ##

hash表的核心就在于计算hash和索引。  
hash值使用key通过hash函数来计算，计算出来的hash用来计算索引，索引表示key-value对存在hash表中的位置。  
例如：

hash=dict->type->hashFunction(key);
    index=hash&dict->ht[0].sizemask;

这里通过掩码计算位置，除此之外还可以通过取模的办法计算。

index = h->hash_func(key) % h->bucket_tot;

**ps：Redis使用MurmurHash2算法来计算key的hash值。**

## 冲突解决 ##

解决冲突的办法有很多，比如线性探测、二次探测这都属于开放寻址，还有链地址法，这就是Redis使用的办法，假如两个key最终计算出来的index相同，那么后插入进hash表的key-value对将以头插法的方式插入到链表中。  
这就是为什么在`dictht`结构中`table`是一个二次指针了。

## rehash ##

什么是rehash，首先需要明白的概念就是负载因子，它的计算公式如下：  
负载因子=总key−value对hash表的大小(1)

负载因子越小说明hash表中备用空间就越多，当负载因子超过某个大小时，就需要对hash表进行扩容，也就是所谓的rehash。

rehash的过程就是将ht\[0\]中的key-value对迁移到ht\[1\]中，不过由于要进行扩容，因此**ht\[1\]的size要比ht\[0\]大**，redis的规则是，第一个大于等于ht\[0\].used\*2的2n，比如说`ht[0].used=7`扩容之后的大小应该为16=24>2∗7=14

当数据量很大的时候，rehash将非常耗时，要将所有的key-value对进行迁移是一项很费时间的事情，因此，redis会在增删改查这些操作中进行渐进式的rehash，也就是说，每次进行增删改查操作时会查一下标志位，看是否需要rehash，如果是，将进行一次rehash操作，这一点在代码中很容易看出来，在很多操作中都会查询是否在进行rehash，如果是，则单步的rehash一次：

if (dictIsRehashing(d)) _dictRehashStep(d);
    
    int dictRehash(dict *d, int n) {
       //
    //...
        while(n--) {
            dictEntry *de, *nextde;
            /* Check if we already rehashed the whole table... */
            // 如果 0 号哈希表为空，那么表示 rehash 执行完毕
            if (d->ht[0].used == 0) {
                // 释放 0 号哈希表
                zfree(d->ht[0].table);
                // 将原来的 1 号哈希表设置为新的 0 号哈希表
                d->ht[0] = d->ht[1];
                // 重置旧的 1 号哈希表
                _dictReset(&d->ht[1]);
                // 关闭 rehash 标识
                d->rehashidx = -1;
                // 返回 0 ，向调用者表示 rehash 已经完成
                return 0;
            }
    
            /* Note that rehashidx can't overflow as we are sure there are more
             * elements because ht[0].used != 0 */
            // 确保 rehashidx 没有越界
            assert(d->ht[0].size > (unsigned)d->rehashidx);
    
            // 略过数组中为空的索引，找到下一个非空索引
            while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
    
            // 指向该索引的链表表头节点
            de = d->ht[0].table[d->rehashidx];
            /* Move all the keys in this bucket from the old to the new hash HT */
            // 将链表中的所有节点迁移到新哈希表
            // T = O(1)
            while(de) {
                unsigned int h;
    
                // 保存下个节点的指针
                nextde = de->next;
    
                /* Get the index in the new hash table */
                // 计算新哈希表的哈希值，以及节点插入的索引位置
                h = dictHashKey(d, de->key) & d->ht[1].sizemask;
    
                // 插入节点到新哈希表----插入到头部
                de->next = d->ht[1].table[h];
                d->ht[1].table[h] = de;
    
                // 更新计数器
                d->ht[0].used--;
                d->ht[1].used++;
    
                // 继续处理下个节点
                de = nextde;
            }
            // 将刚迁移完的哈希表索引的指针设为空
            d->ht[0].table[d->rehashidx] = NULL;
            // 更新 rehash 索引
            d->rehashidx++;
        }
    
        return 1;
    }