這篇介紹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 */
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
