Redis 字典在数据存储中的核心要点
Redis 字典概述
Redis 作为一款高性能的键值对数据库，其字典结构是支撑数据存储与快速检索的关键基石。字典，在 Redis 中被广泛应用于数据库的底层实现以及诸如哈希（Hash）数据类型等高级数据结构。它本质上是一种基于哈希表实现的关联数组，能够高效地通过键（key）找到对应的值（value）。
在 Redis 中，字典使用哈希表作为底层数据结构来存储键值对。哈希表是一种以数组为基础的数据结构，通过对键进行哈希计算，得到一个哈希值，该哈希值作为数组的索引，从而快速定位到对应的值所在的位置。然而，由于哈希函数的特性，不同的键可能会产生相同的哈希值，这就导致了哈希冲突。为了解决哈希冲突，Redis 使用了链地址法（separate chaining）。
哈希表结构
Redis 的哈希表结构定义在 dict.h 头文件中，如下所示：
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
table是一个数组，数组中的每个元素都是一个指向dictEntry结构体的指针。dictEntry结构体用于存储键值对。size表示哈希表的大小，即table数组的长度。sizemask是size - 1，用于计算哈希值在table数组中的索引位置。通过hash & sizemask这样的操作，可以将哈希值映射到table数组的有效索引范围内。used记录哈希表中已使用的槽（slot）数量，也就是当前存储的键值对数量。
字典结构
字典结构体 dict 包含了两个哈希表，主要用于实现渐进式 rehash：
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
type是一个指向dictType结构体的指针，dictType结构体定义了针对不同数据类型的操作函数，例如哈希函数、比较函数等。
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;
privdata是一个指针，用于传递一些私有数据给dictType中的函数。ht是一个包含两个dictht结构体的数组，通常情况下，只有ht[0]用于存储数据，ht[1]在 rehash 过程中发挥作用。rehashidx记录当前 rehash 的进度，如果rehashidx == -1，表示当前没有进行 rehash 操作。iterators记录当前正在运行的迭代器数量，用于确保在迭代字典时不会进行 rehash 操作，以免破坏迭代器的状态。
哈希表节点结构
哈希表节点 dictEntry 用于存储键值对，其定义如下：
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
key是指向键的指针。v是一个联合体，用于存储值，可以是指针类型，也可以是整数或浮点数类型。next是指向下一个dictEntry节点的指针，用于解决哈希冲突，通过链表的方式将冲突的节点链接起来。
哈希函数
Redis 使用 MurmurHash2 算法作为默认的哈希函数，该算法具有较高的性能和良好的哈希分布特性。在 dict.c 中，哈希函数的调用如下：
static unsigned int dictGenHashFunction(const void *key, int len) {
return dictLegacyHashFunction(key, len);
}
unsigned int dictLegacyHashFunction(const void *key, int len) {
uint32_t h = DICT_HT_INITIAL_SIZE;
const char *p = key;
while (len--)
h = 33 * h ^ *p++;
return h & 0xffffffff;
}
这里的 dictGenHashFunction 最终调用 dictLegacyHashFunction 来计算哈希值。dictLegacyHashFunction 通过对键的每个字节进行特定的运算来生成哈希值，这种简单的算法在实际应用中也能表现出较好的效果。
哈希冲突解决
如前文所述，Redis 使用链地址法解决哈希冲突。当两个或多个键的哈希值相同时，这些键值对会被存储在同一个哈希表槽位对应的链表中。例如，假设有三个键 key1、key2 和 key3，它们的哈希值都映射到哈希表的第 i 个槽位。那么，在哈希表的 table[i] 位置，会存储一个 dictEntry 节点，该节点包含 key1 和对应的值，并且其 next 指针会指向包含 key2 的 dictEntry 节点，而这个节点的 next 指针又会指向包含 key3 的 dictEntry 节点，从而形成一个链表。
在查找键值对时，首先根据键计算哈希值，确定其在哈希表中的槽位。然后，从该槽位对应的链表头部开始遍历链表，通过比较键来找到目标键值对。这种方式虽然在冲突较多时会降低查找效率，但在哈希分布良好的情况下，能够有效地减少哈希冲突的影响，并且实现相对简单。
插入操作
当向 Redis 字典中插入一个新的键值对时，首先会计算键的哈希值，通过哈希值和 sizemask 确定该键值对应该存储在哈希表的哪个槽位。如果该槽位为空，直接将新的 dictEntry 节点插入到该槽位。如果该槽位已经有其他节点（即发生了哈希冲突），则将新节点插入到该槽位对应的链表头部。
以下是简化的插入操作伪代码：
function insert(dict, key, value):
hash = hash_function(key)
index = hash & dict.ht[0].sizemask
if dict.ht[0].table[index] is null:
create new dictEntry with key and value
dict.ht[0].table[index] = new dictEntry
dict.ht[0].used++
else:
create new dictEntry with key and value
new dictEntry.next = dict.ht[0].table[index]
dict.ht[0].table[index] = new dictEntry
dict.ht[0].used++
if dict.ht[0].used >= dict.ht[0].size * load_factor:
rehash(dict)
在插入操作后，会检查哈希表的负载因子（load factor，即 used / size）。如果负载因子超过一定阈值（Redis 默认是 1），则会触发 rehash 操作，以保证哈希表的性能。
查找操作
查找操作通过计算键的哈希值，定位到哈希表的槽位，然后在该槽位对应的链表中查找目标键值对。以下是简化的查找操作伪代码：
function find(dict, key):
hash = hash_function(key)
index = hash & dict.ht[0].sizemask
current = dict.ht[0].table[index]
while current is not null:
if keys_are_equal(current.key, key):
return current.value
current = current.next
return null
首先计算键的哈希值并确定槽位，然后从该槽位对应的链表头部开始遍历，通过比较键来查找目标值。如果找到匹配的键，则返回对应的值；如果遍历完链表都未找到，则返回 null。
删除操作
删除操作同样先计算键的哈希值，定位到哈希表的槽位，然后在链表中查找并删除目标键值对。以下是简化的删除操作伪代码：
function delete(dict, key):
hash = hash_function(key)
index = hash & dict.ht[0].sizemask
prev = null
current = dict.ht[0].table[index]
while current is not null:
if keys_are_equal(current.key, key):
if prev is null:
dict.ht[0].table[index] = current.next
else:
prev.next = current.next
free(current)
dict.ht[0].used--
return true
prev = current
current = current.next
return false
在找到目标键值对后，需要处理链表的链接关系，将其从链表中移除，并释放相应的内存空间。同时，更新哈希表的 used 计数。
Rehash 操作
随着数据的不断插入和删除，哈希表的负载因子会发生变化。当负载因子过高时，哈希冲突的概率会显著增加，导致查找、插入和删除操作的性能下降。为了维持哈希表的高效性能，Redis 会在适当的时候进行 rehash 操作，即重新分配哈希表的大小，并将旧哈希表中的所有键值对重新映射到新哈希表中。
触发条件
- 负载因子过高：当
ht[0].used / ht[0].size >= 1且redisServer.activerehashing为 1（表示允许主动 rehash）时，会触发 rehash。 - 负载因子过低：当
ht[0].used / ht[0].size < 0.1时，也会触发 rehash，此时会缩小哈希表的大小。
渐进式 Rehash
由于 Redis 是单线程模型，处理大量数据的 rehash 操作可能会导致服务器阻塞，影响性能。因此，Redis 采用渐进式 rehash 策略。在渐进式 rehash 过程中，Redis 不会一次性将旧哈希表中的所有键值对迁移到新哈希表，而是分多次逐步完成。
具体做法是，在 dict 结构体中维护一个 rehashidx 字段，记录当前 rehash 的进度。每次执行与字典相关的操作（如插入、查找、删除）时，除了执行正常的操作外，还会顺便将 ht[0] 中 rehashidx 位置的键值对迁移到 ht[1] 中，并将 rehashidx 加 1。当 rehashidx 等于 ht[0].size 时，表示 rehash 完成，此时将 ht[1] 赋值给 ht[0]，释放 ht[1]，并将 rehashidx 设为 -1。
以下是渐进式 rehash 的简化代码示例：
int dictRehash(dict *d, int n) {
int empty_visits = n * 10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
while (n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
while (d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while (de) {
uint64_t h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
在 dictRehash 函数中，n 表示每次调用时需要迁移的键值对数量。函数通过循环逐步将 ht[0] 中的键值对迁移到 ht[1]，直到 ht[0] 中的所有键值对都迁移完毕。
字典在 Redis 数据库中的应用
在 Redis 数据库中，字典是存储键值对的核心数据结构。每个 Redis 数据库都由一个 redisDb 结构体表示，其中包含一个字典用于存储数据库中的所有键值对：
typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */
dict *ready_keys; /* Blocked keys that received a PUSH */
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
int id; /* Database ID */
long long avg_ttl; /* Average TTL, just for stats */
unsigned long expires_cursor; /* Cursor of the active expire cycle. */
list *defrag_later; /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;
dict字典用于存储数据库中的所有键值对。expires字典用于存储设置了过期时间的键及其过期时间。
当执行 SET key value 命令时，实际上就是向 redisDb 的 dict 中插入一个新的键值对；执行 GET key 命令时，就是从 dict 中查找对应的值。通过这种方式，Redis 利用字典结构实现了高效的数据存储和检索。
字典在哈希数据类型中的应用
Redis 的哈希（Hash）数据类型也是基于字典实现的。哈希类型允许存储多个键值对，每个键值对中的键称为字段（field），值称为字段值（value）。在 Redis 内部，每个哈希对象都包含一个字典，用于存储这些字段和字段值。
当执行 HSET key field value 命令时，实际上是在哈希对象的字典中插入一个新的键值对，其中键为 field，值为 value。执行 HGET key field 命令时，就是从哈希对象的字典中查找 field 对应的 value。
以下是使用 Python 和 Redis 客户端库 redis - py 操作哈希数据类型的示例代码：
import redis
# 连接 Redis 服务器
r = redis.Redis(host='localhost', port=6379, db = 0)
# 设置哈希字段值
r.hset('myhash', 'field1', 'value1')
r.hset('myhash', 'field2', 'value2')
# 获取哈希字段值
value1 = r.hget('myhash', 'field1')
print(value1.decode('utf - 8'))
# 获取所有哈希字段和值
all_fields = r.hgetall('myhash')
for field, value in all_fields.items():
print(field.decode('utf - 8'), value.decode('utf - 8'))
在这个示例中，通过 hset 方法向名为 myhash 的哈希对象中插入字段值，通过 hget 方法获取单个字段值，通过 hgetall 方法获取所有字段和值。这些操作本质上都是对哈希对象内部字典的操作。
字典的性能分析
字典结构在 Redis 中的性能表现非常出色，主要得益于其高效的哈希算法和合理的冲突解决策略。在理想情况下，哈希表的查找、插入和删除操作的平均时间复杂度为 O(1)，这使得 Redis 能够快速处理大量的键值对操作。
然而，当哈希冲突严重时，查找、插入和删除操作的时间复杂度会退化为 O(n)，其中 n 是哈希表中链表的长度。为了避免这种情况，Redis 通过动态调整哈希表的大小（rehash 操作）来保持较低的负载因子，从而保证字典的高性能。
此外，渐进式 rehash 策略在保证字典性能的同时，避免了一次性 rehash 对服务器造成的阻塞，使得 Redis 在处理大数据量时依然能够保持高效和稳定。
综上所述，Redis 字典通过精心设计的结构、算法和操作策略，成为了 Redis 高性能数据存储和检索的核心基础，为 Redis 在各种应用场景中的广泛应用提供了坚实的保障。无论是简单的键值对存储，还是复杂的哈希数据类型，字典结构都发挥着至关重要的作用。理解 Redis 字典的核心要点，对于深入掌握 Redis 的工作原理以及优化基于 Redis 的应用程序性能具有重要意义。