面试官：说说Redis的Hash底层 我：......（来自阅文的面试题）

//字典结构体
typedef struct dict {
dictType *type;//类型，包括一些自定义函数，这些函数使得key和value能够存储
void *privdata;//私有数据
dictht ht[2];//两张hash表
long rehashidx; //渐进式hash标记，如果为-1，说明没在进行hash
unsigned long iterators; //正在迭代的迭代器数量
} dict;

//hash结构体
typedef struct dictht {
dictEntry **table;//真正数据的数组
unsigned long size;//数组的大小
unsigned long sizemask;//用户将hash映射到table的位置索引，他的值总是等于size-1
unsigned long used;//已用节点数量
} dictht;

//每个节点的结构体
typedef struct dictEntry {
   void *key; //key
   union {
          void *val;
          uint64_t u64;
          int64_t s64;
          double d;
   } v;//value
  struct dictEntry *next; //下一个数据节点的地址
} dictEntry;

/* 创建并初始化字典 */
dict *dictCreate(dictType *type,void *privDataPtr)
{
     dict *d = zmalloc(sizeof(*d));
     _dictInit(d,type,privDataPtr);
     return d;
}

/* Initialize the hash table */
int _dictInit(dict *d, dictType *type,void *privDataPtr)
{
     _dictReset(&d->ht[0]);
     _dictReset(&d->ht[1]);
     d->type = type;
     d->privdata = privDataPtr;
     d->rehashidx = -1;//赋值为-1，表示未进行hash
     d->iterators = 0;
return DICT_OK;
}

static int _dictExpandIfNeeded(dict *d)
{
      //判断是否处于扩容状态中，通过调用宏常量#define                                                 
      dictIsRehashing(d) ((d)->rehashidx != -1)
      //来判断是否可以扩容
      if (dictIsRehashing(d)) return DICT_OK;

      //判断第一个数组size是否为0,如果为0，则调用扩容方法，大小为宏常量
      //#define DICT_HT_INITIAL_SIZE 4
      if (d->ht[0].size == 0) 
             return dictExpand(d, DICT_HT_INITIAL_SIZE);

      //下面先列出if条件中所使用到的参数
      // static int dict_can_resize = 1;数值为1表示可以扩容
      //static unsigned int dict_force_resize_ratio = 5;
      //我们来分析if条件，如果第一个数组的所有节点数量大于等于第一个数组的大小（表      示节点数据已经有些多）
      //并且可用扩容（数值为1）或者所有节点数量除以数组大小大于5
      //这个条件表示扩容那个的条件，第一个就是节点必要大于等于数组长度，
      //第二点就再可以扩容和数据太多，超过5两个中选其一
      if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize ||
      d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
      {
            //调用扩容方法
            return dictExpand(d, d->ht[0].used*2);
      }
return DICT_OK;
}

int dictExpand(dict *d, unsigned long size)
{
      dictht n;
      //获取扩容后真正的大小，找到比size大的最小值，且是2的倍数
      unsigned long realsize = _dictNextPower(size);

      //一些判断条件
      if (dictIsRehashing(d) || d->ht[0].used > size)
            return DICT_ERR;

      if (realsize == d->ht[0].size) return DICT_ERR;

      n.size = realsize;
      n.sizemask = realsize-1;
      n.table = zcalloc(realsize*sizeof(dictEntry*));
      n.used = 0;

      //第一个hash为null，说明在初始化
      if (d->ht[0].table == NULL) {
            d->ht[0] = n;
      return DICT_OK;
      }

      //正在hash，给第二个hash的长度设置新的，
      d->ht[1] = n;
      d->rehashidx = 0;//设置当前正在hash
return DICT_OK;
}

/* 找到比size大的最小值，且是2的倍数 */
static unsigned long _dictNextPower(unsigned long size)
{
      unsigned long i = DICT_HT_INITIAL_SIZE;

      if (size >= LONG_MAX) return LONG_MAX;
      while(1) {
            if (i >= size)
                  return i;
      i *= 2;
      }
}

     //重新hash这个哈希表
// Redis的哈希表结构共有两个table数组，t0和t1，平常只使用一个t0，当需要重hash时则重hash到另一个table数组中
//参数列表
// 1. d: 待移动的哈希表，结构中存有目前已经重hash到哪个桶了
// 2. n: N步进行rehash
// 返回值 返回0说明整个表都重hash完成了，返回1代表未完成
int dictRehash(dict *d, int n) {
      int empty_visits = n*10;
      //如果当前rehashidx=-1,则返回0，表示hash完成
      if (!dictIsRehashing(d)) return 0;
      //分n步，而且ht[0]还有没有移动的节点
      while(n-- && d->ht[0].used != 0) {
            dictEntry *de, *nextde;
            assert(d->ht[0].size > (unsigned long)d->rehashidx);
            //第一个循环用来更新 rehashidx 的值，因为有些桶为空，所以 rehashidx并非每次都比原来前进一个位置，而是有可能前进几个位置，但最多不超过 10。
            //将rehashidx移动到ht[0]有节点的下标，也就是table[d->rehashidx]非空
      while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
      }
     //第二个循环用来将ht[0]表中每次找到的非空桶中的链表（或者就是单个节点）拷贝到ht[1]中
      de = d->ht[0].table[d->rehashidx]; 

     /* 利用循环将数据节点移过去 */
     while(de) {
          unsigned int h;

          nextde = de->next;
          h = dictHashKey(d, de->key) & d->ht[1].sizemask;
          de->next = d->ht[1].table[h];
          d->ht[1].table[h] = de;
          d->ht[0].used--;
          d->ht[1].used++;
          de = nextde;
          }
     d->ht[0].table[d->rehashidx] = NULL;
     d->rehashidx++;
    }

     if (d->ht[0].used == 0) {
          zfree(d->ht[0].table);
          d->ht[0] = d->ht[1];
          _dictReset(&d->ht[1]);
     d->rehashidx = -1;
     return 0;
}

return 1;
}