Redis源碼剖析 - Redis內置數據結構之字典dict

哈希表在C++中對應的是map數據結構，但在Redis中稱作dict（字典）。Redis只是用了幾個簡單的結構體和幾種常見的哈希算法就實現了一個簡單的類似高級語言中的map結構。下面我們來具體分析一下dict的實現。

redis源碼剖析訓練營主講內容包含8個技術點：

1：數據存儲分析

2：redis存儲原理

3：redis事件機制

4：redis6.0-IO多線程

5：redis有序集合的實現-跳表

6：跳表的應用以及與其他動態有序搜索結構比較

7：redis-driver實現

8：redis高可用部署策略

redis源碼剖析訓練營學習地址可以後臺私信「redis」

---

在學習數據結構的時候，我們接觸過一種稱作「散列表」的結構，可以根據關鍵字而直接訪問記錄。說的具體一點就是通過把key值映射到表中的一個位置來訪問，從而加快查找速度。Redis中的dict數據結構和我們之前學過的「散列表」大同小異。總結如下：

1、dict的結構

Redis定義了dictEntry、dictType、dictht和dict四個結構體來實現散列表的功能。它們具體定義如下：

（1）dictEntry結構體

/* 保存鍵值（key - value）對的結構體，類似於STL的pair。*/typedef struct dictEntry { // 關鍵字key定義 void *key; // 值value定義，只能存放一個被選中的成員 union { void *val; uint64_t u64; int64_t s64; double d; } v; // 指向下一個鍵值對節點 struct dictEntry *next;} dictEntry;

從dictEntry的定義我們也可以看出dict通過「拉鏈法」來解決衝突問題。

（2）、dictType結構體

/* 定義了字典操作的公共方法，類似於adlist.h文件中list的定義，將對節點的公共操作方法統一定義。搞不明白為什麼要命名為dictType */typedef struct dictType { /* hash方法，根據關鍵字計算哈希值 */ unsigned int (*hashFunction)(const void *key); /* 複製key */ void *(*keyDup)(void *privdata, const void *key); /* 複製value */ void *(*valDup)(void *privdata, const void *obj); /* 關鍵字比較方法 */ int (*keyCompare)(void *privdata, const void *key1, const void *key2); /* 銷毀key */ void (*keyDestructor)(void *privdata, void *key); /* 銷毀value */ void (*valDestructor)(void *privdata, void *obj);} dictType;

（3）、dictht結構體

/* 哈希表結構 */typedef struct dictht { // 散列數組。 dictEntry **table; // 散列數組的長度 unsigned long size; // sizemask等於size減1 unsigned long sizemask; // 散列數組中已經被使用的節點數量 unsigned long used;} dictht;

（4）、dict結構體

/* 字典的主操作類，對dictht結構再次包裝 */typedef struct dict { // 字典類型 dictType *type; // 私有數據 void *privdata; // 一個字典中有兩個哈希表 dictht ht[2]; // 數據動態遷移的下標位置 long rehashidx; // 當前正在使用的迭代器的數量 int iterators; } dict;

這四個結構體之間的關係如下：

2、散列函數

Redis提供了三種不同的散列函數，分別是：

（1）、使用Thomas Wang’s 32 bit Mix哈希算法，對一個整型進行哈希，該方法在dictIntHashFunction函數中實現。
（2）、使用MurmurHash2哈希算法對字符串進行哈希，該方法在dictGenHashFunction函數中實現。
（3）、在dictGenCaseHashFunction函數中提供了一種比較簡單的哈希算法，對字符串進行哈希

上面這三種方法的實現具體可以參考下面的代碼。至於這幾種方法的優劣，這裡就不展開講了（我自己也不是很清楚），大家可以自行google一下。

3、Rehash操作

Rehash是dict一個很重要的操作。在前面我們看到dict結構體中有兩個哈希表（定義為dictht ht[2]）。通常情況下，dict中的所有數據（鍵值對）都存放在ht[0]，但隨著dict中數據量的增加需要進行擴容操作（為什麼？數據越多，衝突的元素越多，ht[0]中的鍊表越長，查找效率越低），此時就需要進行rehash。dict在rehash的時先申請一個更大的空間並用ht[1]指向該空間，然後把ht[0]中的所有數據rehash到ht[1]中，數據遷移完畢後在將ht[1]賦值給ht[0]並清空ht[1]。如果這個rehash過程是一次性完成的倒是很好理解，但從其源碼中我們可以看出：dict的rehash操作並不是一次性完成的，而是分成多步。具體來說dict提供了兩種不同的策略：一種是每次將ht[0]中的一個bucket，也就是散列數組中對應的一個鍊表中的所有數據進行rehash到ht[1]中，對應的函數是_dictRehashStep。另一種是每次執行一段固定的時間，時間到了就暫停rehash操作，對應的函數是dictRehashMilliseconds。

_dictRehashStep和dictRehashMilliseconds底層都調用了dictRehash函數來進行rehash操作。實現如下：

/* 執行n步漸進式的rehash操作，如果還有key需要從舊錶遷移到新表則返回1，否則返回0 */int dictRehash(dict *d, int n) { if (!dictIsRehashing(d)) return 0; // n步漸進式的rehash操作就是每次只遷移哈希數組中的n個bucket while(n--) { dictEntry *de, *nextde; /* Check if we already rehashed the whole table... */ // 檢查是否對整個哈希表進行了rehash操作 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; } /* Note that rehashidx can&34;AS IS&include <stdint.h>define __DICT_H// 成功 or 出錯define DICT_ERR 1/* Unused arguments generate annoying warnings... */define DICT_HT_INITIAL_SIZE 4/* 下面是節點（鍵值對）操作的宏定義 *//* ------------------------------- Macros ------------------------------------*//* 釋放節點value，實際上調用dictType中的valDestructor函數 */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)/* 設置節點的值value，類型為signed int */define dictSetUnsignedIntegerVal(entry, _val_) \ do { entry->v.u64 = _val_; } while(0)/* 設置節點的值value，類型為double */define dictFreeKey(d, entry) \ if ((d)->type->keyDestructor) \ (d)->type->keyDestructor((d)->privdata, (entry)->key)/* 設置節點的鍵key */define dictCompareKeys(d, key1, key2) \ (((d)->type->keyCompare) ? \ (d)->type->keyCompare((d)->privdata, key1, key2) : \ (key1) == (key2))/* 獲取指定key的哈希值*/define dictGetKey(he) ((he)->key)/* 獲取節點的value值 */define dictGetSignedIntegerVal(he) ((he)->v.s64)/* 獲取節點的value值，類型為unsigned int */define dictGetDoubleVal(he) ((he)->v.d)/* 獲取字典中哈希表的總長度 */define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)/* 判斷字典dict是否正在執行rehash操作 */endif /* __DICT_H */

dict.c源文件：

/* Hash Tables Implementation. * * This file implements in memory hash tables with insert/del/replace/find/ * get-random-element operations. Hash tables will auto resize if needed * tables of power of two in size are used, collisions are handled by * chaining. See the source code for more information... :) * * Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com> * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * Neither the name of Redis nor the names of its contributors may be used * to endorse or promote products derived from this software without * specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS &34; * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */34;fmacros.h&include <stdio.h>include <string.h>include <limits.h>include <ctype.h>34;dict.h&include &34;34;redisassert.h&39;t want to move too much memory * around when there is a child performing saving operations. * * Note that even when dict_can_resize is set to 0, not all resizes are * prevented: a hash table is still allowed to grow if the ratio between * the number of elements and the buckets > dict_force_resize_ratio. *//*通過dictEnableResize() / dictDisableResize()方法我們可以啟用/禁用ht空間重新分配. * 這對於Redis來說很重要, 因為我們用的是寫時複製機制而且不想在子進程執行保存操作時移動過多的內存. * * 需要注意的是，即使dict_can_resize設置為0, 並不意味著所有的resize操作都被禁止: * 一個a hash table仍然可以拓展空間，如果bucket與element數量之間的比例 > dict_force_resize_ratio。 */ static int dict_can_resize = 1;static unsigned int dict_force_resize_ratio = 5;/* -------------------------- private prototypes ---------------------------- *//** 下面的方法由static修飾，是私有方法 */// 判斷字典dict是否需要擴容static int _dictExpandIfNeeded(dict *ht);// 由於哈希表的容量只取2的整數次冪，該函數對給定數字以2的整數次冪進行上取整static unsigned long _dictNextPower(unsigned long size);// 返回給定新key的對應空閒的索引地址static int _dictKeyIndex(dict *ht, const void *key);// 字典的初始化static int _dictInit(dict *ht, dictType *type, void *privDataPtr);/* -------------------------- hash functions -------------------------------- *//* Thomas Wang&39;s 32 bit Mix哈希算法，對一個整型進行哈希。這是一種基於移位運算的哈希算法，直接根據 給定的key值進行移位操作，具有比較高的效率*/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;}// 哈希種子，跟產生隨機數的種子類似static uint32_t dict_hash_function_seed = 5381;// 設置新的哈希種子void dictSetHashFunctionSeed(uint32_t seed) { dict_hash_function_seed = seed;}// 獲取當前哈希種子的數值uint32_t dictGetHashFunctionSeed(void) { return dict_hash_function_seed;}/* MurmurHash2, by Austin Appleby * Note - This code makes a few assumptions about how your machine behaves - * 1. We can read a 4-byte value from any address without crashing * 2. sizeof(int) == 4 * * And it has a few limitations - * * 1. It will not work incrementally. * 2. It will not produce the same results on little-endian and big-endian * machines. */ /* MurmurHash2哈希算法，我也不知道是什麼東東。網上資料顯示MurmurHash2主要對一個字符串進行哈希，其 基本思想是將給定的key按每四個字符分組，每四個字符當做一個uint32_t整形進行處理。 */// MurmurHash2哈希算法的實現，根據key值和指定長度進行哈希unsigned int dictGenHashFunction(const void *key, int len) { /* &39; and &39; are mixing constants generated offline. They&39;magic&39;random&39;s not really a rehashing * we just set the first hash table so that it can accept keys. */ // 如果舊錶為空，則這並不是一次rehashing操作，直接將新的哈希表賦值給舊錶指針 if (d->ht[0].table == NULL) { d->ht[0] = n; return DICT_OK; } /* Prepare a second hash table for incremental rehashing */ /* 將新創建的哈希表賦值給ht[1]，rehashidx設置為0，準備進行漸進式的rehash操作 */ d->ht[1] = n; d->rehashidx = 0; return DICT_OK;}/* Performs N steps of incremental rehashing. Returns 1 if there are still * keys to move from the old to the new hash table, otherwise 0 is returned. * Note that a rehashing step consists in moving a bucket (that may have more * than one key as we use chaining) from the old to the new hash table. *//* 執行n步漸進式的rehash操作，如果還有key需要從舊錶遷移到新表則返回1，否則返回0 */int dictRehash(dict *d, int n) { if (!dictIsRehashing(d)) return 0; // n步漸進式的rehash操作就是每次只遷移哈希數組中的n歌元素 while(n--) { dictEntry *de, *nextde; /* Check if we already rehashed the whole table... */ // 檢查是否對整個哈希表進行了rehash操作 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; } /* Note that rehashidx can&39;t mess with the two hash tables otherwise * some element can be missed or duplicated. * * This function is called by common lookup or update operations in the * dictionary so that the hash table automatically migrates from H1 to H2 * while it is actively used. */ /* 在執行查詢或更新操作時，如果符合rehash條件會觸發一次rehash操作，每次執行一步 */static void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1);}/* Add an element to the target hash table *//* 往字典中添加一個新的鍵值對 */int dictAdd(dict *d, void *key, void *val){ // 往字典中添加一個只有key的dictEntry結構 dictEntry *entry = dictAddRaw(d,key); // 如果entry == NULL，說明該key已經存在，添加失敗 if (!entry) return DICT_ERR; // 設置對應的value dictSetVal(d, entry, val); return DICT_OK;}/* Low level add. This function adds the entry but instead of setting * a value returns the dictEntry structure to the user, that will make * sure to fill the value field as he wishes. * * This function is also directly exposed to user API to be called * mainly in order to store non-pointers inside the hash value, example: * * entry = dictAddRaw(dict,mykey); * if (entry != NULL) dictSetSignedIntegerVal(entry,1000); * * Return values: * * If key already exists NULL is returned. * If key was added, the hash entry is returned to be manipulated by the caller. */ /* dictAdd的底層實現方法。往字典中添加一個只有key的dictEntry結構，如果給定的key已經存在，則返回NULL */dictEntry *dictAddRaw(dict *d, void *key){ int index; dictEntry *entry; dictht *ht; // 觸發rehash操作 if (dictIsRehashing(d)) _dictRehashStep(d); /* Get the index of the new element, or -1 if * the element already exists. */ // 如果給定key已經存在，則操作失敗直接返回NULL if ((index = _dictKeyIndex(d, key)) == -1) return NULL; /* Allocate the memory and store the new entry */ // 如果字典正在rehash，則插入到新表ht[1]，否則插入到舊錶ht[0] ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; entry = zmalloc(sizeof(*entry)); // 使用拉鏈法處理衝突 entry->next = ht->table[index]; ht->table[index] = entry; // 更新鍵值對數量 ht->used++; /* Set the hash entry fields. */ dictSetKey(d, entry, key); return entry;}/* Add an element, discarding the old if the key already exists. * Return 1 if the key was added from scratch, 0 if there was already an * element with such key and dictReplace() just performed a value update * operation. */ /* 添加或替換字典中的鍵值對，如果返回值為1，表示執行了添加操作，如果返回值是0，表示執行了替換操作 */int dictReplace(dict *d, void *key, void *val){ dictEntry *entry, auxentry; /* Try to add the element. If the key * does not exists dictAdd will suceed. */ // 現場時添加一個鍵值對，如果添加成功則直接返回，否則執行替換操作 if (dictAdd(d, key, val) == DICT_OK) return 1; /* It already exists, get the entry */ // 根據key找到鍵值對節點 entry = dictFind(d, key); /* Set the new value and free the old one. Note that it is important * to do that in this order, as the value may just be exactly the same * as the previous one. In this context, think to reference counting, * you want to increment (set), and then decrement (free), and not the * reverse. */ // 設置新值，釋放舊值。需要考慮value是同一個的情況 auxentry = *entry; dictSetVal(d, entry, val); dictFreeVal(d, &auxentry); return 0;}/* dictReplaceRaw() is simply a version of dictAddRaw() that always * returns the hash entry of the specified key, even if the key already * exists and can&39;t have a table at all */ 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]; while(he) { if (dictCompareKeys(d, key, he->key)) return he; he = he->next; } if (!dictIsRehashing(d)) return NULL; } return NULL;}/* 根據給定key獲取對應的value */void *dictFetchValue(dict *d, const void *key) { dictEntry *he; he = dictFind(d,key); return he ? dictGetVal(he) : NULL;}/* A fingerprint is a 64 bit number that represents the state of the dictionary * at a given time, it&39;s 64 bit integer hash. */ hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1; hash = hash ^ (hash >> 24); hash = (hash + (hash << 3)) + (hash << 8); // hash * 265 hash = hash ^ (hash >> 14); hash = (hash + (hash << 2)) + (hash << 4); // hash * 21 hash = hash ^ (hash >> 28); hash = hash + (hash << 31); } return hash;}/* 初始化一個普通迭代器 */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;}dictEntry *dictNext(dictIterator *iter){ while (1) { if (iter->entry == NULL) { // 首次迭代需要初始化entry屬性 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++; if (iter->index >= (long) ht->size) { // 如果正在執行rehash操作，則要處理從舊錶ht[0]到ht[1]的情形 if (dictIsRehashing(iter->d) && iter->table == 0) { iter->table++; iter->index = 0; ht = &iter->d->ht[1]; } else { break; } } iter->entry = ht->table[iter->index]; } else { iter->entry = iter->nextEntry; } if (iter->entry) { /* We need to save the &39; here, the iterator user * may delete the entry we are returning. */ iter->nextEntry = iter->entry->next; return iter->entry; } } return NULL;}/* 釋放迭代器 */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);}/* Return a random entry from the hash table. Useful to * implement randomized algorithms *//* 從字典dict中隨機返回一個鍵值對，需要使用隨機函數 */dictEntry *dictGetRandomKey(dict *d){ dictEntry *he, *orighe; unsigned int h; int listlen, listele; // 如果字典dict沒有任何元素，直接返回 if (dictSize(d) == 0) return NULL; // 觸發一次rehash操作 if (dictIsRehashing(d)) _dictRehashStep(d); /* 下面的做法是先隨機選取散列數組中的一個槽，這樣就得到一個鍊表（如果該槽中沒有元素則重新選取）， 然後在該列表中隨機選取一個鍵值對返回 */ if (dictIsRehashing(d)) { // 如果字典正在rehash，則舊錶ht[0]和新表ht[1]中都有數據 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 { do { h = random() & d->ht[0].sizemask; he = d->ht[0].table[h]; } while(he == NULL); } /* Now we found a non empty bucket, but it is a linked * list and we need to get a random element from the list. * The only sane way to do so is counting the elements and * select a random index. */ /* 從鍊表中選取一個鍵值對 */ listlen = 0; orighe = he; // 統計元素個數 while(he) { he = he->next; listlen++; } // 隨機選取下標 listele = random() % listlen; he = orighe; // 找到對應元素 while(listele--) he = he->next; return he;}/* Function to reverse bits. Algorithm from: * http://graphics.stanford.edu/~seander/bithacks.html39;fn&39;privdata&39;de&39;s say we already iterated with * a 4 bit cursor 1100 (the mask is 1111 because hash table size = 16). * * If the hash table will be resized to 64 elements, then the new mask will * be 111111. The new buckets you obtain by substituting in ??1100 * with either 0 or 1 can be targeted only by keys we already visited * when scanning the bucket 1100 in the smaller hash table. * * By iterating the higher bits first, because of the inverted counter, the * cursor does not need to restart if the table size gets bigger. It will * continue iterating using cursors without &39; at the end, and also * without any other combination of the final 4 bits already explored. * * Similarly when the table size shrinks over time, for example going from * 16 to 8, if a combination of the lower three bits (the mask for size 8 * is 111) were already completely explored, it would not be visited again * because we are sure we tried, for example, both 0111 and 1111 (all the * variations of the higher bit) so we don&39;t miss keys moving during rehashing. * 3) The reverse cursor is somewhat hard to understand at first, but this * comment is supposed to help. */ /* 遍歷字典dict中的每個鍵值對並執行指定的回調函數 */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; /* Emit entries at cursor */ de = t0->table[v & m0]; while (de) { fn(privdata, de); de = de->next; } } else { t0 = &d->ht[0]; t1 = &d->ht[1]; /* Make sure t0 is the smaller and t1 is the bigger table */ if (t0->size > t1->size) { t0 = &d->ht[1]; t1 = &d->ht[0]; } m0 = t0->sizemask; m1 = t1->sizemask; /* Emit entries at cursor */ de = t0->table[v & m0]; while (de) { fn(privdata, de); de = de->next; } /* Iterate over indices in larger table that are the expansion * of the index pointed to by the cursor in the smaller table */ do { /* Emit entries at cursor */ de = t1->table[v & m1]; while (de) { fn(privdata, de); de = de->next; } /* Increment bits not covered by the smaller mask */ v = (((v | m0) + 1) & ~m0) | (v & m0); /* Continue while bits covered by mask difference is non-zero */ } while (v & (m0 ^ m1)); } /* Set unmasked bits so incrementing the reversed cursor * operates on the masked bits of the smaller table */ v |= ~m0; /* Increment the reverse cursor */ v = rev(v); v++; v = rev(v); return v;}/* ------------------------- private functions ------------------------------ *//* Expand the hash table if needed */// 判斷字典dict是否需要擴容static int _dictExpandIfNeeded(dict *d){ /* Incremental rehashing already in progress. Return. */ // 如果正在執行rehash操作，則直接返回 if (dictIsRehashing(d)) return DICT_OK; /* If the hash table is empty expand it to the initial size. */ // 如果字典中哈希表的為空，則為其擴展到初始大小 if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); /* If we reached the 1:1 ratio, and we are allowed to resize the hash * table (global setting) or we should avoid it but the ratio between * elements/buckets is over the &34; threshold, we resize doubling * the number of buckets. */ // 如果滿足下列條件（已用節點數>=節點總數或節點填充率過高），擴容兩倍 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;}/* Our hash table capability is a power of two */// 由於哈希表的容量只取2的整數次冪，該函數對給定數字以2的整數次冪進行上取整static unsigned long _dictNextPower(unsigned long size){ unsigned long i = DICT_HT_INITIAL_SIZE; // 不能超過長整形的最大值 if (size >= LONG_MAX) return LONG_MAX; // 以2的整數次冪進行上取整 while(1) { if (i >= size) return i; i *= 2; }}/* Returns the index of a free slot that can be populated with * a hash entry for the given &39;. * If the key already exists, -1 is returned. * * Note that if we are in the process of rehashing the hash table, the * index is always returned in the context of the second (new) hash table. *//* 返回給定key對應的空閒的索引節點，如果該key已經存在，則返回-1 */static int _dictKeyIndex(dict *d, const void *key){ unsigned int h, idx, table; dictEntry *he; /* Expand the hash table if needed */ if (_dictExpandIfNeeded(d) == DICT_ERR) return -1; /* Compute the key hash value */ // 調用對應的哈希算法獲得給定key的哈希值 h = dictHashKey(d, key); for (table = 0; table <= 1; table++) { idx = h & d->ht[table].sizemask; /* Search if this slot does not already contain the given key */ he = d->ht[table].table[idx]; // 依次比較該slot上的所有鍵值對的key是否和給定key相等 while(he) { if (dictCompareKeys(d, key, he->key)) return -1; he = he->next; } // 如果不是正在執行rehash操作，第二個表為空表，無需繼續查找 if (!dictIsRehashing(d)) break; } return idx;}/* 清空字典數據但不釋放空間 */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;}void dictEnableResize(void) { dict_can_resize = 1;}void dictDisableResize(void) { dict_can_resize = 0;}39;t use for Redis currently, but that is partof the library. *//* ----------------------- Debugging ------------------------*/34;No stats available for empty dictionaries\n&34;Hash table stats:\n&34; table size: %ld\n&34; number of elements: %ld\n&34; different slots: %ld\n&34; max chain length: %ld\n&34; avg chain length (counted): %.02f\n&34; avg chain length (computed): %.02f\n&34; Chain length distribution:\n&34; %s%ld: %ld (%.02f%%)\n&34;>= &34;&34;-- Rehashing into ht[1]:\n&39;\0&39;s used for intepreter&endif