redis源码6--字典Dict：查找、删除、随机获取key等

主要函数

//返回字典中包含键 key 的节点，找到返回节点，找不到返回 NULL
dictEntry *dictFind(dict *d, const void *key)
// 如果给定key不存在，将key插入到字典，如果key存在，返回该key的字典节点
dictEntry *dictReplaceRaw(dict *d, void *key) 
//查找并删除包含给定键的节点，参数 nofree 决定是否调用键和值的释放函数。0 表示调用，1 表示不调用
static int dictGenericDelete(dict *d, const void *key, int nofree)
//从字典中删除包含给定键的节点，并且调用键值的释放函数来删除键值
int dictDelete(dict *ht, const void *key) 
//从字典中删除包含给定键的节点，但不调用键值的释放函数来删除键值
int dictDeleteNoFree(dict *ht, const void *key)
//删除哈希表上的所有节点，并重置哈希表的各项属性
int _dictClear(dict *d, dictht *ht, void(callback)(void *))
//删除并释放整个字典
void dictRelease(dict *d)
//清空字典上的所有哈希表节点，并重置字典属性
void dictEmpty(dict *d, void(callback)(void*))
//获取包含给定键的节点的值
void *dictFetchValue(dict *d, const void *key)
//随机返回字典中任意一个节点。可用于实现随机化算法。
dictEntry *dictGetRandomKey(dict *d)
//返回连续的count个节点，开头的节点随机，要保证des有充足的空间
int dictGetRandomKeys(dict *d, dictEntry **des, int count)

dictFind

返回字典中包含键 key 的节点，找到返回节点，找不到返回 NULL

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);
  // 在字典的哈希表中查找这个键
  // T = O(1)
  for (table = 0; table <= 1; table++) {

    // 计算索引值
    idx = h & d->ht[table].sizemask;

    // 遍历给定索引上的链表的所有节点，查找 key
    he = d->ht[table].table[idx];
    // T = O(1)
    while(he) {

        if (dictCompareKeys(d, key, he->key))
            return he;

        he = he->next;
    }

    // 如果程序遍历完 0 号哈希表，仍然没找到指定的键的节点
    // 那么程序会检查字典是否在进行 rehash ，
    // 如果正在rehash，继续查找1号哈希表，否则返回NULL
    if (!dictIsRehashing(d)) return NULL;
  }

  // 进行到这里时，说明两个哈希表都没找到
  return NULL;
}

dictReplace

将给定的键值对添加到字典中，如果键已经存在，那么删除旧有的键值对。
如果键值对为全新添加，那么返回 1 。
如果键值对是通过对原有的键值对更新得来的，那么返回 0 。
T = O(N)

int dictReplace(dict *d, void *key, void *val)
{
  dictEntry *entry, auxentry;

  // 尝试直接将键值对添加到字典
  // 如果键 key 不存在的话，添加会成功
  // T = O(N)
  if (dictAdd(d, key, val) == DICT_OK)
    return 1;

  // 运行到这里，说明键 key 已经存在，那么找出包含这个 key 的节点
  // T = O(1)
  entry = dictFind(d, key);

  // 先保存原有的值的指针
  auxentry = *entry;
  // 然后设置新的值
  // T = O(1)
  dictSetVal(d, entry, val);
  // 然后释放旧值
  // T = O(1)
  dictFreeVal(d, &auxentry);

  return 0;
}

dictReplaceRaw

如果给定key不存在，将key插入到字典，如果key存在，返回该key的字典节点

dictEntry *dictReplaceRaw(dict *d, void *key) {

  // 使用 key 在字典中查找节点
  // T = O(1)
  dictEntry *entry = dictFind(d,key);

  // 如果节点找到了直接返回节点，否则添加并返回一个新节点
  // T = O(N)
  return entry ? entry : dictAddRaw(d,key);
}

dictGenericDelete

静态函数，查找并删除包含给定键的节点
参数 nofree 决定是否调用键和值的释放函数，0 表示调用，1 表示不调用
找到并成功删除返回 DICT_OK ，没找到则返回 DICT_ERR
T = 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; /* d->ht[0].table is NULL */

  // 进行单步 rehash ，T = O(1)
  if (dictIsRehashing(d)) _dictRehashStep(d);

  // 计算哈希值
  h = dictHashKey(d, key);

  // 遍历哈希表
  // T = O(1)
  for (table = 0; table <= 1; table++) {

    // 计算索引值 
    idx = h & d->ht[table].sizemask;
    // 指向该索引上的链表
    he = d->ht[table].table[idx];
    prevHe = NULL;
    // 遍历链表上的所有节点
    // T = O(1)
    while(he) {
    
        if (dictCompareKeys(d, key, he->key)) {
            // 超找目标节点

            /* Unlink the element from the list */
            // 从链表中删除
            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;
    }

    // 如果执行到这里，说明在 0 号哈希表中找不到给定键
    // 那么根据字典是否正在进行 rehash ，决定要不要查找 1 号哈希表
    if (!dictIsRehashing(d)) break;
  }

  // 没找到
  return DICT_ERR; /* not found */
}

dictDelete

从字典中删除包含给定键的节点，并且调用键值的释放函数来删除键值

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

dictDeleteNoFree

从字典中删除包含给定键的节点，但不调用键值的释放函数来删除键值

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

_dictClear

删除哈希表上的所有节点，并重置哈希表的各项属性
T = O(N)

int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
  unsigned long i;

  // 遍历整个哈希表
  // T = O(N)
  for (i = 0; i < ht->size && ht->used > 0; i++) {
    dictEntry *he, *nextHe;

    if (callback && (i & 65535) == 0) callback(d->privdata);

    // 跳过空索引
    if ((he = ht->table[i]) == NULL) continue;

    // 遍历整个链表
    // T = O(1)
    while(he) {
        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 */
}

dictRelease

删除并释放整个字典
T = O(N)

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

dictEmpty

清空字典上的所有哈希表节点，并重置字典属性

void dictEmpty(dict *d, void(callback)(void*)) {

  // 删除两个哈希表上的所有节点
  // T = O(N)
  _dictClear(d,&d->ht[0],callback);
  _dictClear(d,&d->ht[1],callback);
  // 重置属性 
  d->rehashidx = -1;
  d->iterators = 0;
}

dictFetchValue

获取包含给定键的节点的值
如果节点不为空，返回节点的值，否则返回 NULL
T = O(1)

void *dictFetchValue(dict *d, const void *key) {
  dictEntry *he;

  // T = O(1)
  he = dictFind(d,key);

  return he ? dictGetVal(he) : NULL;
}

dictGetRandomKey

随机返回字典中任意一个节点。可用于实现随机化算法。如果字典为空，返回 NULL 。
T = O(N)

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

  // 如果正在 rehash ，那么将 1 号哈希表也作为随机查找的目标
  if (dictIsRehashing(d)) {
    // T = O(N)
    do {
        //随机取一个索引，范围在两个哈希表的size相加的区间内，相当于将两个哈希表的table拼接起来，ht[0]作为前半段，ht[1]作为后半段
        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);
  // 否则，只从 0 号哈希表中查找节点
  } else {
    // T = O(N)
    do {
        h = random() & d->ht[0].sizemask;
        he = d->ht[0].table[h];
    } while(he == NULL);
  }

 // 目前 he 已经指向一个非空的节点链表
  // 程序将从这个链表随机返回一个节点
  listlen = 0;
  orighe = he;
  // 计算节点数量, T = O(1)
  while(he) {
    he = he->next;
    listlen++;
  }
  // 取模，得出随机节点的索引
  listele = random() % listlen;
  he = orighe;
  // 按索引查找节点
  // T = O(1)
  while(listele--) he = he->next;

  // 返回随机节点
  return he;
}

dictGetRandomKeys

返回count个连续的节点，第一个节点随机取，然后直接取第一个节点后面的count -1 个，函数调用时，要保证des有充足的空间

int dictGetRandomKeys(dict *d, dictEntry **des, int count) {
  //哈希表下标
  int j; 
   //用于判断取到的节点数量是否足够了
  int stored = 0;
  //当字典没有那么多节点时，调整count
  if (dictSize(d) < count) count = dictSize(d);

  while(stored < count) {
    for (j = 0; j < 2; j++) {
       //随机取一个索引
        unsigned int i = random() & d->ht[j].sizemask;
        int size = d->ht[j].size;

        //遍历该哈希表的所有索引
        while(size--) {
            //指向该索引链表的第一个节点
            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;
        }
        //如果想访问ht[1]哈希表，需要字典正在进行 rehash，不然不能访问ht[1]
        assert(dictIsRehashing(d) != 0);
    }
  }
  return stored; /* Never reached. */
}