Redis原始碼閱讀三:雜湊表
直接上程式碼:
typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry; typedef struct dictType { uint64_t (*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; /* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. */ typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictht; typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; /* rehashing not in progress if rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */ } dict;
-
採用面向介面程式設計,把函式定義放到
struct dictType
裡,這裡是對字典中所有 元素進行操作的函式 -
struct dictEntry
是字典中K-V真正存放的地方,void *key
是K,而union ... v
是V -
每個字典有兩張雜湊表,在
dictht ht[2]
這裡定義。rehashidx
是一個標記位,代表是否處於 重新雜湊。其中rehash採用的是漸進式rehash,可以看到程式碼中有好幾個地方有這樣的程式碼:
if (dictIsRehashing(d)) _dictRehashStep(d);
-
dict使用的雜湊函式見:ofollow,noindex" target="_blank">https://en.wikipedia.org/wiki/SipHash
-
解決衝突是用鏈式
-
迭代,字典在有安全跌帶器的時候不會進行rehash,見程式碼:
/* This function performs just a step of rehashing, and only if there are * no safe iterators bound to our hash table. When we have iterators in the * middle of a rehashing we can'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. */ static void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1); }