专栏首页Java技术大杂烩Redis 数据结构-字典源码分析

Redis 数据结构-字典源码分析

本文首发于个人公众号 Java 技术大杂烩,欢迎关注

前言

字典这种数据结构并不是 Redis 那几种基本数据结构,但是 hash , sets 和 sorted sets 这几种数据结构在底层都是使用字典来实现的(并不仅仅是字典),现在看下它的实现原理。

结构

Redis 字典的结构和 Java 中的 HashMap 有点类似,都是存放键值对,在底层都是使用数组加链表(称为一个哈希表)的形式来实现的,但与 HashMap 不同的是,在 Redis 中,它由两个哈希表组成,它的结构大致如下图所示:

由上图可以看到,它使用两个 hashtable ,姑且称之为 0 号哈希表和 1 号哈希表,每次只会使用 0 号哈希表,那么 1 号哈希表有什么用呢?当哈希表的键值对很多或很少的话,就需要对哈希表进行扩展或缩小,比如哈希表中数组的大小默认为 4 ,如果哈希表中键值对很多,则数组中每项的链表就会很长,而链表查找速度很很慢,不像数组那样根据索引定位,所以为了让哈希表的负载因子(load factor)维持在一个合理的范围内,就需要对哈希表进行扩展或缩小,称为 rehash。

结构定义

接下来看下上述结构图的定义,

首先看下字典结构的定义:

typedef struct dict {
    dictType *type; //字典类型
    void *privdata; //私有数据
    dictht ht[2]; // 哈希表,有两个,实现渐进式rehash
    long rehashidx; // rehash 索引,当不进行rehash的时候,值为-1
    unsigned long iterators; // 当前正在运行的迭代器的数量
} dict;

其中,dictht ht[2] 对应的是上图中的ht[0][1]

之后,看下哈希表的定义:

/*
 * 哈希表
 */
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

对应的上图中的哈希表数组,数组中的每一项是链表,链表节点使用 dictEntry 表示,接下来看下 dictEntry 的定义:

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

以上的定义就表示的字典的数据结构,上述的定义代码是在 dict.h 文件中,该文件中,除了上述代码外,还有一些其他的API定义,如迭代器等。

接下来看下字典的操作,如添加元素,删除元素,查找元素,rehash 等,这个操作代码主要是在 dict.c 文件中

字典操作

首先看下几个公共的方法;

_dictInit : 初始化哈希表
int _dictInit(dict *d, dictType *type, void *privDataPtr)
{
    // 初始化两个哈希表的各项属性值
    // 但暂时还不分配内存给哈希表数组
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type; // 设置类型
    d->privdata = privDataPtr; // 设置私有数据
    d->rehashidx = -1; // 设置 rehash的状态,表示不正在rehash
    d->iterators = 0; // 设置安全迭代器数量
    return DICT_OK;
}
_dictKeyIndex: 根据 key 来获取添加的这个键值对应该存放在哈希表中的索引。
//如果 key 已经存在于哈希表,那么返回 -1
//如果字典正在进行 rehash ,那么总是返回 1 号哈希表的索引。因为在字典进行 rehash 时,新节点总是插入到 1 号哈希表。
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    // 哈希表是否需要扩展
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    // 遍历 0 号哈希表和 1 号哈希表
    for (table = 0; table <= 1; table++) {
        // 获取哈希表中的每一项
        idx = hash & d->ht[table].sizemask;
        //获取每一项的链表
        he = d->ht[table].table[idx];
        // 遍历链表
        while(he) {
            // 如果key 存在,则放回 -1 
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        // 如果哈希表没有正在进行rehash操作,则表示只有 0 号哈希表中有数据,就不要在 1 号哈希表中进行查找
        // 否则的话,就还需要遍历 1 号哈希表进行查找
        if (!dictIsRehashing(d)) break;
    }
    // 返回索引
    return idx;
}
_dictExpandIfNeeded : 哈希表是否需要扩展
static int _dictExpandIfNeeded(dict *d)
{
    // 如果正在进行 rehash,则表示正在进行扩展,直接返回 OK
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果 0 号哈希表为空,则需要对哈希表进行初始化,初始化哈希表数组的大小为DICT_HT_INITIAL_SIZE
    // #define DICT_HT_INITIAL_SIZE 4 
    // 可以看到,哈希表数组的初始大小为 4 
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    // 以下两个条件之一为真时,对字典进行扩展
    // 1)字典已使用节点数和字典大小之间的比率接近 1:1 并且 dict_can_resize 为真
    // 2)已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
    // 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);
    }
    return DICT_OK;
}

上述代码中,如果哈希表为空,即是第一次添加元素的时候,需要初始化哈希表,哈希表的大小为 4 ,如下所示:

还有一种情况是,如果哈希表的已有的节点和哈希表的大小的比例超过阈值 dict_force_resize_ratio 即 5 的时候,需要对哈希表进行扩展,

扩展的哈希表大小为已使用节点的2倍,如果哈希表的大小为 4 ,已使用节点数量为24, 则 24/4 > 5 ,就需要对哈希表进行扩展,此时哈希表的大小为 24*2 = 48。

dictExpand : 扩展哈希表的过程
// 扩展或创建一个新的哈希表
int dictExpand(dict *d, unsigned long size)
{
    // 如正在进行 rehash,表示已经进行扩展,返回扩展失败
    // 如果扩展的大小比已有节点还要小,则扩展失败
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; /* the new hash table */
    // 新的哈希表的大小,为 2 的 size 次方
    unsigned long realsize = _dictNextPower(size);

    // 如果扩展的哈希表大小和原先的哈希表大小一样,则扩展失败
    if (realsize == d->ht[0].size) return DICT_ERR;

    n.size = realsize;
    n.sizemask = realsize-1;
    // 申请空间
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    // 如果 0 号哈希表为空,表示这是一次初始化:将新哈希表赋给 0 号哈希表。
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    // 如果 0 号哈希表非空,那么这是一次 rehash :程序将新哈希表设置为 1 号哈希表,
    // 并将字典的 rehash 标识打开,让程序可以开始对字典进行 rehash
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

rehash

接下来看下字典的 rehash,字典为什么需要 rehash,随着操作的不断执行, 哈希表保存的键值对会逐渐地增多或者减少, 如果保存的键值很多,哈希表较小,则哈希表中每一项的链表就会很长,而链表的查找速度较慢,所以为了让哈希表的负载因子(load factor)维持在一个合理的范围之内, 当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩。而在 Redis 的字典扩展或缩小的过程中,是一个渐进式的过程,为什么不是一次性进行操作,而是渐进式的方式?因为如果字典较大,在扩展的时候,需要重新申请空间,再把旧字典的值 copy 到新的字典中取,这是一个 O(n) 的操作,很费时,所有,采用的是渐进式的方式,在字典进行扩展的过程中,还可以进行其他的操作,如添加,查找等。rehash 的过程就是根据 0 号哈希表的已有节点来计算需要扩展的大小,根据该大小创建 1 号哈希表,再把 0 号哈希表的数据慢慢移动到 1 号哈希表上,rehash 指的是重新计算键的哈希值和索引值, 然后将键值对放置到 ht[1] 哈希表的指定位置上。当移到完成后,再把 1 号哈希表赋给 0 号哈希表,之后清空 1 号哈希表,为下次 rehash 做准备。

接下来从代码层面看下 rehash 的过程:

// 执行 N 步渐进式 rehash
// 返回 1 表示仍有键需要从 0 号哈希表移动到 1 号哈希表,
// 返回 0 则表示所有键都已经迁移完毕。
// 注意:rehash的时候,都是以桶(链表)为单位的,一个桶里面可能有多个节点,
int dictRehash(dict *d, int n) {

    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    // 如果rehash已经完毕,则返回0
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        // 取出hash表中的每个桶
        de = d->ht[0].table[d->rehashidx];

        // 循环把该桶中所有的键移动到新的hash表中,桶中的节点以链表的形式存放
        while(de) {
            uint64_t h;

            nextde = de->next;

            // 在新的哈希表中获取要存放元素的索引
            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; // 下一个节点
        }
        // 该桶中的所有key都转移成功后,置为null,
        d->ht[0].table[d->rehashidx] = NULL;
        // 获取下一个桶
        d->rehashidx++;
    }

    // 当0号哈希表中所有的键都移到1号表后,
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table); // 重置 0 号哈希表
        d->ht[0] = d->ht[1]; // 把 1 号哈希表的指针赋值给 0 号表
        _dictReset(&d->ht[1]); // 重置1号哈希表,为下一次rehash做准备
        d->rehashidx = -1; // rehash完成
        return 0; // rehash完成
    }

    return 1;
}
dictAdd: 向字典中添加元素
int dictAdd(dict *d, void *key, void *val)
{
    // 键添加到字典,并返回包含了这个键的新哈希节点
    dictEntry *entry = dictAddRaw(d,key,NULL);
    // 如果键存在,添加失败
    if (!entry) return DICT_ERR;
    // 如果键不存在,则设置值
    dictSetVal(d, entry, val);
    return DICT_OK;
}
//将键插入到字典中,如果键已经存在,则返回null,否则的话,以该键创建新的哈希节点,插入到字典中并返回
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;
    //进行 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 在哈希表中获取新元素存放的索引,如果元素已存在,则返回null
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    //如果正在进行rehash,则直接把新元素插入到 1 号哈希表中,否则的话,将新元素插入到 0 号哈希表中
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 分配空间
    entry = zmalloc(sizeof(*entry));
    // 把新节点插入到对应的索引中
    entry->next = ht->table[index];
    ht->table[index] = entry;
    //哈希表中已使用节点加1
    ht->used++;

    // 设置新节点的键
    dictSetKey(d, entry, key);
    // 返回新创建的节点
    return entry;
}

如下图所示:

dictDelete : 删除节点
// 删除成功,返回 OK , 如果找不到对应的键,则删除失败
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
// 查找并删除包含给定键的节点
// 参数 nofree 决定是否调用键和值的释放函数, 0 表示调用,1 表示不调用
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    // 0 号哈希表和 1 号哈希表中使用节点的数量都为0,表示哈希表为空
    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    //计算key的哈希值
    h = dictHashKey(d, key);

    //两个哈希表,表示需要在两个哈希表中查找
    for (table = 0; table <= 1; table++) {
        //计算索引值
        idx = h & d->ht[table].sizemask;
        //指向该索引上的链表
        he = d->ht[table].table[idx];
        // 当前节点的上一个节点
        prevHe = NULL;
        //遍历该链表上的所有节点
        while(he) {
             // 找到要删除的key
            if (key==he->key || dictCompareKeys(d, key, he->key)) {

                //从链表上删除该节点
                if (prevHe) // 如果要删除的节点的前一个节点不为空,表示删除节点不是第一个节点
                    prevHe->next = he->next;
                else // 如果要删除的节点是第一个节点,则直接把该节点的下一个节点设置为该链表的头节点
                    d->ht[table].table[idx] = he->next;
                //释放键和值
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                    zfree(he);
                }
                //使用节点减1
                d->ht[table].used--;
                //返回删除的节点
                return he;
            }
            // 把当前节点设置为前一个节点
            prevHe = he;
            //查找下一个节点
            he = he->next;
        }
        // 如果字典不正在进行 rehash,表示只有 0 号哈希表中有数据,不需要在 1 号哈希表中进行查找
        // 否则,如果 rehash 正在进行,则还需要在 1 号哈希表中进行查找删除
        if (!dictIsRehashing(d)) break;
    }
    return NULL; /* not found */
}

删除节点的过程如下:

if (prevHe) // 如果要删除的节点的前一个节点不为空,则删除该节点
    prevHe->next = he->next;
else // 如果要删除的节点是第一个节点,则直接把该节点的下一个节点设置为该链表的头节点
    d->ht[table].table[idx] = he->next;

前一个节点不为空:prevHe->next = he->next

要删除的是第一个节点:d->ht[table].table[idx] = he->next

dictFetchValue : 查找对应键的值,
//返回对应键的值
void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;

    he = dictFind(d,key);
    return he ? dictGetVal(he) : NULL;
}
//查找key对应的节点
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;
    //哈希表为空
    if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
    // 正在rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);

   // 计算键的哈希值
    h = dictHashKey(d, key);

    //在 0 号哈希表和 1 号哈希表中查找
    for (table = 0; table <= 1; table++) {
        // 索引值
        idx = h & d->ht[table].sizemask;
        // 索引值对应的链表
        he = d->ht[table].table[idx];
        // 遍历链表
        while(he) {
            // 找到就返回
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        // 如果正在进行rehash,1号哈希表中可能也有数据,则需要再在1号哈希表中进行查找,
        // 如果rehash完毕了,表示只有0号哈希表中有数据,就不需要在1号哈希表中查找了,直接返回null
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

命令操作字典

接下来看下 hash, sets 和 sorted sets 命令是如何操作字典的。

hash 操作字典

  1. 添加操作:
// hash 底层存放数据不仅仅是字典这种数据结构,还有压缩列表等结构
int hashTypeSet(robj *o, sds field, sds value, int flags) {
    int update = 0;

    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
      ........................

      // 如果该对象的编码方式是字典的方式,则需要在字典中添加该键值对 
    } else if (o->encoding == OBJ_ENCODING_HT) {
        dictEntry *de = dictFind(o->ptr,field);
        // 如果已存在,则更新
        if (de) {
            sdsfree(dictGetVal(de));
            if (flags & HASH_SET_TAKE_VALUE) {
                dictGetVal(de) = value;
                value = NULL;
            } else {
                dictGetVal(de) = sdsdup(value);
            }
            update = 1;
        } else {
            sds f,v;
            if (flags & HASH_SET_TAKE_FIELD) {
                f = field;
                field = NULL;
            } else {
                f = sdsdup(field);
            }
            if (flags & HASH_SET_TAKE_VALUE) {
                v = value;
                value = NULL;
            } else {
                v = sdsdup(value);
            }
            // 向字典中添加元素 
            dictAdd(o->ptr,f,v);
        }
    } 
......................
    return update;
}

查找操作:

sds hashTypeGetFromHashTable(robj *o, sds field) {
    dictEntry *de;

    // 编码格式为哈希表
    serverAssert(o->encoding == OBJ_ENCODING_HT);

    // 在哈希表中查找
    de = dictFind(o->ptr, field);
    if (de == NULL) return NULL;
    // 返回对应的值
    return dictGetVal(de);
}

删除操作:

int hashTypeDelete(robj *o, sds field) {
    int deleted = 0;

    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
     ......................
     // 编码方式为哈希表
    } else if (o->encoding == OBJ_ENCODING_HT) {
        // 从哈希表中删除元素
        if (dictDelete((dict*)o->ptr, field) == C_OK) {
            deleted = 1;

            if (htNeedsResize(o->ptr)) dictResize(o->ptr);
        }

    } else {
        serverPanic("Unknown hash encoding");
    }
    return deleted;
}

sets 操作字典

添加操作:

int setTypeAdd(robj *subject, sds value) {
    long long llval;
    // 如果编码方式为哈希表
    if (subject->encoding == OBJ_ENCODING_HT) {
        dict *ht = subject->ptr;
        // 在哈希表中添加元素
        dictEntry *de = dictAddRaw(ht,value,NULL);
        if (de) {
            dictSetKey(ht,de,sdsdup(value));
            dictSetVal(ht,de,NULL);
            return 1;
        }
    } else if (subject->encoding == OBJ_ENCODING_INTSET) {
         ....................
    } else {
        serverPanic("Unknown set encoding");
    }
    return 0;
}

删除操作:

int setTypeRemove(robj *setobj, sds value) {
    long long llval;
    // 编码方式为哈希表
    if (setobj->encoding == OBJ_ENCODING_HT) {
        // 在哈希表中删除元素
        if (dictDelete(setobj->ptr,value) == DICT_OK) {
            if (htNeedsResize(setobj->ptr)) dictResize(setobj->ptr);
            return 1;
        }
    } else if (setobj->encoding == OBJ_ENCODING_INTSET) {
       ..............
    } else {
        serverPanic("Unknown set encoding");
    }
    return 0;
}

以上就是 Redis 中字典的实现原理

本文分享自微信公众号 - Java技术大杂烩(tsmyk0715),作者:TSMYK

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ThreadLocal 源码解析

    ThreadLocal 顾名思义就是在每个线程内部都会存储只有当前线程才能访问的变量的一个副本,然后当前线程修改了该副本的值后而不会影响其他线程的值,各个变量之...

    Java技术大杂烩
  • Vue加载优化,速度提高一倍。

    之前做的一个Vue项目,流程大概是这这样的:从公众号进入,由外系统获取用户的openid等信息,然后再跳转到项目首页进行加载初始化操作。

    Java技术大杂烩
  • Redis 初探-安装与使用

    Redis是一个使用ANSI C编写的开源、支持网络、基于内存、可选持久性的键值对存储数据库。从2015年6月开始,Redis的开发由Redis Labs赞助,...

    Java技术大杂烩
  • 浅谈哈希表

    哈希表是一种根据哈希键去寻找哈希值的数据映射结构。通过该结构找到哈希键映射的位置,再根据映射的位置去寻找存放哈希值的地方。

    小蜜蜂
  • 哈希表的理论知识

    哈希表又称散列表,若要存储的元素个数为n,设置一个长度为m(m >= n)的连续内存单元,以每个元素的关键字为自变量,通过一个称为哈希的函数把关键字映射为内存单...

    晚上没宵夜
  • 朝花夕拾-哈希表(hashTable)

    所以在Aa,BB、Ab,BC时会出现碰撞。通过如下测试代码可以发现,他们的hashCode是相同的。

    皮皮熊
  • AI综述专栏| 大数据近似最近邻搜索哈希方法综述(上)(附PDF下载)

    在科学研究中,从方法论上来讲,都应先见森林,再见树木。当前,人工智能科技迅猛发展,万木争荣,更应系统梳理脉络。为此,我们特别精选国内外优秀的综述论文,开辟“综述...

    马上科普尚尚
  • LeetCode | 你不得不了解的哈希算法 !

    问大家一个问题 。如果手机上存储了 1000 个联系人 ,现在要你给小詹打个电话 ,跟他说 ,他老婆喊他回家吃饭 。你会怎么做 ?

    小小詹同学
  • 哈希算法的设计要点及应用场景

    大家好,我是多选参数的程序锅,一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇主要介绍了哈希算法相关的内容,包括什么是哈希算法、哈...

    syy
  • 哈希

    我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个...

    对弈

扫码关注云+社区

领取腾讯云代金券