Redis 数据结构 哈希表(hashtable/dict/map)

哈希表是一种非常关键的数据结构，在计算机系统中发挥着重要作用。
它的底层是数组+链表，通过哈希计算，能以 O(1) 的复杂度快速根据key查询到数据。

(1) 数据结构-哈希表

假设让我们自己实现一个哈希表，我们要考虑哪些方面？

1. 哈希表提供的功能
2. 哈希表操作的时间复杂度为O(1)
3. 哈希表的容量与扩容

(1.1) 哈希表的常用方法

新建哈希表、新增数据、修改数据、删除数据、查询数据

(1.2) 哈希函数-优化时间复杂度的利器

要想使时间复杂度为O(1)，要通过高效的定位方法，比如hash函数

但是hash函数有个问题，可能会哈希冲突，冲突后有多种方法 链地址法、 开放定位法、 再哈希法，这里我们使用链地址法实现。

/* 哈希函数 */
int hash(Object key) {
    int h;
    // h = key.hashCode() 为第一步 取hashCode值
    // h ^ (h >>> 16)  为第二步 高位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

链式哈希的链不能太长，否则会降低 哈希表性能。
链表哈希的链表太长时可以转换为红黑树提高查询性能。

(1.3) 哈希表容量与扩容

这里我们在创建哈希表的时候支持指定容量
扩容时容量是原来的2倍

public void resize(){

}

如果容量特别大，内存不够怎么办？

(2) Redis里的哈希表

对于 Redis 键值数据库来说，哈希表既是键值对中的一种值类型，同时，Redis 也使用一个全局 哈希表来保存所有的键值对，从而既满足应用存取 Hash 结构数据需求，又能提供快速查询功能。

在实际应用 哈希表时，当数据量不断增加，它的性能就经常会受到哈希冲突和 rehash 开销的影响。

针对哈希冲突，Redis 采用了链式哈希，在不扩容哈希表的前提下，将具有相同哈希值的数据链接起来，以便这些数据在表中仍然可以被查询到；
对于 rehash 开销，Redis 实现了渐进式 rehash 设计，进而缓解了 rehash 操作带来的额外开销对系统的性能影响。

dict.h 文件定义了 哈希表的结构、哈希项，以及 哈希表的各种操作函数，
dict.c 文件包含了 哈希表各种操作的具体实现代码。

源码 https://github.com/redis/redis/blob/6.0/src/dict.h
https://github.com/redis/redis/blob/6.0/src/dict.c

(2.1) 哈希表结构定义

/* 
 * 这是哈希表结构。
 * 每个字典都有两个这样的字典，因为我们实现了增量重新哈希，从旧表到新表。 
 */
typedef struct dictht {
    dictEntry **table;  // 哈希节点数组  一维数组的指针
    unsigned long size;  // 哈希表大小
    unsigned long sizemask;  // 哈希表大小掩码，用于计算索引值，等于 size - 1
    unsigned long used;  // 哈希表已使用节点个数
} dictht;

/*
 * 哈希表节点
 */
typedef struct dictEntry {
    void *key; // key的指针
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;  // value  联合结构体(不同场景使用不同大小，省内存)
    struct dictEntry *next; // 链表的下一个节点的指针
} dictEntry;

可以看到 哈希表dictht里定义了 二维数组()、哈希表大小、
哈希节点里定义了 键(key)、值(v)、链表的下一个节点(next)，其中值(v)是一个联合体，联合体中包含了指向实际值的指针 *val，还包含了无符号的 64 位整数、有符号的 64 位整数，以及 double 类的值。

为什么要使用联合体呢？
这种实现方法是一种节省内存的小技巧，因为当值为整数或双精度浮点数时，由于其本身就是64位，就可以不用指针指向了，而是可以直接存在键值对的结构体中，这样就避免了再用一个指针，从而节省了内存空间。

(2.2) 哈希表提供的功能

操作	函数	算法复杂度
创建一个新字典	dictCreate	O(1)
添加新键值对到字典	dictAdd	O(1)
添加或更新给定键的值	dictReplace	O(1)
在字典中查找给定键所在的节点	dictFind	O(1)
在字典中查找给定键的值	dictFetchValue	O(1)
从字典中随机返回一个节点	dictGetRandomKey	O(1)
根据给定键，删除字典中的键值对	dictDelete	O(1)
清空并释放字典	dictRelease	O(N)
清空并重置（但不释放）字典	dictEmpty	O(N)
缩小字典	dictResize	O(N)
扩大字典	dictExpand	O(N)
对字典进行给定步数的 rehash	dictRehash	O(N)
在给定毫秒内，对字典进行rehash	dictRehashMilliseconds	O(N)

(2.2.1) 创建一个哈希表

/* 创建一个新的哈希表 */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    // 分配内存
    dict *d = zmalloc(sizeof(*d));
    // 初始化
    _dictInit(d,type,privDataPtr);
    return d;
}

/* 初始化哈希表 */
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    _dictReset(&d->ht[0]); // 重置ht[0]
    _dictReset(&d->ht[1]); // 重置ht[1]
    d->type = type; // 设置哈希表类型
    d->privdata = privDataPtr; // 
    d->rehashidx = -1; // 设置成-1 代表没有进行rehash
    d->iterators = 0; // 
    return DICT_OK;
}

/* 重置已经初始化的哈希表
 * NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{
    ht->table = NULL; // 哈希表的数组置为null
    ht->size = 0; // 哈希表长度设置为0
    ht->sizemask = 0; // 掩码设置为0
    ht->used = 0; // 已使用空间设置为0
}

(2.2.2) 哈希表添加元素

// file: dict.c

/* 
 * 往哈希表添加一个元素
 * 
 * @param *d
 * @param *key
 * @param *val
 */
int dictAdd(dict *d, void *key, void *val)
{
    // 创建哈希节点 并设置key  (这个时候没有往哈希表设置val)
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    // 哈希表设置val
    dictSetVal(d, entry, val);
    return DICT_OK;
}

/* 
 *  低级添加或查找：
 *  此函数添加条目但不是设置值，而是将 dictEntry 结构返回给用户，这将确保按照他的意愿填充值字段。
 *
 *  这个函数也是直接暴露给用户API调用的，主要是为了在hash值里面存储非指针，例如：
 *
 *    entry = dictAddRaw(dict,mykey,NULL);
 *    if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
 *
 *  返回值：
 *    如果键已经存在，则返回 NULL，如果 existing 不为 NULL，则“*existing”将填充现有条目。
 *    如果添加了键，则返回哈希条目以供调用者操作。
 */
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    // 如果正在rehash，进行rehash   这里只迁移一个桶，几乎对性能无影响
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 获取元素下标  如果元素已经存在返回-1 
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* 分配内存并存储新条目。
     * 在顶部插入元素，假设在数据库系统中，最近添加的条目更有可能被更频繁地访问。*/

    // 如果在进行rehash，往ht[1]里添加元素 
    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++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

// file:  dict.h

/* 设置key */
#define dictSetKey(d, entry, _key_) do { \
    if ((d)->type->keyDup) \
        (entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
    else \
        (entry)->key = (_key_); \
} while(0)

// file:  dict.h

/* 设置val */
#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \
        (entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
    else \
        (entry)->v.val = (_val_); \
} while(0)

(2.2.3) 哈希表更新元素

/*
 * 添加或覆盖：
 *  添加一个元素，如果键已经存在则丢弃旧值。
 *  如果该键是从头开始添加的，则返回 1，
 *  如果已经存在具有该键的元素，则返回 0，并且 dictReplace() 刚刚执行了值更新操作。
 */
int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, *existing, auxentry;

    // 添加条目
    entry = dictAddRaw(d,key,&existing);
    if (entry) {
        // 设置值
        dictSetVal(d, entry, val);
        return 1;
    }

    /* 设置新值并释放旧值。 
     * 请注意，按此顺序执行此操作很重要，因为值可能与前一个值完全相同。 
     * 在这种情况下，想想引用计数，你想要递增（设置），然后递减（自由），而不是相反。
     */
    auxentry = *existing;
    // 覆盖值
    dictSetVal(d, existing, val);
    // 释放原来的
    dictFreeVal(d, &auxentry);
    return 0;
}

(2.2.4) 哈希表查找元素

/*
 * 
 * @param *d
 * @param *key
 */
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    // 字典是空的，字典里两个哈希表都是空的 
    if (dictSize(d) == 0) return NULL; /* dict is empty */
    // 哈希表正在rehash，执行rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // 计算key的hash
    h = dictHashKey(d, key);
    // 有2个哈希表 ht[0] ht[1]，有可能正在rehash，所以都要查，对应代码是 table=0 table<=1 
    for (table = 0; table <= 1; table++) {
        // 获取数组索引下标
        idx = h & d->ht[table].sizemask;
        // 桶/链表头结点
        he = d->ht[table].table[idx];
        // 遍历链表
        while(he) {
            // key相同 或 key对比相等
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he; // 返回对应节点
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

(2.2.5) 哈希表删除元素

/* 
 * 删除一个元素
 * 成功时返回 DICT_OK，如果找不到该元素则返回 DICT_ERR。 
 * 
 * @param *ht
 * @param *key
 */
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}

/*
 * 搜索并删除元素。
 * 这是 dictDelete() 和 dictUnlink()的辅助函数，请检查这些函数的顶部注释。
 * 
 * @param *d
 * @param *key 
 * @param nofree 
 */
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    // ht[0] ht[1] 已使用大小为0，返回null
    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

    // 如果正在rehash，执行rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // 获取hash值
    h = dictHashKey(d, key);
    // ht[0] ht[1] 都会查，所以 table=0 table<=1 
    for (table = 0; table <= 1; table++) {
        // 获取下标
        idx = h & d->ht[table].sizemask;
        // 获取桶
        he = d->ht[table].table[idx];
        prevHe = NULL;
        // 遍历链表
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                /* Unlink the element from the list */
                if (prevHe)
                    prevHe->next = he->next; // 移除链表里的当前节点
                else
                    d->ht[table].table[idx] = he->next; // 设置next节点为头结点，next有可能是null
                if (!nofree) {
                    // 释放key
                    dictFreeKey(d, he);
                    // 释放val
                    dictFreeVal(d, he);
                    // 释放entry
                    zfree(he);
                }
                // 更新使用元素个数
                d->ht[table].used--;
                return he;
            }
            // 更新前驱节点
            prevHe = he;
            // 处理下一个节点
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }

    // 没有找到key
    return NULL;
}

(2.2.5) 查找key的下标

/* Returns the index of a free slot that can be populated with
 * a hash entry for the given 'key'.
 * If the key already exists, -1 is returned
 * and the optional output parameter may be filled.
 *
 * Note that if we are in the process of rehashing the hash table, the
 * index is always returned in the context of the second (new) hash table. 
 *
 * @param *d 哈希表
 * @param *key key的指针
 * @param hash key的哈希值
 * @param **existing 已存在的哈希节点指针
 */
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    // 如果哈希表正在扩容返回 DICT_ERR 返回
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    // 遍历2个哈希表     
    for (table = 0; table <= 1; table++) {
        // 获取key的数组下标
        idx = hash & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        // 链表节点
        he = d->ht[table].table[idx];
        // 遍历链表
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                // key已存在，existing的指针指向哈希节点he
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

(2.3) 哈希表扩容

哈希表扩容是指 rehash 操作，其实就是指扩大 哈希表空间。

Redis rehash流程

1. Redis里保存了两个 Hash表 ht[0]和 ht[1]，用于 rehash 时交替保存数据；
2. 在正常服务请求阶段，所有的键值对写入哈希表 ht[0]；
3. 当进行 rehash 时，键值对被迁移到哈希表 ht[1]中；
4. 当迁移完成后，ht[0]的空间会被释放，并把 ht[1]的地址赋值给 ht[0]，ht[1]的表大小设置为 0

这样一来，又回到了正常服务请求的阶段，ht[0]接收和服务请求，ht[1]作为下一次 rehash 时的迁移表。

typedef struct dict {
    dictType *type; // 类型
    void *privdata; //
    dictht ht[2]; // 2个哈希表
    long rehashidx; // rehashidx == -1 则rehashing没有进行  
    unsigned long iterators; // 当前正在运行的迭代器数
} dict;

在rehashing时，rehashidx对应要操作的 ht[0].table[rehashidx] 的桶

(3) 渐进式rehash

rehash的整体流程

(3.1) rehash的触发条件-什么时候发生rehash

1. 在哈希表为空时，调用_dictExpandIfNeeded会触发哈希表初始化，默认大小为4。

2. 在哈希表不为空时，触发rehash需要同时满足2个条件:

• 已使用桶数量:哈希表桶容量 达到了 1:1 的比例 (ht[0].used > ht[0].size)
• 允许调整哈希表的大小(dict_can_resize=1) 或者 元素/桶 > 5 (dict_force_resize_ratio>5)

具体代码如下:

// file: dict.c 

/* 
 * 如果需要扩展哈希表
 *
 * @param *d
 */
static int _dictExpandIfNeeded(dict *d)
{
    // 增量rehash正在进行中，返回   通过 rehashidx != -1 判断
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果哈希表为空，则将其扩展到初始大小。 初始大小默认为4 
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* 
     * 如果 已使用桶数量:哈希表桶容量 达到了 1:1 的比例，
     * 并且我们被允许调整哈希表的大小(全局设置) 或者 应该避免它但是元素/桶之间的比例超过了“安全”阈值 5 ，
     * 我们调整大小使桶的数量为原来2倍。
     * 
     * If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))  // dict_force_resize_ratio 默认为5 
    {
        // 扩容
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

dict_can_resize 变量值默认是1，可以在 dictEnableResize、 dictDisableResize 函数中设置

// file: dict.c 

/* 
 * 使用 dictEnableResize() / dictDisableResize() 我们可以根据需要启用/禁用哈希表的大小调整。 
 * 这对 Redis 来说非常重要，因为我们使用写时复制，并且不想在有子进程正在执行保存操作时移动太多内存。
 *
 * 请注意，即使将 dict_can_resize 设置为 0，也不会阻止所有调整大小：
 *   如果元素数量与桶数之间的比率 > dict_force_resize_ratio，则哈希表仍然允许增长。
 */
static int dict_can_resize = 1;

void dictEnableResize(void) {
    dict_can_resize = 1;
}

void dictDisableResize(void) {
    dict_can_resize = 0;
}

dict_force_resize_ratio 值在 dict.c 文件中定义，默认是5

(3.1.1) 在哪些函数里调用了_dictExpandIfNeeded

_dictExpandIfNeeded 是被 _dictKeyIndex 函数调用的
_dictKeyIndex 函数又会被 dictAddRaw 函数调用
dictAddRaw 会被 dictAdd dictRelace dictAddorFind sentinelLeaderIncr setTypeAdd zunionInterGenericCommand 函数调用

当我们往 Redis 中写入新的键值对或是修改键值对时，Redis 都会判断下是否需要进行 rehash。
这里你可以参考下面给出的示意图，其中就展示了 _dictExpandIfNeeded 被调用的关系。

(3.2) 渐进式rehash如何执行？

为什么要实现渐进式rehash？

因为哈希表在执行rehash时，由于哈希表扩容，key对应的位置会改变，很多key就需要从原来的位置复制到新的位置。
而在键复制时，由于Redis主线程无法执行其他请求，会阻塞主线程，如果要复制的键特别多，Redis在执行哈希表扩容时，此时Redis Server对外是不可用的，这个是我们不能接受的。

为了避免Redis Server在哈希表扩容时不可用，提出了渐进式 rehash 的方法。
相当于把一次要干的很多事情分成多次要做的小事情。 把一次要复制的100万个key 转换为 10万次每次复制10个key，这样既不影响其他请求，也把哈希表扩容了。

渐进式rehash在代码层面是如何实现的呢？
有两个关键函数：dictRehash 和 _dictRehashStep。

/* 
 * 执行N步增量rehashing。 
 * 如果仍有键从旧哈希表移动到新哈希表，则返回 1，否则返回 0。
 *
 * 请注意，重新散列步骤包括将一个桶(在使用链表时可能有不止一个键)从旧哈希表移动到新哈希表，
 * 但是由于哈希表的一部分可能由空白组成，因此不能保证 这个函数甚至会重新散列一个桶，
 * 因为它总共最多访问 N*10 个空桶，避免它所做的工作量将不受限制，并且该函数可能会阻塞很长时间。
 *
 * @param *d
 * @param n
 */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; // 最多访问10倍的空桶 一个桶对应一个数组下标
    // 如果哈希表没有进行rehashing 返回0
    if (!dictIsRehashing(d)) return 0;
    
    // 循环
    // n>0 并且 哈希表里已使用元素 > 0 时，进行
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        // 避免ht[0]数组下标越界 
        assert(d->ht[0].size > (unsigned long)d->rehashidx);

        // 哈希表ht[0]对应数组下标的元素为null 也就是 桶对应的元素为null
        while(d->ht[0].table[d->rehashidx] == NULL) {
            // 全局rehashidx+1  这里的rehashidx 就是要操作的 ht[0].table的下标对应的桶
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        // 获取ht[0].table[rehashidx] 对应的桶 也就是链表(头)节点
        // 备注 de是一个指针
        de = d->ht[0].table[d->rehashidx];

        // 遍历链表  将这个桶中的所有键从旧的ht[0] 移到新的ht[1] 
        // de是链表头节点
        while(de) { // 不为空
            uint64_t h;
            
            nextde = de->next;  // 后继节点

            // 获取key在新ht[1]的下标
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            // 尾插法
            // 插入到 原来链表节点(可能为空)的前面
            // de->next 是一个指针，操作会比较快
            de->next = d->ht[1].table[h];
            // 更新桶里链表的头节点
            // 备注: de是一个指针，所以操作会比较快，不会太耗时
            d->ht[1].table[h] = de;

            d->ht[0].used--; // 更新ht[0]已使用个数
            d->ht[1].used++; // 更新ht[1]已使用个数

            de = nextde; // 指向下一个链表节点
        }
        // 把ht[0].table[d->rehashidx] 对应桶的链表置空  
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++; // 更新rehashidx
    }

    // 判断ht[0]的数据是否全部迁移完成 
    if (d->ht[0].used == 0) {
        // 释放ht[0]内存空间
        zfree(d->ht[0].table);
        // 把ht[0]指向ht[1]，以便接受正常的请求
        d->ht[0] = d->ht[1];
        // 重置ht[1]的大小为0
        _dictReset(&d->ht[1]);
        // 设置全局哈希表的rehashidx标识为-1，表示rehash结束
        d->rehashidx = -1;
        //返回0，表示ht[0]中所有元素都迁移完
        return 0;
    }

    //返回1，表示ht[0]中仍然有元素没有迁移完
    return 1;
}

/*
 * 此函数仅执行一个重新散列步骤，并且仅当没有安全迭代器绑定到我们的散列表时。 
 * 当在重新散列中间有迭代器时，不能弄乱两个散列表，否则某些元素可能会丢失或重复。
 *
 * 此函数由字典中的常见查找或更新操作调用，以便哈希表在主动使用时自动从 H1 迁移到 H2。
 *
 * @param *d
 */
static void _dictRehashStep(dict *d) {
    // rehash一个桶的数据
    if (d->iterators == 0) dictRehash(d,1);
}

/* 
 * 以 ms+"delta" 毫秒rehash。 
 * "delta" 的值大于0，多数情况下小于1。 
 * 确切的上限取决于 dictRehash(d,100) 的运行时间。
 * 
 * @param *d
 * @param ms
 */
int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds(); // ms时间戳
    int rehashes = 0;
    
    while(dictRehash(d,100)) { // 一次rehash 100个桶
        rehashes += 100;
        // 超过指定时间，break
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

dictAddRaw -> _dictRehashStep
dictGenericDelete -> _dictRehashStep
dictFind -> _dictRehashStep
dictGetRandomKey -> _dictRehashStep
dictGetSomeKeys -> _dictRehashStep

_dictRehashStep -> dictRehash
incrementallyRehash -> dictRehashMilliseconds -> dictRehash

(3.3) 渐进式rehash时，增删改查操作哪个哈希表?

当部分bucket 执行 rehash，部分bucket还没有执行rehash，这时增删查请求操作是对ht[1]操作，还是ht[0] ?

在新增操作时，调用dictAdd，会调用dictAddRaw，有一行代码专门对rehash做了处理，会保存到ht[1]，ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

在更新操作时，调用dictReplace，会调用dictAddRaw -> _dictKeyIndex，在查找key时有个判断 for (table = 0; table <= 1; table++)，会在2个哈希表查找，然后通过指针替换entry，操作的是key所在的哈希表。

在删除操作时，调用dictDelete方法，会对ht[0]和ht[1]都做删除， for (table = 0; table <= 1; table++) 这行代码就是要对2个哈希表分表处理

查询操作，调用dictFind方法，也是会对两个ht都查询，for (table = 0; table <= 1; table++)，先查ht[0]，查到了返回，没有查到再查ht[1]

(3.4) rehash扩容后有多大-rehash的结果

在 Redis 中，rehash 对 哈希表空间的扩容是通过调用 dictExpand 函数来完成的。

dictExpand 函数的参数有两个，一个是要扩容的 哈希表，另一个是要扩到的容量

/*
 * 扩展或创建哈希表
 * 
 * @param *d 要扩容的哈希表
 * @param size 扩容后的容量
 */
int dictExpand(dict *d, unsigned long size)
{
    // 校验
    // 如果已经在扩容 或者 扩容后的大小<哈希表中已有的元素数 返回错误
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; // 新哈希表
    unsigned long realsize = _dictNextPower(size); // 获取扩容后的大小 (realsize >= size 并且 realsize是2的幂次方)

    // 扩容后的大小 = 当前大小，返回错误
    if (realsize == d->ht[0].size) return DICT_ERR;

    // 为新的哈希表分配内存 并 将所有指针初始化为NULL
    n.size = realsize; // 大小
    n.sizemask = realsize-1; //  
    n.table = zcalloc(realsize*sizeof(dictEntry*));  // 分配内存
    n.used = 0;  // 未使用

    // 这是第一次初始化吗？ 如果是这样，那不是真正的重新哈希，我们只是设置第一个哈希表，以便它可以接受keys。  
    if (d->ht[0].table == NULL) { // 未初始化
        d->ht[0] = n;
        return DICT_OK;
    }

    // 为 增量哈希 准备第二个哈希表 // Prepare a second hash table for incremental rehashing
    d->ht[1] = n; // 设置哈希表
    d->rehashidx = 0; // 设置 rehash index
    return DICT_OK;
}

/* 哈希表的容量是2的幂次方 */
static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE; // 哈希表初始大小默认是4 

    // 如果要扩容的大小已经超过最大值，则返回最大值加1
    if (size >= LONG_MAX) return LONG_MAX + 1LU;

    // 这里是计算2的幂次方 获取一个>=size 的最小2的幂次方
    while(1) {
        // 如果扩容大小大于等于要扩容的值，就返回当前值
        if (i >= size)
            return i;
        i *= 2;
    }
}

为什么哈希表的容量要是2的幂次方？
因为容量是2的幂次方，进行计算可以转换为位运算，位运算计算比较快。

(4) Redis里的Hash函数

当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

Hash 函数会影响 哈希表的查询效率及哈希冲突情况，那么，你能从 Redis 的源码中，找到 哈希表使用的是哪一种 Hash 函数吗？

在rehash时，dictRehash函数里 从老的ht[0]把数据迁移到ht[1]的时候，需要计算key的hash，与sizemask计算获取数组下标，对应代码是 h = dictHashKey(d, de->key) & d->ht[1].sizemask;

dictHashKey(d, de->key) 调用了哈希函数，点进这个方法

调用 #define dictHashKey(d, key) (d)->type->hashFunction(key)，也就是使用的 hashFunction(key) 这个函数

想了想，Hash有多种实现，而且struct dict也定义了dictType *type

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的地方，发现有很多，排除掉redis-cli.c sentinel.c 感觉 dict.c 和 server.c里的概率更大
看了一下server.c里的引用，有setDictType zsetDictType dbDictType 而且注释里写着 /* hash function */
看了dictSdsHash，对应 dictGenHashFunction

uint64_t dictGenHashFunction(const void *key, int len) {
    return siphash(key,len,dict_hash_function_seed);
}

发现使用的siphash.c文件里的siphash

这个方法不太容易看懂，但是作用是计算一个key的hash值

uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k) {
#ifndef UNALIGNED_LE_CPU
    uint64_t hash;
    uint8_t *out = (uint8_t*) &hash;
#endif
    uint64_t v0 = 0x736f6d6570736575ULL;
    uint64_t v1 = 0x646f72616e646f6dULL;
    uint64_t v2 = 0x6c7967656e657261ULL;
    uint64_t v3 = 0x7465646279746573ULL;
    uint64_t k0 = U8TO64_LE(k);
    uint64_t k1 = U8TO64_LE(k + 8);
    uint64_t m;
    const uint8_t *end = in + inlen - (inlen % sizeof(uint64_t));
    const int left = inlen & 7;
    uint64_t b = ((uint64_t)inlen) << 56;
    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;

    for (; in != end; in += 8) {
        m = U8TO64_LE(in);
        v3 ^= m;

        SIPROUND;

        v0 ^= m;
    }

    switch (left) {
    case 7: b |= ((uint64_t)in[6]) << 48; /* fall-thru */
    case 6: b |= ((uint64_t)in[5]) << 40; /* fall-thru */
    case 5: b |= ((uint64_t)in[4]) << 32; /* fall-thru */
    case 4: b |= ((uint64_t)in[3]) << 24; /* fall-thru */
    case 3: b |= ((uint64_t)in[2]) << 16; /* fall-thru */
    case 2: b |= ((uint64_t)in[1]) << 8; /* fall-thru */
    case 1: b |= ((uint64_t)in[0]); break;
    case 0: break;
    }

    v3 ^= b;

    SIPROUND;

    v0 ^= b;
    v2 ^= 0xff;

    SIPROUND;
    SIPROUND;

    b = v0 ^ v1 ^ v2 ^ v3;
#ifndef UNALIGNED_LE_CPU
    U64TO8_LE(out, b);
    return hash;
#else
    return b;
#endif
}

(5) 总结

1、Redis 中的 dict 数据结构，采用「链式哈希」的方式存储，当哈希冲突严重时，会开辟一个新的哈希表，翻倍扩容，并采用「渐进式 rehash」的方式迁移数据

2、所谓「渐进式 rehash」是指，把很大块迁移数据的开销，平摊到多次小的操作中，目的是降低主线程的性能影响

3、Redis 中凡是需要 O(1) 时间获取 k-v 数据的场景，都使用了 dict 这个数据结构，也就是说 dict 是 Redis 中重中之重的「底层数据结构」

4、dict 封装好了友好的「增删改查」API，并在适当时机「自动扩容、缩容」，这给上层数据类型（Hash/Set/Sorted Set）、全局哈希表的实现提供了非常大的便利

5、例如，Redis 中每个 DB 存放数据的「全局哈希表、过期key」都用到了 dict：

6、「全局哈希表」在触发渐进式 rehash 的情况有 2 个：

• 增删改查哈希表时：每次迁移 1 个哈希桶（文章提到的 dict.c 中的 _dictRehashStep 函数）
• 定时 rehash：如果 dict 一直没有操作，无法渐进式迁移数据，那主线程会默认每间隔 100ms 执行一次迁移操作。这里一次会以 100 个桶为基本单位迁移数据，并限制如果一次操作耗时超时 1ms 就结束本次任务，待下次再次触发迁移（文章没提到这个，详见 dict.c 的 dictRehashMilliseconds 函数）

（注意：定时 rehash 只会迁移全局哈希表中的数据，不会定时迁移 Hash/Set/Sorted Set 下的哈希表的数据，这些哈希表只会在操作数据时做实时的渐进式 rehash）

7、dict 在负载因子超过 1 时（used: bucket size >= 1），会触发 rehash。但如果 Redis 正在 RDB 或 AOF rewrite，为避免父进程大量写时复制，会暂时关闭触发 rehash。但这里有个例外，如果负载因子超过了 5（哈希冲突已非常严重），依旧会强制做 rehash（重点）

8、dict 在 rehash 期间，查询旧哈希表找不到结果，还需要在新哈希表查询一次

参考资料

[1] Redis源码剖析与实战 - 03 如何实现一个性能优异的Hash表？
[2] Redis设计与实现 - 字典