Redis - 字典的实现与哈希冲突解决

1. 字典的实现

edis的字典数据类型的实现主要分为两个部分：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; 
    unsigned long iterators; 
} dict;

其中，type属性表示字典的类型，而privdata属性表示字典的私有数据，它是一个指针类型，可以指向一个可选的私有数据结构。

值得注意的是，Redis中的字典使用了两个哈希表(dictht ht[2])，一个用于平时的读写操作，另一个仅在rehash过程中使用，用作新的哈希表。

2. 哈希算法

在Redis中，主要采用MurmurHash2这个非加密哈希算法。此算法的优点主要有三个：

• 速度快：MurmurHash算法的速度非常快，可以在很短的时间内计算出哈希值。
• 均匀性好：MurmurHash算法的哈希值分布均匀，因此冲突的概率较低。
• 易于实现：MurmurHash算法的实现非常简单。

3. 解决键冲突

解决哈希冲突，Redis采用了“链地址法”：当两个键的哈希值相同时，会将它们链接在同一个哈希槽（slot）上，形成一个链表。

4. rehash

5. 哈希表的扩容与收缩

总结

Redis字典的实现充分考虑了性能和内存效率，采用了一系列优化策略来保证其高效的运行，包括使用了MurmurHash算法，采用链地址法处理哈希冲突，以及通过渐进式rehash避免操作的长时间阻塞等。