typedef struct dictht{
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
table
:存储节点的数组size
:table数组的长度sizemask
:size-1,用于在添加节点时计算节点在table中的位置used
:节点数量typedef struct dictEntry{
void *key
union {
void *val;
unit64_t u64;
int64_t s64;
}v;
struct dictEntry *next
} dictEntry;
key
:节点的keyunion
:节点的value(可以是指针、unit64_t整数、int64_t整数)next
:下一个节点的地址typedef struct dict {
dictType *type
void *privdata
dictht ht[2]
} dict;
type
:操作哈希表的各种函数privdata
:上述函数所需的入参ht[2]
:存储两个哈希表,一个正常使用,另一个在rehash时使用。当加载因子(load factor)大于1或小于0.1时就要进行rehash。 加载因子计算公式:
load_factor = ht[0].used / ht[0].size
当需要进行扩容/缩容的时候,究竟创建多大的哈希表呢?这取决于如下公式: