Redis源码阅读之字典（一）

数据结构

字典的基本单元——`dictEntry`

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21



typedef struct dictEntry {

    void *key;

    union {

        void *val;

        uint64_t u64;

        int64_t s64;

        double d;

    } v;

    struct dictEntry *next;

} dictEntry;

dictEntry是Redis中的哈希表数据接口的基本单元，有一个指向key的指针，还有一个联合体v，代表的是字典的值，它可以是一个数字（浮点或者有符号整型或者无符号整型），还有一个next字段指向下一个dictEntry的指针。说明了一个问题，dictEntry其实是一个链表节点。

哈希表——`dictht`

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17



/* This is our hash table structure. Every dictionary has two of this as we

 * implement incremental rehashing, for the old to the new table. */

typedef struct dictht {

    dictEntry **table;

    unsigned long size;

    unsigned long sizemask;

    unsigned long used;

} dictht;

从注释可以明显看出，这个结构是redis的哈希表结构，每个字典都会有两个哈希表元素，以便于在rehashing的时候从旧的哈希表将数据迁移到新的哈希表中。

再观察，第一个字段table，其实就是一个dictEntry的指针列表，size代表table的长度，used代表table当前存储的dictEntry(注意，假如size==8,used==8,这不代表table的每个元素都不为NULL，因为算出来的hash可能会碰撞，hash和sizemask相与后可能会再一次碰撞)，sizemask作用就是保证hash后的值，能够落入table的范围内，其实说白了，就是求某一个key落入到dictht的哪个index里面，具体操作要看函数_dictKeyIndex。里面有一行代码是idx = hash & d->ht[table].sizemask;，这个就是sizemask的主要作用。关于size,sizemask,在dictExpand可以看到对其赋值，size就是创建的table长度，sizemask是size-1。

根据dictht和dictEntry的结构其实我们可以推论出一个事情，那就是redis的哈希表实现几乎就是最简单的哈希实现，数组加上链表，如果哈希碰撞，其实是一个灾难性的发生。为什么不使用数据加上红黑树的实现方式呢？下面图是来自于网络，最简单的哈希实现方式：

字典的类型——dictType

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17



typedef struct dictType {

    uint64_t (*hashFunction)(const void *key);

    void *(*keyDup)(void *privdata, const void *key);

    void *(*valDup)(void *privdata, const void *obj);

    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    void (*keyDestructor)(void *privdata, void *key);

    void (*valDestructor)(void *privdata, void *obj);

} dictType;

其实光看这里真的看不出来啥，看看咋用的吧，在server.c文件中，有一堆声明，我就随意拿一个出来了：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21



/* Generic hash table type where keys are Redis Objects, Values

 * dummy pointers. */

dictType objectKeyPointerValueDictType = {

    dictEncObjHash,            /* hash function */

    NULL,                      /* key dup */

    NULL,                      /* val dup */

    dictEncObjKeyCompare,      /* key compare */

    dictObjectDestructor,      /* key destructor */

    NULL                       /* val destructor */

};

看注释基本还是能看明白：

hashFunction是将key哈希化的函数
keyDup是拷贝key的函数，
valDup是拷贝value的函数
keyCompare是用来比较两个key是否相等的函数
keyDestructor是用来删除key对象的函数
valDestructor是用来删除value对象的函数

这个结构咋理解呢？想想python里面的__hash__函数，它其实就对应的是hashFunction，又例如golang中新建一个map[string]uint64,其实就已经隐含了key和value的拷贝，对比了。当然，对于redis这种主力是c语言来说，对于不需要的变量，理所当然需要一个释放内存的操作。只是说其他语言不需要是因为有GC的原因。

主角——字典结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15



typedef struct dict {

    dictType *type;

    void *privdata;

    dictht ht[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    unsigned long iterators; /* number of iterators currently running */

} dict;

type字段，是为了保存字典操作key和value的增删查改的函数的。
privdata字段，没啥用了，不管它了。
ht字段，这里照应了上面dictht的注释，这里会有两个dictht，目的就是为了rehash。
rehashidx字段，表示rehash的进度(其实就是ht[0]中table的index)，如果没有在rehash操作时，这个字段默认为-1。

迭代器

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17



typedef struct dictIterator {

    dict *d;

    long index;

    int table, safe;

    dictEntry *entry, *nextEntry;

    /* unsafe iterator fingerprint for misuse detection. */

    long long fingerprint;

} dictIterator;

如果safe是1，那么久是一个安全的迭代器，你可以增加(dictAdd)或者查找(dictFind)，反之，只能查找下一个(dictNext)。

宏定义

API操作的返回值

1
2
3
4
5



#define DICT_OK 0 // 成功

#define DICT_ERR 1 // 失败

防止编译器报警

1
2
3
4
5



/* Unused arguments generate annoying warnings... */

#define DICT_NOTUSED(V) ((void) V)

哈希表的默认大小

1
2
3
4
5



/* This is the initial size of every hash table */

#define DICT_HT_INITIAL_SIZE     4

使用`dictType`

释放value的内存

1
2
3
4
5
6
7



#define dictFreeVal(d, entry) \

    if ((d)->type->valDestructor) \

        (d)->type->valDestructor((d)->privdata, (entry)->v.val)

在设置value的时候，如果存在`valDup`函数，会拷贝一份value

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13



#define dictSetVal(d, entry, _val_) do { \

    if ((d)->type->valDup) \

        (entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \

    else \

        (entry)->v.val = (_val_); \

} while(0)

释放key占用的内存

1
2
3
4
5
6
7



#define dictFreeKey(d, entry) \

    if ((d)->type->keyDestructor) \

        (d)->type->keyDestructor((d)->privdata, (entry)->key)

在设置key的时候，如果存在`keyDup`函数，会拷贝一份key

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13



#define dictSetKey(d, entry, _key_) do { \

    if ((d)->type->keyDup) \

        (entry)->key = (d)->type->keyDup((d)->privdata, _key_); \

    else \

        (entry)->key = (_key_); \

} while(0)

比较两个key，查看是否相等

1
2
3
4
5
6
7
8
9



#define dictCompareKeys(d, key1, key2) \

    (((d)->type->keyCompare) ? \

        (d)->type->keyCompare((d)->privdata, key1, key2) : \

        (key1) == (key2))

算出key的hash值

1
2
3

#define dictHashKey(d, key) (d)->type->hashFunction(key)

操作`dictEntry`

获取key

1
2
3

#define dictGetKey(he) ((he)->key)

获取value

1
2
3
4
5
6
7
8
9



#define dictGetVal(he) ((he)->v.val)

#define dictGetSignedIntegerVal(he) ((he)->v.s64)

#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)

#define dictGetDoubleVal(he) ((he)->v.d)

操作`dict`

获取槽的数量

1
2
3

#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)

获取dictEntry的数量

1
2
3

#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)

判断是否正在rehashing

1
2
3

#define dictIsRehashing(d) ((d)->rehashidx != -1)

API

列表

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149



// 创建

dict *dictCreate(dictType *type, void *privDataPtr);

// 扩容

int dictExpand(dict *d, unsigned long size);

// 增加, 会调用dictAddRaw

int dictAdd(dict *d, void *key, void *val);

// 增加，如果传入existing，并且查找到对应的key，会对existing赋值

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing);

// 增加或查找，会调用dictAddRaw

dictEntry *dictAddOrFind(dict *d, void *key);

// 替换

// 如果key存在，会将原本的value释放掉，并且返回0

// 如果key不存在，会直接增加，并且返回1

int dictReplace(dict *d, void *key, void *val);

// 删除，调用dictGenericDelete

int dictDelete(dict *d, const void *key);

// 删除，但是不释放空间，调用调用dictGenericDelete

dictEntry *dictUnlink(dict *ht, const void *key);

// 删除，找到对应的key，将其从链表中删除，如果nofree为1，还会释放value和key的空间

static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree);

// 在调用dictUnlink函数后，必须使用该函数释放掉he和其对应的key和value的空间

void dictFreeUnlinkedEntry(dict *d, dictEntry *he);

// 释放dict空间

void dictRelease(dict *d);

// 根据key在dict中查找entry

dictEntry * dictFind(dict *d, const void *key);

// 跟据key在dict查找value，会使用dictFind

void *dictFetchValue(dict *d, const void *key);

// 调整dict的内存占用

// 保证 USED/BUCKETS 的比例接近于1，但是小于等于1

// 如果配置上不允许resize或者正在rehashing，会返回DICT_ERR

int dictResize(dict *d);

// 获取一个非安全的迭代器

dictIterator *dictGetIterator(dict *d);

// 获取一个安全的迭代器，会调用dictGetIterator

dictIterator *dictGetSafeIterator(dict *d);

// 获取下一个entry

dictEntry *dictNext(dictIterator *iter);

// 释放迭代器

// 如果在非安全的情况下，dict有改变，会直接报错

void dictReleaseIterator(dictIterator *iter);

// 随机获取一个entry

// 先random获取table上的index，再次random获取链表上的entry

dictEntry *dictGetRandomKey(dict *d);

// dictGetRandomKey可能会出现随机不公平的情况

// 

dictEntry *dictGetFairRandomKey(dict *d);

// 获取一些entry

// 不保证一定会获取到count个entry，可能跟你的size相关，也可能跟步数(count*10)相关

// 也不保证获取到的数据是不重复的

// 获取到的数据会有连续性，在random到一个非空的index时，会将这个index对应的链表整个存储下来，直到存储满，如果没存储满，index就会自增，然后反复循环，类似于在一个数组中选择一个index，然后圈定这个index后面count个元素，在index自增过程中，如果连续五次都是空的，就会再一次随机

unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count);

// 使用siphash算法

uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len);

// 置空dict

void dictEmpty(dict *d, void(callback)(void*));

// 对dict_can_resize进行设置，控制是否可以resize dict的大小

void dictEnableResize(void);

void dictDisableResize(void);

// 进行rehash操作

int dictRehash(dict *d, int n);

// 在ms毫秒内，进行rehash，每次rehash进行100次，然后再去比较时间

int dictRehashMilliseconds(dict *d, int ms);

// 设置hash的种子，hash种子dictGenCaseHashFunction函数会用

void dictSetHashFunctionSeed(uint8_t *seed);

// 获取hash种子，没人用

// dictGenCaseHashFunction函数是直接拿的seed指针

uint8_t *dictGetHashFunctionSeed(void);

// 遍历dict的key value，但是不保证唯一性

unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction *bucketfn, void *privdata);

// 直接调用的宏dictHashKey

uint64_t dictGetHash(dict *d, const void *key);

// 根据hash和指针来找到对应的entry

dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash);

杂项

`struct dict`中的`void *privdata`是干啥用的？

先看strct dictType:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17



typedef struct dictType {

    uint64_t (*hashFunction)(const void *key);

    void *(*keyDup)(void *privdata, const void *key);

    void *(*valDup)(void *privdata, const void *obj);

    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    void (*keyDestructor)(void *privdata, void *key);

    void (*valDestructor)(void *privdata, void *obj);

} dictType;

可以看出，结构体是使用privdata字段比较多的地方，

再看下dictType声明的地方，在server.c中，有一堆dictType的变量，查看其中的参数可以发现，所有的函数都会使用DICT_NOTUSED(privdata)，再去看下DICT_NOTUSED定义

1
2
3
4
5



/* Unused arguments generate annoying warnings... */

#define DICT_NOTUSED(V) ((void) V)

原来没用了……

文章目录

Redis源码阅读之字典（一）

数据结构

字典的基本单元——`dictEntry`

哈希表——`dictht`

字典的类型——dictType

主角——字典结构

迭代器

宏定义

API操作的返回值

防止编译器报警

哈希表的默认大小

使用`dictType`

释放value的内存

在设置value的时候，如果存在`valDup`函数，会拷贝一份value

释放key占用的内存

在设置key的时候，如果存在`keyDup`函数，会拷贝一份key

比较两个key，查看是否相等

算出key的hash值

操作`dictEntry`

获取key

获取value

操作`dict`

获取槽的数量

获取dictEntry的数量

判断是否正在rehashing

API

列表

杂项

`struct dict`中的`void *privdata`是干啥用的？

See Also

最近文章

分类

标签

其它

文章目录

数据结构

字典的基本单元——dictEntry

哈希表——dictht

字典的类型——dictType

主角——字典结构

迭代器

宏定义

API操作的返回值

防止编译器报警

哈希表的默认大小

使用dictType

释放value的内存

在设置value的时候，如果存在valDup函数，会拷贝一份value

释放key占用的内存

在设置key的时候，如果存在keyDup函数，会拷贝一份key

比较两个key，查看是否相等

算出key的hash值

操作dictEntry

获取key

获取value

操作dict

获取槽的数量

获取dictEntry的数量

判断是否正在rehashing

API

列表

杂项

struct dict中的void *privdata是干啥用的？

See Also

最近文章

分类

标签

其它

字典的基本单元——`dictEntry`

哈希表——`dictht`

使用`dictType`

在设置value的时候，如果存在`valDup`函数，会拷贝一份value

在设置key的时候，如果存在`keyDup`函数，会拷贝一份key

操作`dictEntry`

操作`dict`

`struct dict`中的`void *privdata`是干啥用的？