哈希表

哈希表数据结构

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

  sizemask=size-1

哈希表节点数据结构

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

key属性保存着键值对中的键，而v属性保存着键值对中的值。

image.png

Redis的字典使用哈希表作为底层实现。

字典数据结构

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

image.png

hash算法

# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;