Dict – 字典/hash

哈希表结构定义

typedef struct dictht{
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    //总是等于 size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
 
}dictht

typedef struct dictEntry{
     //键
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
 
     //指向下一个哈希表节点，形成链表，用来解决hash冲突
     struct dictEntry *next;
}dictEntry

• 扩容和收缩： 当哈希表保存的键值对太多或者太少时，就要通过rehash来对hash表进行相应的扩展或者收缩，具体步骤：

1. 如果执行扩展，会基于原哈希表创建一个大小等于已使用2倍的哈希表。相反，如果执行的是收缩操作，每次收缩根据已使用空间缩小一倍创建一个新的hash表
   2.重新使用hash算法，计算索引值
   3.所有键值对迁移完成后，释放原hash表的内存空间

• 扩容的条件：
  1.服务器没有执行持久化操作，并且负载因子大于等于1
  2.服务器执行持久化操作，并且负载因子大于等于5
  ps: 负载因子 = 已保存数量 / hash表大小
• 渐进式rehash
  redis采用渐进式rehash，在进行渐进式rehash期间，字典的操作可能会在两个hash表上进行，第一个hash表没找到，就会去第二个hash表查找。进行增加操作，一定在新的hash表上进行。

原文地址：http://www.cnblogs.com/youj/p/16914545.html