介紹 Redis的哈希字典通過key值來找對應的value。需要注意的是Redis的字典是如何進行rehash的。 源碼 dict.h dict.c 數據結構 如上圖所示，哈希字典用dict結構體表示，其中含有兩個哈希表，主要用於進行rehash操作。同時哈希表使用量表的方式解決沖突。具體的數據結構如下： [cpp] /* * 哈希表節點 */ typedef struct dictEntry { // 鍵 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 鏈往後繼節點 struct dictEntry *next; } dictEntry; /* * 特定於類型的一簇處理函數 */ 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; /* * 哈希表 */ typedef struct dictht { // 哈希表節點指針數組（俗稱桶，bucket） dictEntry **table; // 指針數組的大小 unsigned long size; // 指針數組的長度掩碼，用於計算索引值 unsigned long sizemask; // 哈希表現有的節點數量 unsigned long used; } dictht; /* * 字典 * * 每個字典使用兩個哈希表，用於實現漸進式 rehash */ typedef struct dict { // 特定於類型的處理函數 dictType *type; // 類型處理函數的私有數據 void *privdata; // 哈希表（2個） dictht ht[2]; // 記錄 rehash 進度的標志，值為-1 表示 rehash 未進行 int rehashidx; // 當前正在運作的安全迭代器數量 int iterators; } dict; /* * 字典迭代器 * * 如果 safe 屬性的值為 1 ，那麼表示這個迭代器是一個安全迭代器。 * 當安全迭代器正在迭代一個字典時，該字典仍然可以調用 dictAdd 、 dictFind 和其他函數。 * * 如果 safe 屬性的值為 0 ，那麼表示這不是一個安全迭代器。 * 如果正在運作的迭代器是不安全迭代器，那麼它只可以對字典調用 dictNext 函數。 */ typedef struct dictIterator { // 正在迭代的字典 dict *d; int table, // 正在迭代的哈希表的號碼（0 或者 1） index, // 正在迭代的哈希表數組的索引 safe; // 是否安全？ dictEntry *entry, // 當前哈希節點 *nextEntry; // 當前哈希節點的後繼節點 } dictIterator; 分析 rehash 在字典中使用了兩個hash表就是為了方便進行rehash的，rehash主要有兩種方式，一是由後台調用cron進行按照100步進進行hash，二是在進行添加刪除字典中的元素的時候進行1步的hash。 這裡每一次的hash的步進是以真個hash key對應的鏈表為單位的，也就是說1步進的rehash是將原來hash表中的一個key鏈表進行rehash到新的哈希表中的位置。這裡可以看出Redis在此處是犧牲了內存但是換來了性能的響應。將rehash進行分散操作可以避免阻塞導致的性能急劇下降。www.2cto.com 迭代器 迭代器的屬性如果是安全的則表明可以在迭代的過程中進行dictAdd等其他的操作，而如果迭代器是不安全的則只能進行next的操作。 同時Redis限制在有迭代器訪問字典的時候進行rehash，因為這樣會造成對一個元素訪問多次。但是在rehash的過程中可以隨時的對字典進行遍歷，一旦迭代器開始遍歷字典了，rehash就會暫停知道沒有迭代器在對字典進行遍歷為止。
