底层数据结构-dict

• 字典（也叫哈希表）

• 结构定义

  ##整个哈希表
  typedef struct dictht{
      dictEntry **table; //存储“链表表头指针”的数组
      unsigned long size; //表的大小（即数组的长度）
      unsigned long sizemask; //掩码，用于算索引值，总是等于 size-1
      unsigned long used; //已有节点的数量
  
  } dictht;
  

  ##数组中的“链表表头指针”所指向的链表节点
  typedef struct dictEntry {
      void *key; //键
      union{
          void *val; //值可以是指针
          uint64_tu64; //也可以是无符号整型
          int64_ts64; //也可以是有符号整型
      }v;  //值
      struct dictEntry *next; //指向的下一个链表节点
  } dictEntry;
  

• 哈希算法

  • 计算哈希值
    • hash = dict->type->hashFunction(key);
  • 合并出索引值
    • index = hash & dict->ht[x].sizemask;

• 好处

  • 使用了“哈希值-链表”的键值对应，解决了哈希冲突的问题

• 坏处

  • 当键值对太多或太少时，需要rerehash(重新散列）
    • 太多则扩容扩大一倍，太小则缩容减小一半
    • 扩容触发条件
      • 服务器没执行BGSAVE或BGREWRITEAOF，且负载因子>=1
      • 服务器执行BGSAVE或BGREWRITEAOF，且负载因子>=5
    • 负载因子 = 已经保存的总链表节点数量/哈希表数组的长度
    • 采用渐近式rehash，可以每次进行一点，但这样就会同时有两个哈希表存在，属于用空间换时间的性能优化方法