关于redis:Redis源码剖析与实战-学习笔记-Day3-如何实现一个性能优异的Hash表

哈希表是一种十分要害的数据结构，在计算机系统中施展着重要作用。
它的底层是数组 + 链表，通过哈希计算，能以 O(1) 的复杂度疾速依据 key 查问到数据。

(1) 数据结构 - 哈希表

假如让咱们本人实现一个哈希表，咱们要思考哪些方面？

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

(1.1) 提供的性能

新建哈希表、新增数据、批改数据、删除数据、查问数据

(1.2) 工夫复杂度 O(1)

要想使工夫复杂度为 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(){//todo}

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

(2) Redis 里的哈希表

对于 Redis 键值数据库来说，哈希表既是键值对中的一种值类型，同时，Redis 也应用一个全局 哈希表来保留所有的键值对，从而既满足利用存取 Hash 构造数据需要，又能提供疾速查问性能。

在理论利用 哈希表时，当数据量一直减少，它的性能就常常会受到 哈希抵触 和 rehash 开销的影响。

针对哈希抵触，Redis 采纳了链式哈希，在不扩容哈希表的前提下，将具备雷同哈希值的数据链接起来，以便这些数据在表中依然能够被查问到；
对于 rehash 开销，Redis 实现了渐进式 rehash 设计，进而缓解了 rehash 操作带来的额定开销对系统的性能影响。

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

源码 https://github.com/redis/redi…

   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 = (2^n - 1)，比 2^n 少 1，用于计算 key 对应桶的下标
    unsigned long used;  // 
} dictht;


/**
 * 哈希表节点
 */
typedef struct dictEntry {
    void *key; // 存储的 key
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;  // 存储的值
    struct dictEntry *next; // 链表的下一个节点
} dictEntry;

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

为什么要应用联合体呢？
这种实现办法是一种节俭内存的小技巧，因为当值为整数或双精度浮点数时，因为其自身就是 64 位，就能够不必指针指向了，而是能够间接存在键值对的构造体中，这样就防止了再用一个指针，从而节俭了内存空间。

(2.2) 哈希表提供的性能

(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;
}

/* Reset a hash table already initialized with ht_init().
 * 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)
{
    // 
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    // 哈希表设置键值对
    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 查找桶 
    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];
        // 遍历链表
        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.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

在哪些函数里调用了_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 = d->ht[0].table[d->rehashidx];

        // 反转链表 - 尾插法
        // 遍历链表  将这个桶中的所有键从旧的 ht[0] 移到新的 ht[1] 
        while(de) {
            uint64_t h;
            
            nextde = de->next; // 下一个链表节点
            // 获取 key 在新 ht[1]的下标
            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--; // 更新 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) 渐进式 hash 时，增删改查操作哪个 ht?

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

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

在更新操作时，调用dictReplace，也会调用dictAddRaw，原理同上

在删除操作时，调用 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

这个办法不太容易看懂

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
}

总结

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 期间，查问旧哈希表找不到后果，还须要在新哈希表查问一次

参考资料

https://weikeqin.com/tags/redis/
[1] Redis 源码分析与实战 – 03 如何实现一个性能优异的 Hash 表？
[2] Redis 设计与实现 – 字典

Redis 源码分析与实战 – 03 如何实现一个性能优异的 Hash 表？https://time.geekbang.org/col…