redis数据结构--字典

Redis的字典底层就是哈希表。

哈希表

首先给出哈希表的定义：

typedef struct dictht{
  dictEntry **table; // 哈希表数组
  unsigned long size; // 哈希表大小
  unsigned long sizemask; // 哈希表大小掩码 等于size - 1
  unsigned long used; // 哈希表已有节点数
} dictht;

其中可以看到，table是一个哈希表节点的数组，数组里存储实际的键值对。

哈希表节点

就是哈希表结构中，table数组中的节点结构：

typedef struct dictEntry{
  void *key; // 键
  union { 
    void *val;
    uint64_t u64;
    int64_t s64;
  } v; // 值
  struct dictEntry *next; // 指向下个哈希表节点
} dictEntry;

可以看出，值的部分可以是一个指针，或者uint64_t或者int64_t的整数。next指针用于把多个键哈希值相同的节点连接在一起解决哈希冲突。

字典

字典的数据结构如下:

typedef struct dict{
  dictType *type; // 类型指定函数
  void *privdata; // 私有数据
  dictht ht[2]; // 哈希表
  int rehashidex; // rehash索引，rehash不在进行的时候为 -1
} dict;

type指向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保存需要传给特定函数的可选参数。
ht中有两个哈希表，ht[0]用于存储键值对，ht[1]在ht[0]做rehash时使用。rehashidx记录rehash的进度，-1为没有rehash在进行。