这篇介绍redis最后一个基础数据结构——hash表。可以毫不夸张的说，hash表是redis一切存储的基础，也是redis得以快如飞的基础。
注：其实还有个intset，不过intset是在持久化dump到硬盘时为节省空间设计的，和我们这里谈的不一样。
dict的设计呢，简单的说是一个双表，“一主一从”，不定时rehash，建议大家在读代码前能够对这个设计有所了解。Anyway，随便搜一搜，很多文章的。
dict.h
1
#ifndef __DICT_H
2
#define
__DICT_H
3
4
#define
DICT_OK 0
5
#define
DICT_ERR 1
6
7
/*
Unused arguments generate annoying warnings...
*/
8
#define
DICT_NOTUSED(V) ((void) V) //redis实现里很多这种NOTUSED宏，算是作者偷懒吧
9
10
typedef
struct
dictEntry {
11
void
*
key;
12
void
*
val;
13
struct
dictEntry *
next;
14
} dictEntry; //redis的一个dict表项，存的是key , val， 以及因为redis的hash是用的拉链法，所以有一个指向下一个dictEntry的指针；
//一个dictEntry的内存占用为12个字节，记住这个数字。
15
16
typedef
struct
dictType {
17
unsigned
int
(*hashFunction)(
const
void
*
key); //hash函数
18
void
*(*keyDup)(
void
*privdata,
const
void
*
key); //复制key
19
void
*(*valDup)(
void
*privdata,
const
void
*
obj); //复制value
20
int
(*keyCompare)(
void
*privdata,
const
void
*key1,
const
void
*
key2); //key的compare函数
21
void
(*keyDestructor)(
void
*privdata,
void
*
key);
22
void
(*valDestructor)(
void
*privdata,
void
*
obj);
23
} dictType; //dict的类型
24
25
/*
This is our hash table structure. Every dictionary has two of this as we
26
* implement incremental rehashing, for the old to the new table.
*/
27
typedef
struct
dictht {
28
dictEntry **
table;
29
unsigned
long
size; //size
30
unsigned
long
sizemask;
31
unsigned
long
used; //used
32
} dictht; //这个是hash table结构，每个dictionary有两个hash 表，实现的是递增的rehash
33
34
typedef
struct
dict {
35
dictType *
type;
36
void
*
privdata;
37
dictht ht[
2
];
38
int
rehashidx;
/*
rehashing not in progress if rehashidx == -1
*/ //记录是否在rehash的一个flag，rehash进行过程中，有些操作不能进行
39
int
iterators;
/*
number of iterators currently running
*/ //记录在dict上正在执行的iter数
40
} dict; //dict的数据结构
41
42
/*
If safe is set to 1 this is a safe iteartor, that means, you can call
43
* dictAdd, dictFind, and other functions against the dictionary even while
44
* iterating. Otherwise it is a non safe iterator, and only dictNext()
45
* should be called while iterating.
*/
//迭代器按照是否可以执行改变hash表的函数区别为safe iterator和non safe iterator， non safe iterator只能执行dictNext函数
46
typedef
struct
dictIterator {
47
dict *
d;
48
int
table, index, safe;
49
dictEntry *entry, *
nextEntry;
50
} dictIterator;
51
52
/*
This is the initial size of every hash table
*/
53
#define
DICT_HT_INITIAL_SIZE 4
54
55
/*
------------------------------- Macros ------------------------------------
*/
56
#define
dictFreeEntryVal(d, entry) \
57
if
((d)->type->
valDestructor) \
58
(d)->type->valDestructor((d)->privdata, (entry)->
val)
59
60
#define
dictSetHashVal(d, entry, _val_) do { \
61
if
((d)->type->
valDup) \
62
entry->val = (d)->type->valDup((d)->
privdata, _val_); \
63
else
\
64
entry->val =
(_val_); \
65
}
while
(
0
)
66
67
#define
dictFreeEntryKey(d, entry) \
68
if
((d)->type->
keyDestructor) \
69
(d)->type->keyDestructor((d)->privdata, (entry)->
key)
70
71
#define
dictSetHashKey(d, entry, _key_) do { \
72
if
((d)->type->
keyDup) \
73
entry->key = (d)->type->keyDup((d)->
privdata, _key_); \
74
else
\
75
entry->key =
(_key_); \
76
}
while
(
0
)
77
78
#define
dictCompareHashKeys(d, key1, key2) \
79
(((d)->type->keyCompare) ?
\
80
(d)->type->keyCompare((d)->
privdata, key1, key2) : \
81
(key1) ==
(key2))
82
83
#define
dictHashKey(d, key) (d)->type->hashFunction(key)
84
85
#define
dictGetEntryKey(he) ((he)->key)
86
#define
dictGetEntryVal(he) ((he)->val)
87
#define
dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)
88
#define
dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
89
#define
dictIsRehashing(ht) ((ht)->rehashidx != -1)
90
91
/*
API
*/
92
dict *dictCreate(dictType *type,
void
*
privDataPtr);
93
int
dictExpand(dict *d, unsigned
long
size);
94
int
dictAdd(dict *d,
void
*key,
void
*
val);
95
int
dictReplace(dict *d,
void
*key,
void
*
val);
96
int
dictDelete(dict *d,
const
void
*
key);
97
int
dictDeleteNoFree(dict *d,
const
void
*
key);
98
void
dictRelease(dict *
d);
99
dictEntry * dictFind(dict *d,
const
void
*
key);
100
void
*dictFetchValue(dict *d,
const
void
*
key);
101
int
dictResize(dict *
d);
102
dictIterator *dictGetIterator(dict *
d);
103
dictIterator *dictGetSafeIterator(dict *
d);
104
dictEntry *dictNext(dictIterator *
iter);
105
void
dictReleaseIterator(dictIterator *
iter);
106
dictEntry *dictGetRandomKey(dict *
d);
107
void
dictPrintStats(dict *
d);
108
unsigned
int
dictGenHashFunction(
const
unsigned
char
*buf,
int
len);
109
unsigned
int
dictGenCaseHashFunction(
const
unsigned
char
*buf,
int
len);
110
void
dictEmpty(dict *
d);
111
void
dictEnableResize(
void
);
112
void
dictDisableResize(
void
);
113
int
dictRehash(dict *d,
int
n); //进行多少个dictEntry的rehash
114
int
dictRehashMilliseconds(dict *d,
int
ms); //限制rehash执行的时间，这两个函数都在redis的主流程中被调用，避免因为执行rehash，无法响应client请求。
115
116
/*
Hash table types
*/
117
extern
dictType dictTypeHeapStringCopyKey;
118
extern
dictType dictTypeHeapStrings;
119
extern
dictType dictTypeHeapStringCopyKeyValue; //三种预先定义好的dictType，具体定义参考其他文件。
120
121
#endif
/* __DICT_H */
