redis源碼6--字典Dict：查找、刪除、隨機獲取key等

主要函數(shù)

//返回字典中包含鍵 key 的節(jié)點，找到返回節(jié)點，找不到返回 NULL
dictEntry *dictFind(dict *d, const void *key)
// 如果給定key不存在，將key插入到字典，如果key存在，返回該key的字典節(jié)點
dictEntry *dictReplaceRaw(dict *d, void *key) 
//查找并刪除包含給定鍵的節(jié)點，參數(shù) nofree 決定是否調(diào)用鍵和值的釋放函數(shù)。0 表示調(diào)用，1 表示不調(diào)用
static int dictGenericDelete(dict *d, const void *key, int nofree)
//從字典中刪除包含給定鍵的節(jié)點，并且調(diào)用鍵值的釋放函數(shù)來刪除鍵值
int dictDelete(dict *ht, const void *key) 
//從字典中刪除包含給定鍵的節(jié)點，但不調(diào)用鍵值的釋放函數(shù)來刪除鍵值
int dictDeleteNoFree(dict *ht, const void *key)
//刪除哈希表上的所有節(jié)點，并重置哈希表的各項屬性
int _dictClear(dict *d, dictht *ht, void(callback)(void *))
//刪除并釋放整個字典
void dictRelease(dict *d)
//清空字典上的所有哈希表節(jié)點，并重置字典屬性
void dictEmpty(dict *d, void(callback)(void*))
//獲取包含給定鍵的節(jié)點的值
void *dictFetchValue(dict *d, const void *key)
//隨機返回字典中任意一個節(jié)點?？捎糜趯崿F(xiàn)隨機化算法。
dictEntry *dictGetRandomKey(dict *d)
//返回連續(xù)的count個節(jié)點，開頭的節(jié)點隨機，要保證des有充足的空間
int dictGetRandomKeys(dict *d, dictEntry **des, int count)

dictFind

返回字典中包含鍵 key 的節(jié)點，找到返回節(jié)點，找不到返回 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;

    // 遍歷給定索引上的鏈表的所有節(jié)點，查找 key
    he = d->ht[table].table[idx];
    // T = O(1)
    while(he) {

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

        he = he->next;
    }

    // 如果程序遍歷完 0 號哈希表，仍然沒找到指定的鍵的節(jié)點
    // 那么程序會檢查字典是否在進行 rehash ，
    // 如果正在rehash，繼續(xù)查找1號哈希表，否則返回NULL
    if (!dictIsRehashing(d)) return NULL;
  }

  // 進行到這里時，說明兩個哈希表都沒找到
  return NULL;
}

dictReplace

將給定的鍵值對添加到字典中，如果鍵已經(jīng)存在，那么刪除舊有的鍵值對。
如果鍵值對為全新添加，那么返回 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 已經(jīng)存在，那么找出包含這個 key 的節(jié)點
  // 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的字典節(jié)點

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

  // 使用 key 在字典中查找節(jié)點
  // T = O(1)
  dictEntry *entry = dictFind(d,key);

  // 如果節(jié)點找到了直接返回節(jié)點，否則添加并返回一個新節(jié)點
  // T = O(N)
  return entry ? entry : dictAddRaw(d,key);
}

dictGenericDelete

靜態(tài)函數(shù)，查找并刪除包含給定鍵的節(jié)點
參數(shù) nofree 決定是否調(diào)用鍵和值的釋放函數(shù)，0 表示調(diào)用，1 表示不調(diào)用
找到并成功刪除返回 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;
    // 遍歷鏈表上的所有節(jié)點
    // T = O(1)
    while(he) {
    
        if (dictCompareKeys(d, key, he->key)) {
            // 超找目標節(jié)點

            /* Unlink the element from the list */
            // 從鏈表中刪除
            if (prevHe)
                prevHe->next = he->next;
            else
                d->ht[table].table[idx] = he->next;

            // 釋放調(diào)用鍵和值的釋放函數(shù)？
            if (!nofree) {
                dictFreeKey(d, he);
                dictFreeVal(d, he);
            }
            
            // 釋放節(jié)點本身
            zfree(he);

            // 更新已使用節(jié)點數(shù)量
            d->ht[table].used--;

            // 返回已找到信號
            return DICT_OK;
        }

        prevHe = he;
        he = he->next;
    }

    // 如果執(zhí)行到這里，說明在 0 號哈希表中找不到給定鍵
    // 那么根據(jù)字典是否正在進行 rehash ，決定要不要查找 1 號哈希表
    if (!dictIsRehashing(d)) break;
  }

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

dictDelete

從字典中刪除包含給定鍵的節(jié)點，并且調(diào)用鍵值的釋放函數(shù)來刪除鍵值

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

dictDeleteNoFree

從字典中刪除包含給定鍵的節(jié)點，但不調(diào)用鍵值的釋放函數(shù)來刪除鍵值

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

_dictClear

刪除哈希表上的所有節(jié)點，并重置哈希表的各項屬性
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);
        // 釋放節(jié)點
        zfree(he);

        // 更新已使用節(jié)點計數(shù)
        ht->used--;

        // 處理下個節(jié)點
        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);
  // 釋放節(jié)點結構
  zfree(d);
}

dictEmpty

清空字典上的所有哈希表節(jié)點，并重置字典屬性

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

  // 刪除兩個哈希表上的所有節(jié)點
  // T = O(N)
  _dictClear(d,&d->ht[0],callback);
  _dictClear(d,&d->ht[1],callback);
  // 重置屬性 
  d->rehashidx = -1;
  d->iterators = 0;
}

dictFetchValue

獲取包含給定鍵的節(jié)點的值
如果節(jié)點不為空，返回節(jié)點的值，否則返回 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

隨機返回字典中任意一個節(jié)點。可用于實現(xiàn)隨機化算法。如果字典為空，返回 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相加的區(qū)間內(nèi)，相當于將兩個哈希表的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];
        //該索引下可能沒有節(jié)點，所以要繼續(xù)循環(huán)找，直到找到有節(jié)點的索引
    } while(he == NULL);
  // 否則，只從 0 號哈希表中查找節(jié)點
  } else {
    // T = O(N)
    do {
        h = random() & d->ht[0].sizemask;
        he = d->ht[0].table[h];
    } while(he == NULL);
  }

 // 目前 he 已經(jīng)指向一個非空的節(jié)點鏈表
  // 程序將從這個鏈表隨機返回一個節(jié)點
  listlen = 0;
  orighe = he;
  // 計算節(jié)點數(shù)量, T = O(1)
  while(he) {
    he = he->next;
    listlen++;
  }
  // 取模，得出隨機節(jié)點的索引
  listele = random() % listlen;
  he = orighe;
  // 按索引查找節(jié)點
  // T = O(1)
  while(listele--) he = he->next;

  // 返回隨機節(jié)點
  return he;
}

dictGetRandomKeys

返回count個連續(xù)的節(jié)點，第一個節(jié)點隨機取，然后直接取第一個節(jié)點后面的count -1 個，函數(shù)調(diào)用時，要保證des有充足的空間

int dictGetRandomKeys(dict *d, dictEntry **des, int count) {
  //哈希表下標
  int j; 
   //用于判斷取到的節(jié)點數(shù)量是否足夠了
  int stored = 0;
  //當字典沒有那么多節(jié)點時，調(diào)整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--) {
            //指向該索引鏈表的第一個節(jié)點
            dictEntry *he = d->ht[j].table[i];
            while (he) {
                //該索引鏈表中有節(jié)點，取出來
                *des = he;
                des++;
                //指向該鏈表的下一個節(jié)點
                he = he->next;
                stored++;
                //取出的節(jié)點足夠了，函數(shù)返回
                if (stored == count) return stored;
            }
            //如果該索引下沒有節(jié)點，或者索引鏈表下節(jié)點都取出來了，遍歷下一個索引
            i = (i+1) & d->ht[j].sizemask;
        }
        //如果想訪問ht[1]哈希表，需要字典正在進行 rehash，不然不能訪問ht[1]
        assert(dictIsRehashing(d) != 0);
    }
  }
  return stored; /* Never reached. */
}
最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容