1. HASHTABLE概述
就是数据结构中经典的哈希表衍生, 查询访问仍在常熟步能完成.且特性也和STL中的hash_map 一样,表中元素格式到大一定量时会根据因子乘数扩容相应空白节点,存储,查询也是通过映射函数完成的.
2. HASHTABLE结构
先看图
struct dict (字典结构体)
// 定义一个名为dict的结构体，用于在Redis中实现字典功能。
typedef struct dict {
dictType *type; // 指向一个dictType结构体的指针，该结构体定义了字典的类型特定操作。
void *privdata; // 一个指向私有数据的指针，可以被字典的类型操作使用。
dictht ht[2]; // 包含两个dictht类型的哈希表，用于实现rehashing。
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 一个长整型变量，用于记录rehashing的进度。如果rehashidx的值为-1，则表示没有进行rehashing。
unsigned long iterators; /* number of iterators currently running */
// 一个无符号长整型变量，记录当前运行的迭代器数量。
} dict;1. dictType *type：这是一个指向 dictType 结构体的指针，`dictType` 结构体中包含了一些函数指针，这些函数指针指向的函数用于执行与字典类型相关的特定操作，比如键值对的复制、比较和释放等。
2. void *privdata：这是一个指向私有数据的指针，这个私有数据是与 type 相关联的，可以被 type 中定义的函数使用。
3. dictht ht[2]：这是一个包含两个 dictht 类型的数组，`dictht` 是Redis字典的哈希表实现，包含哈希桶和相关的属性。这两个哈希表用于在rehashing过程中同时存在，以便平滑地从旧哈希表迁移到新哈希表。
4. long rehashidx：Redis字典在需要扩展或收缩哈希表时进行的过程。rehashidx 的值为 -1，表示没有rehashing操作正在进行。
5. unsigned long iterators：这个字段记录了当前正在运行的迭代器数量。迭代器用于遍历字典中的所有元素，这个计数器确保在迭代过程中字典的哈希表结构不会被修改。
struct dictht (哈希表结构体)
typedef struct dictht {
// 一个指向dictEntry指针数组的指针，用于存储哈希表中的所有条目
dictEntry **table;
// 哈希表的大小，即table数组的长度
unsigned long size;
// 用于计算哈希值对应的数组索引的掩码，它的值总是等于size-1
// 这样可以方便地通过位运算来计算索引，提高效率
unsigned long sizemask;
// 记录哈希表中已经使用的条目数量
unsigned long used;
} dictht;struct dictEntry (哈希表素结构体)
typedef struct dictEntry {
// 键，可以指向任意类型的数据
void *key;
// 联合体 v，包含多种类型的值
// 这样可以节省内存，因为不同类型的值可以直接存储在这个联合体中
union {
// 指向实际值的指针，可以指向任意类型的数据
void *val;
// 无符号的 64 位整数
uint64_t u64;
// 有符号的 64 位整数
int64_t s64;
// 双精度浮点数
double d;
} v;
// 指向同一个哈希桶中的下一个条目的指针
// 用于解决哈希冲突，通过链表的方式将具有相同哈希值的条目连接起来
struct dictEntry *next;
// 一个任意长度的数据块，大小由 dictType 的 dictEntryMetadataBytes() 函数返回
// 这个数据块用于存储额外的元数据，比如过期时间等
void *metadata[];
} dictEntry;
3. HASHTABLE表渐进式扩容
先看图:
触发条件:
写入数据时,进行负载率计算 k = dictht.user/dictht.size
扩容因子(负载指数) >= 1时会进行(会受[持久化进程工作]BGSAVE或者BGREWRITEAOF进程影响), >= 5 强制进行扩容,忽略后台是否有 BGSAVE/BGREWRITEAOF 持久化进程在工作
// 定义一个名为dict的结构体，用于在Redis中实现字典功能。
typedef struct dict {
dictType *type; // 指向一个dictType结构体的指针，该结构体定义了字典的类型特定操作。
void *privdata; // 一个指向私有数据的指针，可以被字典的类型操作使用。
dictht ht[2]; // 包含两个dictht类型的哈希表，用于实现rehashing。
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 一个长整型变量，用于记录rehashing的进度。如果rehashidx的值为-1，则表示没有进行rehashing。
unsigned long iterators; /* number of iterators currently running */
// 一个无符号长整型变量，记录当前运行的迭代器数量。
} dict;主副表:字典结构体中定义容量为2的哈希表成员 ht[2], ht[0] 表示是主表,不触发扩容/缩容时所有哈希表操作都在该表进行;ht[1] 是副表,只在扩容和缩容时用到,扩容/缩容后的新表会在副表构建完成.之后再交换ht[0]ht[1]第地址指向,这样新表就会变成主表.
工作原理:
这里分两种情况说:
扩容过程没有其他hash表操作:
将扩缩容标记rehashindx 置为0,表示开始扩容或缩容,创建一个空新表,表的大小是 use*2 向上取整 2^n个,比如 use= 500 则有: 500*2 向上取2^n 幂次整 = 1000 -> 2^n = 1024 (n = 10) ,空表创建好后会将旧表中的的元素重新与新表建立映射并使用头插法将数据剪切过去(也就是所迁移过去的元素,再旧表是没有的).迁移完成后将ht[2] 数组里的量指向内容交换,将rehashindx值置为-1,扩容完成.
扩容过程中有其他hash操作:
同上这里只说新表已经建立完成下发生的几种情况:
1.扩容时发生查询(扩缩容时若在酒标找不到数值,则会搜索新表):
a.在旧表中找到: 返回元素值,顺便做rehash和剪切迁移操作
b.旧表找不到:查新表返回数据继续迁移
c.发现是一个已做删除标记的脏节点,立马返回
2.加入元素
a.新表中加入,drict.use + 1
4. 缩容
触发条件:
写入数据时,载率计算 k = dictht.user/dictht.size < 0.1 会进行缩容 (会受[持久化进程工作]BGSAVE或者BGREWRITEAOF进程影响) 没有持久化进程在工作时才会开始
新表大小:
同扩容： use*2 向上取整 2^n个,比如 use= 500 则有: 500*2 向上取2^n 幂次整 = 1000 -> 2^n = 1024 (n = 10)
INTERVIEW
1. HASHTABLE查找元素总数的平均时间复杂度是多少？
根据输入key计算映射桶位置，遍历桶，一般个位数步即可找到目标值，O(1)
2. 一个数据在HASHTABLE中的存储位置是怎么计算的？
大致分两步即可定位到存储位置(对应的哈希桶)
a.将输入的key通过哈希算法(murmurhash2/siphash) 得到哈希值
b.将哈希码和哈希表中结构体（dictht.sizemask）
3. HASHTABLE怎么扩容？
看上面扩容部分
4. HASHTABLE怎么缩容？
看上面缩容
5. 什么时候扩容，什么时候缩容？
统一都是在有元素加入集合的时候触发检查 负载因子
扩容:
负载因子k = drict.use/drict.size >= 1 扩容，但有持久化进程在运行时暂时不会扩容，k >= 5 时不管有没有持久化进程运行都会扩容
缩容
k = drict.use/drict.size < 0.1 缩容，但有持久化进程在运行时暂时不会缩容
f