dict

Redis 字典是应用了哈希表作为底层实现的，一个哈希表里能够有多个哈希表节点，每一个哈希表节点保留字典的一个键值对。

/* Hash Tables Implementation.
 *
 * This file implements in-memory hash tables with insert/del/replace/find/
 * get-random-element operations. Hash tables will auto-resize if needed
 * tables of power of two in size are used, collisions are handled by
 * chaining. See the source code for more information... :)
 *
 * 这个文件实现了一个内存哈希表，* 它反对插入、删除、替换、查找和获取随机元素等操作。*
 * 哈希表会主动在表的大小的二次方之间进行调整。*
 * 键的抵触通过链表来解决。

数据结构

字典

/*
 * 字典
 */
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 公有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的平安迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;

/*
 * 字典类型特定函数
 */
typedef struct dictType {

    // 计算哈希值的函数
    unsigned int (*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;

void *provdata 保留须要传给那些类型特定函数的可选参数。

个别状况下字典只应用 ht[0] ht[1] 只会对 ht[0] 进行 rehash 时应用。

哈希表

/*
 * 哈希表
 *
 * 每个字典都应用两个哈希表，从而实现渐进式 rehash。*/
typedef struct dictht {
    
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

哈希表节点

/*
 * 哈希表节点
 */
typedef struct dictEntry {
    
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，造成链表
    struct dictEntry *next;

} dictEntry;

V 保留的是值，它能够是一个指针，也能够是有符号和无符号的整型

long int 就是 int 都是 4 字节

不同名是因为起因是晚期的 C 编译器定义了 long int 占用 4 个字节，int 占用 2 个字节

long long 才是 8 字节

留神

uint8_t，uint16_t，uint32_t 等都不是什么新的数据类型，它们只是应用 typedef 给类型起的别名

#ifndef __int8_t_defined
# define __int8_t_defined
typedef signed char             int8_t; 
typedef short int               int16_t;
typedef int                     int32_t;
# if __WORDSIZE == 64
typedef long int                int64_t;
# else
__extension__
typedef long long int           int64_t;
# endif
#endif
 
/* Unsigned.  */
typedef unsigned char           uint8_t;
typedef unsigned short int      uint16_t;
#ifndef __uint32_t_defined
typedef unsigned int            uint32_t;
# define __uint32_t_defined
#endif
#if __WORDSIZE == 64
typedef unsigned long int       uint64_t;
#else
__extension__
typedef unsigned long long int  uint64_t;

哈希算法

要将一个新的键值对退出字典，程序须要限依据键计算出哈希值和索引值，而后依据索引值，将蕴含新键值对的哈希表节点放到哈希数组的指定索引上。

解决建抵触

当两个或者以上数量的键被哈希表数组分到了同一个索引上这就时抵触

Redis 的解决办法是 链地址法

每个哈希表节点都有一个 next 指针，多个节点能够用 next 指针形成一个单向链表，被分到同一个索引的多个节点就能够用单向链表连起来。

rehash

随着零碎的运行，哈希表保留的键值会越来越多，为了让哈希表的负载因子维持在一个正当的范畴，程序须要对哈希表的大小进行响应的弹性变动。

简略的说，如果哈希表超过里的元素超过了某个大小，就会给 h[1] 调配空间，就把 h[1] 扩充为 h[0] 的两倍，而后再把 h[0] 中的元素复制到 h[1] 中，再把 h[0] 清空，最初把 h[1] 变为 h[0],h[0] 变为 h[1].

触发扩缩容的条件

扩容

1. 以后服务器没有执行 BGSAVA 和 BGREWRITEAOF，并且哈希表的负载因子大于等于 1
2. 以后服务器正在执行 BGSAVA 和 BGREWRITEAOF，并且哈希表的负载因子大于等于 5

# 负载因子计算
load_facotr = ht[0].used / h[0].size

再执行 BGSAVA 和 BGREWRITEAOF 命令的过程中，Redis 须要创立以后服务器过程的子过程，而大多数操作系统都是采纳写时复制（copy-on-write）技术来优化子过程的应用效率，所以在子过程存在期间，服务器会提供执行拓展所需的负载因子，从而防止不必要的内存写入

当负载因子下于 0.1 主动膨胀。

渐近式 rehash

如果哈希表里的数据过多，咱们是不可能短时间进行 rehash，那太占用服务器资源了，所以咱们能够分屡次渐进式的实现。

给 h[1] 调配空间，在字典中保护一个索引计数器 rehashidx，初始值为 0。

在 rehash 期间，每次对字典进行了增删改查时，还会顺带将 h[0] 哈希表在 rehashidx 的索引上的索引键值对 rehash 到 h[1] 中，当 rehash 实现，rehashidx +1

在最终某个时候，h[0] 的索引键值对都会被 rehash 到 ht[1], 这时 rehashidx -1

留神

这里就有一个问题那么在 rehash 时，整个数据时散布在 h[0] 和 h[1] 上都有的，那么这里咱们规定了程序会先去 h[0] 找再去 h[1] 找。

那么再 rehash 时新增加的数据去哪呢？那必定时间接去 h[1] 保障 h[0] 只会缩小最初为空。