@

目录

• 4. 字典实现 dict.h 和 dict.c
  • 数据结构定义
  • 部分宏定义
  • 哈希函数（本部分可选跳过）
  • Helper函数（可跳过，需要时阅读）
  • dict 构造函数 O(1)
  • dict 析构函数 O(N)
  • hashtable 构造函数 O(1)
  • dict resize O(1)
  • rehash O(m)
  • 限时rehash
  • set k O(1)
  • set kv O(1)
  • get k O(1)
  • update k O(1)
  • update kv O(1)
  • delete kv O(1)
  • get iter O(1)
  • delete iter O(1)
  • 迭代 O(1)
  • dict 随机key O(1)
  • dict scan O(1)

4. 字典实现 dict.h 和 dict.c

数据结构定义

• 状态码

  #define DICT_OK 0	// 操作成功
  #define DICT_ERR 1	// 操作失败（或出错）
  

• 哈希表kv节点

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

• 哈希表

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

• kv操作函数

  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;
  

• dict主角

  typedef struct dict {
      dictType *type;		// 类型特定函数
      void *privdata;		// 私有数据
      dictht ht[2]; 		// 哈希表, 存在一个时占第一个，存在两个时正在rehash
      int rehashidx;		// rehash 索引, 当 rehash 不在进行时，值为 -1
      int iterators;		// 目前正在运行的安全迭代器的数量
  } dict;
  

• dict 迭代器

  typedef struct dictIterator {
      dict *d;    // 被迭代的字典
      // table ：正在被迭代的哈希表号码，值可以是 0 或 1 。
      // index ：迭代器当前所指向的哈希表索引位置。
      // safe ：标识这个迭代器是否安全
      int table, index, safe;
      // entry ：当前迭代到的节点的指针
      // nextEntry ：当前迭代节点的下一个节点
      //             因为在安全迭代器运作时， entry 所指向的节点可能会被修改，
      //             所以需要一个额外的指针来保存下一节点的位置，
      //             从而防止指针丢失
      dictEntry *entry, *nextEntry;
      long long fingerprint; /* unsafe iterator fingerprint for misuse detection */
  } dictIterator;
  

部分宏定义

#define DICT_HT_INITIAL_SIZE     4  												// 哈希表初始大小
// 释放给定字典节点的值
#define dictFreeVal(d, entry) \
    if ((d)->type->valDestructor) \
        (d)->type->valDestructor((d)->privdata, (entry)->v.val)
// 设置给定字典节点的值
#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \
        entry->v.val = (d)->type->valDup((d)->privdata, _val_); \
    else \
        entry->v.val = (_val_); \
} while(0)
...
// 比对两个键
#define dictCompareKeys(d, key1, key2) \
    (((d)->type->keyCompare) ? \
        (d)->type->keyCompare((d)->privdata, key1, key2) : \
        (key1) == (key2))
#define dictHashKey(d, key) (d)->type->hashFunction(key)  // 计算给定键的哈希值
#define dictGetKey(he) ((he)->key) 												// 返回获取给定节点的键
...

哈希函数（本部分可选跳过）

• Thomas Wang's 32 bit Mix Function

  unsigned int dictIntHashFunction(unsigned int key) {
      key += ~(key << 15);
      key ^=  (key >> 10);
      key +=  (key << 3);
      key ^=  (key >> 6);
      key += ~(key << 11);
      key ^=  (key >> 16);
      return key;
  }
  

• Identity hash function for integer keys

  unsigned int dictIdentityHashFunction(unsigned int key) {
      return key;
  }
  

• MurmurHash2, by Austin Appleby

  unsigned int dictGenHashFunction(const void *key, int len) {
      /* 'm' and 'r' are mixing constants generated offline.
       They're not really 'magic', they just happen to work well.  */
      uint32_t seed = dict_hash_function_seed;
      const uint32_t m = 0x5bd1e995;
      const int r = 24;
      /* Initialize the hash to a 'random' value */
      uint32_t h = seed ^ len;
      /* Mix 4 bytes at a time into the hash */
      const unsigned char *data = (const unsigned char *)key;
      while(len >= 4) {
          uint32_t k = *(uint32_t*)data;
          k *= m;
          k ^= k >> r;
          k *= m;
          h *= m;
          h ^= k;
          data += 4;
          len -= 4;
      }
      /* Handle the last few bytes of the input array  */
      switch(len) {
      case 3: h ^= data[2] << 16;
      case 2: h ^= data[1] << 8;
      case 1: h ^= data[0]; h *= m;
      };
      /* Do a few final mixes of the hash to ensure the last few
       * bytes are well-incorporated. */
      h ^= h >> 13;
      h *= m;
      h ^= h >> 15;
      return (unsigned int)h;
  }
  

• a case insensitive hash function (based on djb hash)

  unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
      unsigned int hash = (unsigned int)dict_hash_function_seed;
      while (len--)
          hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
      return hash;
  }
  

关于hash函数，留坑待填，有时间会整理常见hash函数

Helper函数（可跳过，需要时阅读）

• 时间函数 O(1)

  long long timeInMilliseconds(void) {
      struct timeval tv;
      gettimeofday(&tv,NULL);
      return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
  }
  

• Fingerprint函数 O(1)

  long long dictFingerprint(dict *d) {
      long long integers[6], hash = 0;
      int j;
      integers[0] = (long) d->ht[0].table;
      integers[1] = d->ht[0].size;
      integers[2] = d->ht[0].used;
      integers[3] = (long) d->ht[1].table;
      integers[4] = d->ht[1].size;
      integers[5] = d->ht[1].used;
      for (j = 0; j < 6; j++) {
          hash += integers[j];
          hash = (~hash) + (hash << 21); 
          hash = hash ^ (hash >> 24);
          hash = (hash + (hash << 3)) + (hash << 8); 
          hash = hash ^ (hash >> 14);
          hash = (hash + (hash << 2)) + (hash << 4); 
          hash = hash ^ (hash >> 28);
          hash = hash + (hash << 31);
      }
      return hash;
  }
  

• 重置/初始化 hashtable，不涉及内存 O(1)

  static void _dictReset(dictht *ht) {
      ht->table = NULL;
      ht->size = 0;
      ht->sizemask = 0;
      ht->used = 0;
  }
  

• 重置/初始化dict，不涉及内存 O(1)

  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;			// 设置哈希表 rehash 状态
      d->iterators = 0;			// 设置字典的安全迭代器数量
      return DICT_OK;
  }
  

• dict进行一步rehash O(1)

  static void _dictRehashStep(dict *d) {
      if (d->iterators == 0) dictRehash(d,1);
  }
  

• 遍历释放某个hashtable，用户自定义释放内存，并重置 O(n)

  int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
      unsigned long i;
      for (i = 0; i < ht->size && ht->used > 0; i++) {    					// 遍历整个哈希表 T = O(N)
          dictEntry *he, *nextHe;
          if (callback && (i & 65535) == 0) callback(d->privdata);
          if ((he = ht->table[i]) == NULL) continue;   							// 跳过空索引
          while(he) {   			// 遍历整个链表 T = O(1)
              nextHe = he->next;
              dictFreeKey(d, he); // 删除键
              dictFreeVal(d, he); // 删除值
              zfree(he); 			// 释放节点
              ht->used--;			// 更新已使用节点计数
              he = nextHe; 		// 处理下个节点
          }
      }
      zfree(ht->table); 			// 释放哈希表结构
      _dictReset(ht);  			// 重置哈希表属性
      return DICT_OK; 			/* never fails */
  }
  

• 尝试expand，符合条件调用expand函数 O(1) / O(n)

  static int _dictExpandIfNeeded(dict *d) {
      // 渐进式 rehash 已经在进行了，直接返回
      if (dictIsRehashing(d)) return DICT_OK;
      // 如果字典（的 0 号哈希表）为空，那么创建并返回初始化大小的 0 号哈希表 T = O(1)
      if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
      // 一下两个条件同时为真时，对字典进行扩展
      // 1）字典已使用节点数和字典大小之间的比率大于 1
      // 2）dict_can_resize 为真 或者 已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
      if (d->ht[0].used >= d->ht[0].size &&
          (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) {
          // 新哈希表的大小至少是目前已使用节点数的两倍 T = O(N)
          return dictExpand(d, d->ht[0].used * 2);
      }
      return DICT_OK;
  }
  

• 返回合适的hashtable size O(1)

  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;
      }
  }
  

• 返回合适的新key对应的index O(1)

  static int _dictKeyIndex(dict *d, const void *key) {
      unsigned int h, idx, table;
      dictEntry *he;
      if (_dictExpandIfNeeded(d) == DICT_ERR)   	// rehash O(1) / O(N)
          return -1;
      h = dictHashKey(d, key);					// 计算 key 的哈希值
      for (table = 0; table <= 1; table++) {
          idx = h & d->ht[table].sizemask; 		// 计算索引值
          he = d->ht[table].table[idx];  			// 查找 key 是否存在 T = O(1)
          while(he) {
              if (dictCompareKeys(d, key, he->key))
                  return -1;						// 存在返回 -1
              he = he->next;
          }
          if (!dictIsRehashing(d)) break;			// 如果这时 rehash 正在进行，那么继续对 1 号哈希表进行 rehash
      }
      return idx;									// 返回索引值
  }
  

• 返回合适的hashtable size

  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;
      }
  }
  

dict 构造函数 O(1)

dict *dictCreate(dictType *type, void *privDataPtr) {
    dict *d = zmalloc(sizeof(*d));
    _dictInit(d, type, privDataPtr);  //不涉及 hashtable 内存
    return d;
}

dict 析构函数 O(N)

void dictRelease(dict *d) {
    // 删除并清空两个哈希表
    _dictClear(d,&d->ht[0],NULL);
    _dictClear(d,&d->ht[1],NULL);
    // 释放节点结构
    zfree(d);
}

void dictEmpty(dict *d, void(callback)(void*)) {
    // 删除并清空两个哈希表
    _dictClear(d,&d->ht[0],callback);
    _dictClear(d,&d->ht[1],callback);
    // 重置属性 
    d->rehashidx = -1;
    d->iterators = 0;
}

hashtable 构造函数 O(1)

int dictExpand(dict *d, unsigned long size) {
    dictht n;  																			// 新哈希表
    unsigned long realsize = _dictNextPower(size); // 根据 size 参数，计算哈希表的大小
    // 不能在字典正在 rehash 时进行
    // 新 size 的值也不能小于 0 号哈希表的当前已使用节点
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));// 为哈希表分配空间，并将所有指针指向 NULL
    n.used = 0;
    if (d->ht[0].table == NULL) { 	// 如果 0 号哈希表为空，那么这是一次初始化：
        d->ht[0] = n;				//程序将新哈希表赋给 0 号哈希表的指针，然后字典就可以开始处理键值对了。
        return DICT_OK;
    }
    // 否则这是一次 rehash ：
    d->ht[1] = n;  					// 程序将新哈希表设置为 1 号哈希表，
    d->rehashidx = 0;				// 并将字典的 rehash 标识打开，让程序可以开始对字典进行 rehash
    return DICT_OK;
	// 此函数并没初始化kv 或者 rehash kv，因此 O(1)
}

dict resize O(1)

用于初始化hashtable 或者 rehash

int dictResize(dict *d) {
    int minimal;
    // 不能在关闭 rehash 或者正在 rehash 的时候调用
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    // 计算让比率接近 1：1 所需要的最少节点数量
    minimal = d->ht[0].used;
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal); // 调整字典的大小 O(1)
}

rehash O(m)

int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;   	// 只可以在 rehash 进行中时执行
    while(n--) {  							// 进行 N 步迁移，N 为函数参数，N 为槽的个数
        dictEntry *de, *nextde;
        if (d->ht[0].used == 0) {			// 如果旧 0 号哈希表为空，那么表示 rehash 执行完毕
            zfree(d->ht[0].table); 			// 释放旧 0 号哈希表
            d->ht[0] = d->ht[1];			// 0 号哈希表 指向 rehash 完毕的 1 号哈希表
            _dictReset(&d->ht[1]); 			// 重置 1 号哈希表
            d->rehashidx = -1;				// 关闭 rehash 标识
            return 0; 						// 返回 0 ，向调用者表示 rehash 已经完成
        }
        // 略过数组中为空的索引，找到下一个非空索引
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
        de = d->ht[0].table[d->rehashidx]; 	// 指向该索引的链表表头节点
        while(de) {  																			
        	// 将链表中的所有节点迁移到新哈希表 T = O(1)
            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++;    																 	
        // 更新 rehash 索引
    }
    return 1;
}

限时rehash

int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();// 记录开始时间
    int rehashes = 0;
    while(dictRehash(d,100)) {// 100 为步长
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break; // 如果时间已过，跳出
    }
    return rehashes;																// 返回rehash数量
}

set k O(1)

dictEntry *dictAddRaw(dict *d, void *key) {
    int index;
    dictEntry *entry;
    dictht *ht;
    // 如果条件允许的话，进行单步 rehash  T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);
    if ((index = _dictKeyIndex(d, key)) == -1) // 计算键在哈希表中的索引值，存在返回null
        return NULL;
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];// rehash 添加到 1 号哈希表，否则 0 号
    entry = zmalloc(sizeof(*entry));				// 为新节点分配空间
    entry->next = ht->table[index];					// 将新节点插入到链表表头
    ht->table[index] = entry;
    ht->used++;										// 更新哈希表已使用节点数量
    dictSetKey(d, entry, key);						// 设置新节点的键
    return entry;
}

set kv O(1)

int dictAdd(dict *d, void *key, void *val) {
    dictEntry *entry = dictAddRaw(d,key);	// 尝试添加键到字典，并返回包含了这个键的新哈希节点
    if (!entry) return DICT_ERR;   			// 键已存在，添加失败
    dictSetVal(d, entry, val); 				// 键不存在，设置节点的值
    return DICT_OK;
}

get k O(1)

dictEntry *dictFind(dict *d, const void *key) {
    dictEntry *he;
    unsigned int h, idx, table;
    if (d->ht[0].size == 0) return NULL;  		// 空
    // 如果条件允许的话，进行单步 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);					// 计算键的哈希值
    for (table = 0; table <= 1; table++) {		// 在字典的哈希表中查找这个键
        idx = h & d->ht[table].sizemask;		// 计算索引值
        he = d->ht[table].table[idx];			// 遍历给定索引上的链表的所有节点，查找 key
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;	// 没找到， rehash时 继续查找 1 号哈希表
    }
    return NULL;   																// 进行到这里时，说明两个哈希表都没找到
}

void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;
    he = dictFind(d,key);
    return he ? dictGetVal(he) : NULL;
}

update k O(1)

dictEntry *dictReplaceRaw(dict *d, void *key) {
    dictEntry *entry = dictFind(d,key);
    return entry ? entry : dictAddRaw(d,key); //存在直接返回节点，不存在新建节点
}

update kv O(1)

int dictReplace(dict *d, void *key, void *val) {
    dictEntry *entry, auxentry;
    // 尝试set
    if (dictAdd(d, key, val) == DICT_OK)
        return 1;
    // key 已经存在
    entry = dictFind(d, key);
    auxentry = *entry; 				// 先保存原有的值的指针
    dictSetVal(d, entry, val);   	// 然后设置新的值
    dictFreeVal(d, &auxentry);   	// 然后释放旧值
    return 0;
}

delete kv O(1)

static int dictGenericDelete(dict *d, const void *key, int nofree) {
    unsigned int h, idx;
    dictEntry *he, *prevHe;
    int table;
    if (d->ht[0].size == 0) return DICT_ERR; 	// 空
    // 进行单步 rehash ，T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);					// 计算哈希值
    for (table = 0; table <= 1; table++) { 		// 选择哈希表  T = O(1)
        idx = h & d->ht[table].sizemask;		// 计算索引值 
        he = d->ht[table].table[idx];			// 指向该索引上的链表
        prevHe = NULL;
        while(he) { 							// 遍历链表上的所有节点  T = O(1)
            if (dictCompareKeys(d, key, he->key)) { // 超找目标节点
                if (prevHe) 						// 从链表中删除
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                if (!nofree) {						// 释放调用键和值的释放函数？
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);							// 释放节点本身
                d->ht[table].used--;				// 更新已使用节点数量
                return DICT_OK; 					// 返回已找到信号
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;				// 没找到， rehash时 继续查找 1 号哈希表
    }
    return DICT_ERR; 																// 没找到
}

int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0);
}
int dictDeleteNoFree(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,1);
}

get iter O(1)

dictIterator *dictGetIterator(dict *d) {
    dictIterator *iter = zmalloc(sizeof(*iter));
    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

dictIterator *dictGetSafeIterator(dict *d) {
    dictIterator *i = dictGetIterator(d);
    i->safe = 1;
    return i;
}

delete iter O(1)

void dictReleaseIterator(dictIterator *iter) {
    if (!(iter->index == -1 && iter->table == 0)) {
        if (iter->safe)		// 释放安全迭代器时，安全迭代器计数器减一
            iter->d->iterators--;
        else				// 释放不安全迭代器时，验证指纹是否有变化
            assert(iter->fingerprint == dictFingerprint(iter->d));
    }
    zfree(iter);
}

迭代 O(1)

dictEntry *dictNext(dictIterator *iter) {
    while (1) {
        // 指向下个候选节点，待下面查
        if (iter->entry == NULL) { // 1) 第一次迭代 2) 链表迭代完成，寻找下个链表
            dictht *ht = &iter->d->ht[iter->table];		// 被迭代的哈希表
            if (iter->index == -1 && iter->table == 0) {// 第一次迭代
                if (iter->safe) 						// 迭代时更新计数
                    iter->d->iterators++;
                else									// 否则计算指纹
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            iter->index++;								// 迭代时增加index
            if (iter->index >= (signed) ht->size) {		// 当索引大于大小时，迭代完毕
                if (dictIsRehashing(iter->d) && iter->table == 0) {// 如果还有1号hashtable
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                } else {								// 迭代彻底完成
                    break;
                }
            }
            iter->entry = ht->table[iter->index];		// 指向 index 的链表头，交给下面判断
        } else {
            iter->entry = iter->nextEntry;				// 正在迭代某个链表，指向链表的下个节点
        }
        if (iter->entry) {								// 如果不为空，记录链表下个节点，返回
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }
    return NULL; // 迭代完毕
}

dict 随机key O(1)

dictEntry *dictGetRandomKey(dict *d) {
    dictEntry *he, *orighe;
    unsigned int h;
    int listlen, listele;
    // 字典为空
    if (dictSize(d) == 0) return NULL;
    // 进行单步 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    if (dictIsRehashing(d)) {// rehash ，1 号 hashtable 也算在内
        do {
            h = random() % (d->ht[0].size+d->ht[1].size);
            he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
                                      d->ht[0].table[h];
        } while(he == NULL);
    } else { // 否则，只算 0 号 hashtable
        do {
            h = random() & d->ht[0].sizemask;
            he = d->ht[0].table[h];
        } while(he == NULL);
    }
    listlen = 0;// 从这个链表随机返回一个节点
    orighe = he;
    while(he) { // 链表长度
        he = he->next;
        listlen++;
    }
    listele = random() % listlen;// 链表内索引
    he = orighe;
    while(listele--) he = he->next; // 按索引查找节点
    return he;// 返回随机节点
}

int dictGetRandomKeys(dict *d, dictEntry **des, int count) {
    int j; 			// hashtable id
    int stored = 0; // 返回数量
    if (dictSize(d) < count) count = dictSize(d);//  不超过 dictsize
    while(stored < count) {
        for (j = 0; j < 2; j++) {// 0 1 顺序遍历
            unsigned int i = random() & d->ht[j].sizemask; 	// 随机 index，只取 1 次
            int size = d->ht[j].size;
            while(size--) {// 从 index 处的链表开始，一致向后迭代至 count 个
                dictEntry *he = d->ht[j].table[i];
                while (he) {
                    *des = he;
                    des++;
                    he = he->next;
                    stored++;
                    if (stored == count) return stored;
                }
                i = (i+1) & d->ht[j].sizemask;
            }
            assert(dictIsRehashing(d) != 0);
        }
    }
    return stored;
}

dict scan O(1)

// helper 函数，留坑待填
/* Function to reverse bits. Algorithm from:
 * http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
static unsigned long rev(unsigned long v) {
    unsigned long s = 8 * sizeof(v); 
    unsigned long mask = ~0;
    while ((s >>= 1) > 0) {
        mask ^= (mask << s);
        v = ((v >> s) & mask) | ((v << s) & ~mask);
    }
    return v;
}
// 只迭代 v 的链表，并返回下次迭代的下标
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata) {
    dictht *t0, *t1;
    const dictEntry *de;
    unsigned long m0, m1;
    if (dictSize(d) == 0) return 0;	// 跳过空字典
    if (!dictIsRehashing(d)) { 		// 迭代只有一个哈希表的字典
        t0 = &(d->ht[0]); 			// 指向哈希表
        m0 = t0->sizemask;			// 记录 mask
        de = t0->table[v & m0];		// 指向哈希桶
        while (de) {  				// 遍历桶中的所有节点
            fn(privdata, de);
            de = de->next;
        }
    } else {						// 迭代有两个哈希表的字典，指向两个哈希表
        t0 = &d->ht[0];								
        t1 = &d->ht[1];
        if (t0->size > t1->size) {	// 确保 t0 比 t1 要小
            t0 = &d->ht[1];
            t1 = &d->ht[0];
        }
        m0 = t0->sizemask;			// 记录掩码
        m1 = t1->sizemask;
        de = t0->table[v & m0];		// 指向桶，并迭代桶中的所有节点
        while (de) {
            fn(privdata, de);
            de = de->next;
        }
        do {						// 迭代大表中的桶，这些桶被索引的 expansion 所指向
            de = t1->table[v & m1];	// 指向桶，并迭代桶中的所有节点
            while (de) {
                fn(privdata, de);
                de = de->next;
            }
            v = (((v | m0) + 1) & ~m0) | (v & m0);
        } while (v & (m0 ^ m1));
    }
    v |= ~m0;
    v = rev(v);
    v++;
    v = rev(v);
    return v;
}