目录
Dict 优点在于，它能以 O(1) 的复杂度快速查询数据。怎么做到的呢？将 key 通过 Hash 函数的计算，就能定位数据在表中的位置，因为哈希表实际上是数组，所以可以通过索引值快速查询到数据。
但是存在的风险也是有，在哈希表大小固定的情况下，随着数据不断增多，那么哈希冲突的可能性也会越高。
解决哈希冲突的方式，有很多种。
Redis 采用了「链式哈希」来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接起，以便这些数据在表中仍然可以被查询到。
接下来，详细说说 Dict 的结构设计
Dict 的结构
Dict 由三部分组成，分别是：dict、dictht、dicEntry
dictht
dictht 的结构如下：
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
- dictEntry **table，哈希表数组
- unsigned long size，哈希表大小（取值为 2n2^n2n）
- unsigned long sizemask，哈希表大小掩码，用于计算索引值，总是等于 size−1size - 1size−1
- unsigned long used，该哈希表已有的节点数量
dicEntry
dicEntry 结构如下
void *key;/*键*/
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; /*值*/
struct dictEntry *next;/*下一个 entry 的指针*/
} dictEntry;
- dicEntry 和 dictht 之间的组织方式如下图所示
- 当我们向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置。我们存储 k1=v1，假设 k1 的哈希值 h =1，则 1&3 = 1，因此 k1=v1 要存储到数组角标 1 位置。
- 如果计算出来的数组角标值相同，也就是说，出现了 *哈希冲突，redis 采用 ”链式哈希“ 的方式，将具有相同哈希值的数据串起来，形成链结构，这也就是为什么会有 struct dictEntry next 这个成员变量存在
