這篇介紹redis最后一個(gè)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)——hash表?？梢院敛豢鋸埖恼f(shuō)，hash表是redis一切存儲(chǔ)的基礎(chǔ)，也是redis得以快如飛的基礎(chǔ)。
注：其實(shí)還有個(gè)intset，不過(guò)intset是在持久化dump到硬盤(pán)時(shí)為節(jié)省空間設(shè)計(jì)的，和我們這里談的不一樣。
dict的設(shè)計(jì)呢，簡(jiǎn)單的說(shuō)是一個(gè)雙表，“一主一從”，不定時(shí)rehash，建議大家在讀代碼前能夠?qū)@個(gè)設(shè)計(jì)有所了解。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實(shí)現(xiàn)里很多這種NOTUSED宏，算是作者偷懶吧
9
10
typedef
struct
dictEntry {
11
void
*
key;
12
void
*
val;
13
struct
dictEntry *
next;
14
} dictEntry; //redis的一個(gè)dict表項(xiàng)，存的是key , val， 以及因?yàn)閞edis的hash是用的拉鏈法，所以有一個(gè)指向下一個(gè)dictEntry的指針；
//一個(gè)dictEntry的內(nèi)存占用為12個(gè)字節(jié)，記住這個(gè)數(shù)字。
15
16
typedef
struct
dictType {
17
unsigned
int
(*hashFunction)(
const
void
*
key); //hash函數(shù)
18
void
*(*keyDup)(
void
*privdata,
const
void
*
key); //復(fù)制key
19
void
*(*valDup)(
void
*privdata,
const
void
*
obj); //復(fù)制value
20
int
(*keyCompare)(
void
*privdata,
const
void
*key1,
const
void
*
key2); //key的compare函數(shù)
21
void
(*keyDestructor)(
void
*privdata,
void
*
key);
22
void
(*valDestructor)(
void
*privdata,
void
*
obj);
23
} dictType; //dict的類(lèi)型
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; //這個(gè)是hash table結(jié)構(gòu)，每個(gè)dictionary有兩個(gè)hash 表，實(shí)現(xiàn)的是遞增的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的一個(gè)flag，rehash進(jìn)行過(guò)程中，有些操作不能進(jìn)行
39
int
iterators;
/*
number of iterators currently running
*/ //記錄在dict上正在執(zhí)行的iter數(shù)
40
} dict; //dict的數(shù)據(jù)結(jié)構(gòu)
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.
*/
//迭代器按照是否可以執(zhí)行改變hash表的函數(shù)區(qū)別為safe iterator和non safe iterator， non safe iterator只能執(zhí)行dictNext函數(shù)
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); //進(jìn)行多少個(gè)dictEntry的rehash
114
int
dictRehashMilliseconds(dict *d,
int
ms); //限制rehash執(zhí)行的時(shí)間，這兩個(gè)函數(shù)都在redis的主流程中被調(diào)用，避免因?yàn)閳?zhí)行rehash，無(wú)法響應(yīng)client請(qǐng)求。
115
116
/*
Hash table types
*/
117
extern
dictType dictTypeHeapStringCopyKey;
118
extern
dictType dictTypeHeapStrings;
119
extern
dictType dictTypeHeapStringCopyKeyValue; //三種預(yù)先定義好的dictType，具體定義參考其他文件。
120
121
#endif
/* __DICT_H */
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
