字典的實(shí)現(xiàn)
哈希表
typedef struct dictht {
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼壁榕，用于計(jì)算索引值
// 總是等于 size - 1
unsigned long sizemask;
// 該哈希表已有節(jié)點(diǎn)的數(shù)量
unsigned long used;
} dictht;
table屬性是一個(gè)數(shù)組溢吻，數(shù)組中的每個(gè)元素都是一個(gè)指向dictEntry結(jié)構(gòu)的指針。每個(gè)dictEntry結(jié)構(gòu)保存著一個(gè)鍵值對(duì)。
哈希表節(jié)點(diǎn)
/*
* 哈希表節(jié)點(diǎn)
*/
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
struct dictEntry *next;
} dictEntry;
字典
/*
* 字典
*/
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 當(dāng) rehash 不在進(jìn)行時(shí)驹沿，值為 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在運(yùn)行的安全迭代器的數(shù)量
int iterators; /* number of iterators currently running */
} dict;
哈希算法
當(dāng)一個(gè)新的鍵值對(duì)加入字典時(shí)，程序根據(jù) 鍵 計(jì)算出哈希值和索引值蹈胡，然后再根據(jù)索引值，將包含新鍵值對(duì)的哈希表節(jié)點(diǎn)放到哈希表數(shù)組的指引索引上朋蔫。
解決鍵沖突
被分配到同一個(gè)索引上的多個(gè)節(jié)點(diǎn)可以用單向鏈表連接起來(lái)罚渐。新節(jié)點(diǎn)添加到鏈表表頭。
