Hyper の 个人博客

交流技术，分享生活

0%

Redis 原理初探（三）—— 散列表

发表于 更新于 分类于 ， 阅读次数：
本文字数： 4.4k 阅读时长 ≈ 4 分钟

字典

定义

  • 一种用于保存键值对（key-value pair）的抽象数据结构

    • 一个键（key）可以和一个值（value）进行关联（或者说将键映射为值）， 这些关联的键和值就称为键值对 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 键值对
typedef struct dictEntry
{
    void *key; //键
    union //值
    {
		void *val;         //可为一个指针
        unsigned int tu64; //可为uint64型整数
        int ts64;          //可为int64型整数
    } v;
    //指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

// 底层实现：哈希表
typedef struct dictht
{
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    //总是等于size - 1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
} dictht;

注：sizemask 和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面

适用场景

  • 一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串

redis 字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;

typedef struct dict
{
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    // rehash 索引
    //当rehash 不在进行时，值为-1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

注：type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置

  • type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定 类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数

  • privdata 属性则保存了需要传给那些类型特定函数的可选参数

哈希算法：MurmurHash2 算法

步骤

  • 根据键值对的键计算出哈希值和索引值

  • 根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上

1
2
3
4
5
# 使用字典设置的哈希函数，计算键key的哈希值
hash = dict -> type -> hashFunction(key)
# 使用哈希表的sizemask 属性和哈希值，计算出索引值
# 根据情况不同，ht[x] 可以是ht[0]或者ht[1]
index = hash & dict -> ht[x].sizemask

e.g. 一个完整的添加键值对 <k0, v0> 过程：

Step 1：使用语句 hash = dict->type->hashFunction(k0); 计算的处 k0 的哈希值

Step 2：假设计算出的哈希值为 8，则程序继续 index = hash & dict->ht[0].sizemask = 8 & 3 = 0; 计算得到 k0 的索引值为 0，这表示包含这个键值对的节点应该放置到哈希表数组的索引 0 位置上

键冲突的解决

  • 链地址法（separate chaining）

    • def 每个哈希表节点都有一个 next 指针，多个哈希表节点用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来
    • 由于 dictEntry 节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是 将新节点添加到链表的表头位置，其复杂度为 O (1)，排在其他已有节点的前面

大小调整：rehash

定义

​ 重新计算键的哈希值和索引值，然后将键值对从 ht [0] 放置到 ht [1] 的指定位置上

原因

​ 当哈希表保存的键值对太多或太少时，程序要对哈希表的大小进行相应的扩展或收缩，让哈希表负载因子维持在一个合理范围之内

  • 负载因子

    • def 散列表装满程度的标志因子，α = 填入表中的元素个数 / 散列表的长度
    • 由于表长是定值，α 与填入表中的元素个数成正比，所以，α 越大，填入表中的元素就越多，产生冲突的可能性就越大；反之，α 越小，标明填入表中的元素就越少，产生冲突的可能性就越小。一般应该严格控制在 0.7~0.8 之间。超过 0.8，查表时的不命中率按照指数曲线上升

注：详见《数据结构与算法》哈希冲突与二次探测

步骤

  • 为字典的 ht [1] 哈希表分配空间

    • 如果执行的是扩展操作，则 ht [1] 的大小为第一个大于等于 ht [0].used*2 的 2^n
    • 如果执行的收缩操作，则 ht [1] 的大小为第一个大于等于 ht [0].used 的 2^n

  • 进行 rehash 操作

  • 当 ht [0] 包含的所有键值对都迁移到 ht [1] 之后，释放 ht [0]，将 ht [1] 设置为 ht [0]，并在 ht [1] 新创建一个空白哈希表，为下一次 rehash 做准备

e.g. 要对图示字典 ht [0] 进行扩展操作:

Step 1：ht [0].used 当前的值为 4，4*2=8，而 8（2^3）恰好是第一个大于等于 4 的 2 的 n 次方，所以程序会将 ht [1] 哈希表的大小设置为 8

Step 2：将 ht [0] 包含的四个键值对都 rehash 到 ht [1]

Step 3：释放 ht [0]，并将 ht [1] 设置为 ht [0]，然后为 ht [1] 分配一个空白哈希表。执行完毕，程序成功将哈希表的大小从原来的 4 改为了现在的 8

执行条件

​ 当以下条件中任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

  • 服务器目前没有执行 BGSAVE 或 BGREWRITEAOF 命令，并且哈希表负载因子大于等于 1

  • 服务器正在执行 BGSAVE 或 BGREWRITEAOF 命令，并且哈希表负载因子大于等于 5

​ 当哈希表负载因子小于 0.1 时，程序自动开始对哈希表执行收缩操作

注：大多数系统采用写时复制优化子进程使用效率，所以在子进程存在期间服务器会提高执行扩展操作所需的负载因子，以尽可能避免在子进程存在期间进行哈希表扩展操作，以避免不必要的内存写入、最大限度地节约空间

优化的大小调整：渐进式 rehash

定义

  • 分多次、渐进式地将 ht [0] 里面的键值对慢慢地 rehash 到 ht [1]

目的

  • 避免 rehash 对服务器性能造成影响

步骤

  • 为 ht [1] 分配空间，让字典同时持有 ht [0] 和 ht [1] 两个哈希表

  • 在字典中维持一个索引计数器变量 rehashidx 并置 0，表示 rehash 开始工作

  • 在 rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定操作以外，还会顺带将 ht [0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht [1] 中，当 rehash 工作完成之后，程序将 rehashidx 属性的值 + 1

  • 随着字典操作的不断进行，最终在某个时间点上，ht [0] 的所有键值对都被 rehash 到 ht [1] 上，这时将 rehashidx 属性设为 - 1，表示 rehash 完成

e.g. 一次完整的渐进式 rehash 过程：

注：在渐进式 rehash 进行期间，字典 CRUD 操作会在两个哈希表上都进行；新添加到字典的键值对一律会被保存到 ht [1] 里面，而 ht [0] 则不再进行任何添加操作，以保证 ht [0] 包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表

散列表操作

常用命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import redis

# 获取连接
conn = redis.Redis(host='127.0.0.1', port=6379, password='123456')

# HMSET：设置散列表键值对，可添加多个键值对
conn.hmset('hash_key', {'k1': 'v1', 'k2': 'v2', 'k3': 'v3'})
# HMGET：根据键（key）从散列中获取值（value），可同时获取多个值
conn.hmget('hash_key', ['k1', 'k2'])
# HDEL：从散列表中删除指定键值对，可同时删除多个键值对
conn.hdel('hash_key', 'k2', 'k3')
# HLEN：获取散列表当前长度
conn.hlen('hash_key')
# HSET:将散列表中设置指定键的值为给定值
conn.hset('hash_key', 'k1', ['value1'])
# HGET:获取散列表中指定键的值
conn.hget('hash_key', 'k1')
# HSETNX：为散列表中不存在的字段赋值
conn.setnx('hash_key', 'new_field', 'hello_world')

高级特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# HEXISTS：检查给定键（key）是否存在于散列中
conn.exists('hash_key', 'k1')
# HKEYS：获取所有键（key）
conn.keys('hash_key')
# HVALS：获取所有值（value）
conn.hvals('hash_key')
# HGETALL：获取所有键值对
conn.hgetall('hash_key')

conn.hmset('hash_key', {'num_int': '0', 'num_float': '0.0'})
# HINCRBY：将散列中指定键值加上一个给定整数
conn.hincrby('hash_key', 'num_int')
# HINCRBYFLOAT：将散列中指定键值加上一个给定浮点数数
conn.hincrbyfloat('hash_key', 'num_float')

注：当散列中键值对的数目过多时，可以考虑先用 HKEYS 获取所有键（key），再通过 HVALS 只获取必要的值以减少需要传输的数据量

【参考】
[1] 《Redis 的设计与实现》

[2] 《Redis 实战》

相关文章：