Redis的内存存储结构是个大的字典存储，也就是我们通常说的哈希表。Redis小到可以存储几万记录的CACHE,大到可以存储几千万甚至上亿的记录（看内存而定），这充分说明Redis作为缓冲的强大。Redis的核心数据结构就是字典(dict),dict在数据量不断增大的过程中，会遇到HASH(key)碰撞的问题，如果DICT不够大，碰撞的概率增大，这样单个hash 桶存储的元素会越来愈多，查询效率就会变慢。如果数据量从几千万变成几万，不断减小的过程，DICT内存却会造成不必要的浪费。Redis的dict在设计的过程中充分考虑了dict自动扩大和收缩，实现了一个称之为rehash的过程。使dict出发rehash的条件有两个:

1）总的元素个数 除 DICT桶的个数得到每个桶平均存储的元素个数(pre_num),如果 pre_num > dict_force_resize_ratio,就会触发dict 扩大操作。dict_force_resize_ratio = 5。

2）在总元素 * 10 < 桶的个数，也就是,填充率必须<10%, DICT便会进行收缩，让total / bk_num 接近 1:1。

dict rehash扩大流程:

源代码函数调用和解析：

dictAddRaw->_dictKeyIndex->_dictExpandIfNeeded->dictExpand，这个函数调用关系是需要扩大dict的调用关系，
_dictKeyIndex函数代码：

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    // 如果有需要，对字典进行扩展
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;

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

    // 在两个哈希表中进行查找给定 key
    for (table = 0; table <= 1; table++) {

        // 根据哈希值和哈希表的 sizemask 
        // 计算出 key 可能出现在 table 数组中的哪个索引
        idx = h & d->ht[table].sizemask;

        // 在节点链表里查找给定 key
        // 因为链表的元素数量通常为 1 或者是一个很小的比率
        // 所以可以将这个操作看作 O(1) 来处理
        he = d->ht[table].table[idx];
        while(he) {
            // key 已经存在
            if (dictCompareKeys(d, key, he->key))
                return -1;

            he = he->next;
        }

        // 第一次进行运行到这里时，说明已经查找完 d->ht[0] 了
        // 这时如果哈希表不在 rehash 当中，就没有必要查找 d->ht[1]
        if (!dictIsRehashing(d)) break;
    }

    return idx;
}

static int _dictExpandIfNeeded(dict *d)
{
    // 已经在渐进式 rehash 当中，直接返回
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果哈希表为空，那么将它扩展为初始大小
    // O(N)
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    // 如果哈希表的已用节点数 >= 哈希表的大小，
    // 并且以下条件任一个为真：
    //   1) dict_can_resize 为真
    //   2) 已用节点数除以哈希表大小之比大于 
    //      dict_force_resize_ratio
    // 那么调用 dictExpand 对哈希表进行扩展
    // 扩展的体积至少为已使用节点数的两倍
    // O(N)
    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;
}

dict rehash缩小流程:

源代码函数调用和解析：

serverCron->tryResizeHashTables->dictResize->dictExpand

serverCron函数是个心跳函数,调用tryResizeHashTables段为:

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    ....
    if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) {
        // 将哈希表的比率维持在 1:1 附近
        tryResizeHashTables();
        if (server.activerehashing) incrementallyRehash(); //进行rehash动作
    }
    ....
}

void tryResizeHashTables(void) {
    int j;

    for (j = 0; j < server.dbnum; j++) {

        // 缩小键空间字典
        if (htNeedsResize(server.db[j].dict))
            dictResize(server.db[j].dict);

        // 缩小过期时间字典
        if (htNeedsResize(server.db[j].expires))
            dictResize(server.db[j].expires);
    }
}

htNeedsResize函数是判断是否可以需要进行dict缩小的条件判断,填充率必须>10%，否则会进行缩小,具体代码如下：

int htNeedsResize(dict *dict) {
    long long size, used;

    // 哈希表大小
    size = dictSlots(dict);

    // 哈希表已用节点数量
    used = dictSize(dict);

    // 当哈希表的大小大于 DICT_HT_INITIAL_SIZE 
    // 并且字典的填充率低于 REDIS_HT_MINFILL 时
    // 返回 1
    return (size && used && size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < REDIS_HT_MINFILL));
}

int dictResize(dict *d)
{
    int minimal;

    // 不能在 dict_can_resize 为假
    // 或者字典正在 rehash 时调用
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;

    minimal = d->ht[0].used;

    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;

    return dictExpand(d, minimal);
}