哈希表數(shù)據(jù)結(jié)構(gòu)
typedef struct dictht{
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼
unsigned long sizemask;
// 該哈希表已有節(jié)點的數(shù)量
unsigned long used;
};
??sizemask=size-1
哈希表節(jié)點數(shù)據(jù)結(jié)構(gòu)
typedef struct dictEntry{
// 鍵
void *key;
// 值
union{
void *val;
uint64_t u64;
int64_t s64;
}v;
// 指向下個哈希節(jié)點习蓬，形成鏈表
struct dictEntry *next;
};
key屬性保存著鍵值對中的鍵，而v屬性保存著鍵值對中的值措嵌。
image.png
Redis的字典使用哈希表作為底層實現(xiàn)躲叼。
字典數(shù)據(jù)結(jié)構(gòu)
typedef struct dict{
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privateData;
// 哈希表
dictht ht[2];
// rehash索引
// 當rehash不在進行時，值為-1
int rehashidx;
};
image.png
hash算法
# 使用字典設置的哈希函數(shù)企巢，計算鍵 key 的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的 sizemask 屬性和哈希值枫慷，計算出索引值
# 根據(jù)情況不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;
