• 本文对Redis源码的学习是基于5.0.2版本.

前言

  Redis实现的字典是一种key-value键值对的数据结构,如果你看过Java的HashMap这种key-value键值对数据结构的源码,那么本文对你来说难度并不大.
  本人对Redis实现的字典比较有感兴趣的是作者实现的渐进式扩容(rehash),但本文也会全面分析字典的增删改查.

Dict --- (源文件dict.h/dict.c)

Dict的结构体如下 :

# dictEntry   
# key-value 结构
typedef struct dictEntry {
    // key
    void *key;
    // value
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // next指针,指向下一个dictEntry,用来解决哈希冲突
    struct dictEntry *next;
} dictEntry;

# dictht
# 哈希表,正真来存数据的(dictEntry),默认初始化为长度4的哈希表数组
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 当前哈希表数组是多少个桶,即size个桶
    unsigned long size;
    // size-1,方便用于计算数组索引值
    unsigned long sizemask;
    // 当前哈希表数组中存放了多少个dictEntry,即存储的元素个数
    unsigned long used;
} dictht;

# dict 
# 通过dict来操作dictht
typedef struct dict {
    // 该属性用于多态字典 : 类型特定函数
    dictType *type;
    // 该属性用于多态字典 : 私有数据
    void *privdata;
    // 2个dictht哈希表数组
    dictht ht[2];
    // rehash时该值起到作用,表示从哪个索引值开始rehash
    // rehashidx == -1 时表示当前不是处于rehash状态
    long rehashidx;
    // 当前运行的迭代器数,等于0时表示支持rehash
    unsigned long iterators;
} dict;

# dictType
# dict的多态调用函数
typedef struct dictType {
    // 用于计算哈希值的函数
    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;

• dictType : 每个dictType保存了用于操作特定类型键值对的函数,Redis会为用途不同的字典设置不同的类型特定函数.
• privdata : 保存了需要传给那些类型特定函数的可选参数
• ht[2] : 包含两个数组,即数组中2个dictht哈希表数组,一般情况下,只使用ht[0]哈希表,ht[1]在rehash的情况下才会使用.
• 【PS : 什么是rehash : 哈希表保存的键值对逐渐地增多或者减少,为了让哈希表的负载因子维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者太少时,需要对哈希表进行扩展或者收缩,即迁移数据】

dict 结构体如下图 :

创建 --- dictCreate()

dictCreate()

dictCreate() : 初始化dict

# dictCreate()
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    1. // 申请内存
    dict *d = zmalloc(sizeof(*d));
    2. // 最终调用 _dictInit()
    _dictInit(d,type,privDataPtr);
    return d;
}

_dictInit()

# _dictInit
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    // 初始化两个 dictht
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    // 默认为 -1
    d->rehashidx = -1;
    // 默认为 0
    d->iterators = 0;
    return DICT_OK;
}

# _dictReset
static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

添加操作 --- dictAdd()

# dictAdd()
int dictAdd(dict *d, void *key, void *val)
{
    // 调用dictAddRaw(),该函数下面具体分析
    // 该函数包揽了很多工作 : 
    // 检查 初始化、扩容、是否相同的key值dictEntry
    // 创建dictEntry、保存key等
    // 最终会返回一个dictEntry
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    // 保存value
    dictSetVal(d, entry, val);
    return DICT_OK;
}

实则很多工作被dictAddRaw()包揽了,重点看看这个函数.

是否需要迁移数据、扩容、保存key --- dictAddRaw()

这个函数我分为三大部分 :

• ①检查当前字典是否需要迁移数据 : dictRehashStep()
• ②迁移完成后则执行获取index,并且检查当前字典是否需要初始化或者扩容、是否有相同的key值dictEntry : dictKeyIndex()
• ③如果能走到这一步,说明没有相同的key值dictEntry,需要创建dictEntry并且保存key值后插入到对应的index位置中(头部插入法)

# dictAddRaw()
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;
    
    # 检查当前字典是否需要迁移数据
    
    1.// 如果目前处于rehash状态, 执行 _dictRehashStep(),该函数下面具体分析
    // _dictRehashStep() : 判断是否需要迁移数据
    if (dictIsRehashing(d)) _dictRehashStep(d);

    # 迁移完成后则执行获取index,并且检查当前字典是否需要初始化或者扩容
    
    2. // 否则目前并非处于rehash状态 或者 已完成迁移动作
    // 获取index索引,_dictKeyIndex(),该函数下面具体分析
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    # 如果能走到这一步,说明没有相同的key值dictEntry,需要创建dictEntry并且保存key值后插入到对应的index位置中(头部插入法)
    
    3. // 如果当前处于rehash状态,则使用ht[1]
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    4. 申请内存
    entry = zmalloc(sizeof(*entry));
    5. 头部插入法
    entry->next = ht->table[index];
    ht->table[index] = entry;
    6. 存储的个数+1
    ht->used++;
    7. // 保存key指
    dictSetKey(d, entry, key);
    return entry;
    
}

三大步骤:

• ①判断是否执行迁移数据 : 如果当前处于rehash状态,则最终调用dictRehash()来迁移数据,每次最大迁移10个桶的数据,无论桶中有没有数据;
• ②获取index索引 : 根据_dictKeyIndex()来获取;
• ③将dictEntry插入到字典中 :
  • 如果当前处于rehash状态,则使用ht[1];
  • 头部插入法
  • 保存dictEntry的key值.

dictRehashStep() --- 是否执行迁移数据

• 该函数会判断是否需要迁移数据,只有在哈希表没有绑定安全迭代器的情况下才执行,当我们的迭代器处于重新哈希的状态时,我们不进行迁移数据的操作,否则某些元素可能会丢失或重复.
• 此函数由字典中的常用查找或更新操作调用,以便哈希表在活动使用时自动从h1迁移到h2.

# dictRehashStep()
static void _dictRehashStep(dict *d) {
    // 迭代器为0,可以迁移数据
    if (d->iterators == 0) dictRehash(d,1);
}

dictRehash() --- 迁移数据

# dictRehash()
int dictRehash(dict *d, int n) {
    // 最大迁移10个桶的数据,无论桶中有没有数据
    int empty_visits = n*10;
    1. // 再次判断一下当前是否处于rehash状态
    if (!dictIsRehashing(d)) return 0;

    # 迁移数据
    2. // 迁移数据
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        2.1 // 根据rehashidx获取需要迁移的桶
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            2.2 // 已完成10个桶数据的迁移
            if (--empty_visits == 0) return 1;
        }
        2.3 // 开始迁移索引值为rehashidx的桶数据
        de = d->ht[0].table[d->rehashidx];
        
        while(de) {
            uint64_t h;
            nextde = de->next;
            2.3.1 // 重新计算索引值
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            2.3.2 // 头指针插入
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            2.3.3 // 保存used
            d->ht[0].used--;
            d->ht[1].used++;
            2.3.4 // 继续操作下一dictEntry结点
            de = nextde;
        }
        2.4 // 索引值为rehashidx的桶数据迁移完成
        d->ht[0].table[d->rehashidx] = NULL;
        2.5 // 继续推进迁移
        d->rehashidx++;
    }

    3. // 检查是否全部迁移完成
    if (d->ht[0].used == 0) {
        3.1 // 回收ht[0]
        zfree(d->ht[0].table);
        3.2 // ht[0] 指向 ht[1]
        d->ht[0] = d->ht[1];
        3.3 // 重新初始化h[1]
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    return 1;
}

_dictKeyIndex() --- 获取index索引值

  dictKeyIndex() : 该函数的最终目的是计算索引值,即根据key、sizemask计算索引值.
  首先检查当前字典是否需要初始化或者扩容,最后根据key判断当前字典是否存在相同的key值dictEntry,如果出现,则保留原先的,新插入的value并没有进行替换旧的value.否则没有出现,返回idx.

• ①检查是否需要初始化或者扩容 : dictExpandIfNeeded(),具体下面分析.
• ②获取index :
  • 可能此时处于非rehash状态,那么最终返回的是第一张table的idx;并且需要检查是否存在相同的key值dictEntry,如果不存在,那么直接计算获取第一张table的idx;
  • 可能此时处于rehash状态,那么如果第一张table对应的idx桶存在数据,需要检查是否存在相同的key值dictEntry;如果不存在,那么直接计算获取第二张table的idx;
  • 以上两种情况如果存在相同的key值dictEntry,则保留旧的value,新的value并没有覆盖旧的value.

# _dictKeyIndex()
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    1. // 判断是否需要初始化或者扩容,该函数下面具体分析
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    2. // 检查是否有相同的key值dictEntry,如果有则无需再申请dictEntry的内存来保存key，操作同一个dictEntry即可
    // 为什么2个哈希表都要遍历 : 
    ① // 可能此时处于非rehash状态 :
    // 那么直接 操作第一张table,对应的第3步骤直接bread;
    ② // 可能此时处于rehash状态 :
    // 那么如果此时第一张table对应的idx桶存在数据,需要检查是否存在相同的key值dictEntry
    // 如果不存在,那么计算获取第二张table的idx
    for (table = 0; table <= 1; table++) {
        2.1 // 计算索引值
        idx = hash & d->ht[table].sizemask;
        2.2 // 开始判断是否存在相同的key值dictEntry
        he = d->ht[table].table[idx];
        while(he) {
            2.2.1 // 判断是否相同key
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                // 保存相同key的dictEntry的指针
                if (existing) *existing = he;
                return -1;
            }
            2.2.2 // 继续向下一指针查找
            he = he->next;
        }
        3.  // 如果当前不处于rehash状态,则第二张table无需查找了,直接操作第一张table
        if (!dictIsRehashing(d)) break;
    }
    4. // 返回idx
    return idx;
}

_dictExpandIfNeeded() --- 是否执行需要初始化或者扩容

dictExpandIfNeeded() : 是否执行初始化或扩容

• ①第一次初始化 : dictExpand(d, ,DICT_HT_INITIAL_SIZE),第一次初始化长度为4;
• ②否则不是第一次初始化,那么需要检查是否需要扩容 :
  • 如果存储的元素个数大于等于table数组的size,即负载因子大于等于1时,就需要继续判断是否需要扩容了;
  • 如果此时并不是处于正在执行持久化命令(BGSAVE、BGREWRITEAOF),即dict_can_resize == 0,那么继续判断下面的条件,否则不允许扩容;
  • 如果存储的元素个数 除以 table数组的size 大于 dict_force_resize_ratio(负载因子为5) , 那么执行dictExpand()扩容;
  • 当大于 dict_force_resize_ratio触发执行扩容时,并不是扩容为 当前存储的元素个数的2倍,而是会根据这个值继续计算,具体看看下面的_dictNextPower()

static int _dictExpandIfNeeded(dict *d)
{
    // 当前处于rehash状态
    if (dictIsRehashing(d)) return DICT_OK;

    1. // 第一次初始化,需要执行dictExpand()来初始化,DICT_HT_INITIAL_SIZE(该值为4)
    if (d->ht[0].size == 0) return dictExpand(d, ,DICT_HT_INITIAL_SIZE);

    2. // 如果存储的元素个数大于等于table数组的size,那么就需要判断是否需要扩容
    // dict_can_resize : 是否扩容,默认为1,处于正在执行持久化命令(BGSAVE、BGREWRITEAOF),该值为0.
    // d->ht[0].used/d->ht[0].size : 如果 存储的元素个数 除以 table数组的size 大于 dict_force_resize_ratio(该值为5) , 那么执行dictExpand()扩容
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        2.1 // 并不是扩容为 当前存储的元素个数的2倍,而是会根据这个值继续计算,具体看看下面的_dictNextPower()
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

dictExpand() --- 执行扩容操作

# dictExpand()
# 参数size : 新的table长度扩容为 最少size
int dictExpand(dict *d, unsigned long size)
{
    // 如果当前是处于rehash状态 或者 字典中存储元素个数 大于 扩容长度
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    // 扩容后新的哈希表
    dictht n;
    // 重新计算扩容长度,_dictNextPower()保证扩容的长度总是2的次幂且大于等于size
    unsigned long realsize = _dictNextPower(size);

    // 重新扩容到相同的表大小是没有用的
    if (realsize == d->ht[0].size) return DICT_ERR;

    // 以下都是设置ht[0]、ht[1]属性
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

_dictNextPower() --- 保证了扩容长度总是2的次幂

dictNextPower() : 该函数保证了扩容长度总是2的次幂,并且是大于等于size.

# _dictNextPower()
static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX + 1LU;
    while(1) {
        // 保证大于等于size
        if (i >= size)
            return i;
        // 保证了总是2的次幂
        i *= 2;
    }
}

小结

• dictAdd() 的添加操作核心是dictAddRaw(),dictAddRaw()包揽了 渐进式迁移数据、初始化或者扩容、最终是否保存key的操作.
• 渐进式迁移数据 : 如果当前处于rehash状态,并且非迭代状态,那么当前需要先迁移h[0]中10个桶数据到h[1] ;
• 初始化或者扩容 : 如果当前字典并非处于rehash状态,并且 负载因子大于等于1,那么如果满足 负载因子大于5 这个条件,则执行扩容,扩容的长度为最少 字典存储的元素个数 * 2 , 举个例子 : 如果当前字典存储的个数为 17 触发扩容 , 那么 17 * 2 = 34 , 最终扩容的哈希表数组长度则为 64 , 具体可以结合_dictNextPower() ;
• 是否保存key : 保存key的前提是当前字典中并没有相同的key值dictEntry,那么则需要创建新的dictEntry来保存key,否则保留原先的dictEntry,即新插入的value并没有进行替换旧的value.

创建或者查找 --- dictAddOrFind()

还是调用dictAddRaw(),那么跟dictAdd()有什么区别 :

• dictAdd() : 传送的&existing是一个NULL,即出现相同key的时候是不做任何操作的.
• dictAddOrFind() : 传送的&existing是一个dictEntry指针,即如果出现相同的key值dictEntry,会把existing指向该dictEntry,我们根据拿到的这个指针来做相对应的操作.

dictEntry *dictAddOrFind(dict *d, void *key) {
    dictEntry *entry, *existing;
    entry = dictAddRaw(d,key,&existing);
    return entry ? entry : existing;
}

创建 --- dictReplace()

还是调用dictAddRaw(),那么跟dictAdd()有什么区别 :

• dictAdd() : 传送的&existing是一个NULL,即出现相同key的时候是不做任何操作的.
• dictReplace() : 传送的&existing是一个dictEntry指针,即如果出现相同的key值dictEntry,会把existing指向该dictEntry,我们根据拿到的这个指针来覆盖掉旧的value值.

int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, *existing, auxentry;

    // 返回entry则表示没有相同key值dictEntry,创建成功
    entry = dictAddRaw(d,key,&existing);
    if (entry) {
        // 创建成功,设置value值
        dictSetVal(d, entry, val);
        // 返回1表示插入
        return 1;
    }
    
    // 出现相同key值dictEntry,覆盖掉旧的value
    auxentry = *existing;
    // 覆盖掉旧的value
    dictSetVal(d, existing, val);
    // 回收旧的value
    dictFreeVal(d, &auxentry);
    // 返回0表示覆盖
    return 0;
}

删除操作 --- dictDelete()、dictUnlink()

# dictDelete() : 回收被删除的dictEntry
int dictDelete(dict *ht, const void *key) {
    // 最终调用 dictGenericDelete()
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}

# dictUnlink() : 不回收被删除的dictEntry,并返回该dictEnty
dictEntry *dictUnlink(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,1);
}

# dictGenericDelete()
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

    // 如果处于rehash状态,先迁移10个桶数据
    if (dictIsRehashing(d)) _dictRehashStep(d);
    1. // 计算hash值
    h = dictHashKey(d, key);

    2. // 开始查找是否存在删除的key值dictEntry
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        2.1 // 记录上一个dictEntry结点
        prevHe = NULL;
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                2.2 // 出现相同的key值dictEntry
                if (prevHe)
                    2.2.1 // 上一节点.next 与 下一节点接上
                    prevHe->next = he->next;
                else
                    2.2.2 // 删除的是头结点
                    d->ht[table].table[idx] = he->next;
                2.3 // 是否执行回收内存
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                    zfree(he);
                }
                d->ht[table].used--;
                return he;
            }
            2.5 // 继续向下一结点查找
            prevHe = he;
            he = he->next;
        }
        // 如果当前非rehash状态,操作第一张table就好
        // 否则第二张table也需要查找删除
        if (!dictIsRehashing(d)) break;
    }
    // 没有查找到对应的key值dictEntry
    return NULL;
}

回收操作 --- dictFreeUnlinkedEntry

# dictFreeUnlinkedEntry()
void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {
    if (he == NULL) return;
    dictFreeKey(d, he);
    dictFreeVal(d, he);
    zfree(he);
}

清空字典并回收内存 --- dictRelease()

# dictRelease()
void dictRelease(dict *d)
{
    _dictClear(d,&d->ht[0],NULL);
    _dictClear(d,&d->ht[1],NULL);
    zfree(d);
}

根据key查找操作dictEntry --- dictFind()

# dictFind()
# 根据key查找dictEntry
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;
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            // 存在需要查找的dictEntry
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

根据key查找操作value --- dictFetchValue()

# dictFetchValue()
void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;
    // 根据key值查找dictEntry
    he = dictFind(d,key);
    // 返回value值
    return he ? dictGetVal(he) : NULL;
}

迭代器相关 --- dictIterator

  如果safe设置为1,这是一个安全的迭代器,也就是说,即使在迭代时,也可以对字典调用dictAdd()、dictFind和其他函数.否则它是一个不安全的迭代器,迭代时只能调用dictNext().

typedef struct dictIterator {
    // 字典
    dict *d;
    // 哈希表数组索引值
    long index;
    // 哪张表,是否为安全迭代器
    int table, safe;
    // 迭代的数据
    dictEntry *entry, *nextEntry;
    // 非安全迭代器
    long long fingerprint;
} dictIterator;

初始化字典迭代器 --- dictGetIterator()

# dictGetIterator()
dictIterator *dictGetIterator(dict *d)
{
    dictIterator *iter = zmalloc(sizeof(*iter));
    
    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    // 不是安全的迭代器
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

初始化字典为安全迭代器 --- dictGetSafeIterator()

# dictGetSafeIterator()
dictIterator *dictGetSafeIterator(dict *d) {
    dictIterator *i = dictGetIterator(d);
    // 安全迭代器
    i->safe = 1;
    return i;
}

迭代 --- dictNext()

# dictNext()
# 安全下可调用
# 不安全下必须调用
dictEntry *dictNext(dictIterator *iter)
{
    while (1) {
        // 使用iter->entry来存储迭代到的数据
        if (iter->entry == NULL) {
            // 根据iter->table迭代哪张table
            dictht *ht = &iter->d->ht[iter->table];
            if (iter->index == -1 && iter->table == 0) {
                // 安全迭代器
                if (iter->safe)
                    iter->d->iterators++;
                else
                // 非安全迭代器
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            iter->index++;
            // 迭代第二张table
            if (iter->index >= (long) ht->size) {
                if (dictIsRehashing(iter->d) && iter->table == 0) {
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                } else {
                    break;
                }
            }
            // 把迭代的数据接上iter->entry
            iter->entry = ht->table[iter->index];
        } else {
        // 完成迭代数据
            iter->entry = iter->nextEntry;
        }
        // 最终把迭代的数据iter->entry接上iter->nextEntry
        if (iter->entry) {
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }
    return NULL;
}

释放迭代 --- dictReleaseIterator()

# dictReleaseIterator()
void dictReleaseIterator(dictIterator *iter)
{
    if (!(iter->index == -1 && iter->table == 0)) {
        if (iter->safe)
            iter->d->iterators--;
        else
            assert(iter->fingerprint == dictFingerprint(iter->d));
    }
    zfree(iter);
}

结束语

• 渐进式rehash : 当需要扩容的时候,Redis并不是直接扩容,而是采用渐进式扩容,即每个字典的删除、查找、更新和添加等操作会进行迁移10个桶数据,这样就不会导致数据较大的时候,阻塞更多的请求,将rehash操作对所需的工作均摊到对字典的每个删除、查找、更新和添加操作上.
• 应用场景 : 字典被广泛用于实现Redis的各自功能,其中包括数据库和哈希键.
• Redis中的字典使用哈希表作为底层实现,每个字典带有两个哈希表,一个平时使用,另一个仅在进行rehash的使用.
• Java的HashMap、ConcurrentHashp都是键值对数据结构的实现,都有很大的相似之处,有兴趣的可以结合这些文章一起看看.
• 原创不易
• 希望看完这篇文章的你有所收获!

相关参考资料

• Redis设计与实现【书籍】