字典
定义
![]()
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;
int ts64;
} v;
struct dictEntry *next;
} dictEntry;
typedef struct dictht
{
dictEntry **table;
unsigned long size;
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];
int rehashidx;
} dict;
|
注：type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置
哈希算法：MurmurHash2 算法
步骤
1
2
3
4
5
|
hash = dict -> type -> hashFunction(key)
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，查表时的不命中率按照指数曲线上升
注：详见《数据结构与算法》哈希冲突与二次探测
步骤
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
![]()
执行条件
当以下条件中任意一个被满足时，程序会自动开始对哈希表执行扩展操作：
当哈希表负载因子小于 0.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')
conn.hmset('hash_key', {'k1': 'v1', 'k2': 'v2', 'k3': 'v3'})
conn.hmget('hash_key', ['k1', 'k2'])
conn.hdel('hash_key', 'k2', 'k3')
conn.hlen('hash_key')
conn.hset('hash_key', 'k1', ['value1'])
conn.hget('hash_key', 'k1')
conn.setnx('hash_key', 'new_field', 'hello_world')
|
高级特性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
conn.exists('hash_key', 'k1')
conn.keys('hash_key')
conn.hvals('hash_key')
conn.hgetall('hash_key')
conn.hmset('hash_key', {'num_int': '0', 'num_float': '0.0'})
conn.hincrby('hash_key', 'num_int')
conn.hincrbyfloat('hash_key', 'num_float')
|
注：当散列中键值对的数目过多时，可以考虑先用 HKEYS 获取所有键（key），再通过 HVALS 只获取必要的值以减少需要传输的数据量
【参考】
[1] 《Redis 的设计与实现》
[2] 《Redis 实战》
