Redis源码阅读--dict (11) nosqlredis

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保存的是值，它可以是一个指针，也可以是有符号和无符号的整型
【Redis源码阅读--dict (11)】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 charint8_t; typedef short intint16_t; typedef intint32_t; # if __WORDSIZE == 64 typedef long intint64_t; # else __extension__ typedef long long intint64_t; # endif #endif /* Unsigned.*/ typedef unsigned charuint8_t; typedef unsigned short intuint16_t; #ifndef __uint32_t_defined typedef unsigned intuint32_t; # define __uint32_t_defined #endif #if __WORDSIZE == 64 typedef unsigned long intuint64_t; #else __extension__ typedef unsigned long long intuint64_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].
触发扩缩容的条件扩容

当前服务器没有执行BGSAVA和BGREWRITEAOF，并且哈希表的负载因子大于等于1
当前服务器正在执行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]只会减少最后为空。