Fork me on GitHub

redis源码阅读——dict

Posted on | Post modified: | In
Words count in article: 554 | Reading time ≈ 2

dict类型

先看宏定义

最基本的是dict类型，如下：

1
2
3
4
5
6
7
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    PORT_LONG rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;
  • dictType 是一个结构体，包含了dict的一些基础方法
  • privdata 是私有数据
  • dictht 是哈希表
  • rehashidx 代表是否在进行重哈希，如果不为-1则代表正在进行重哈希
  • iterators 代表迭代器，暂时还不太理解

接下来看哈希表的结构(dictht):

1
2
3
4
5
6
typedef struct dictht {
    dictEntry **table;
    PORT_ULONG size;
    PORT_ULONG sizemask;
    PORT_ULONG used;
} dictht;
  • table是一个指向dictEntry的二级指针
  • size代表哈希表的大小
  • sizemask 总是等于size-1
  • used代表该哈希表已有的节点数量

这是dictht的构造：

不过这里为什么要二级指针呢？

可以这样理解，因为dictEntry *本身就是一个一级指针，同时table指向的又是一个指针数组，所以这里需要二级指针了

复习一下数组指针和指针数组的概念

数组指针，本质上还是指针

int (*p)[n]
()运算优先级更高，*优先与p结合，p还是一个指针，不过p指向的是一个数组，这时候p+1运算的步长就是n,故这样的指针也叫行指针

指针数组
int *p[n]
[]优先级更高，p先与方括号结合，这时候p代表的是一个数组，这个数组中每个元素都是一个指针，故此时p就是二级指针

之后继续看dictEntry类型

1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

这里面存储了key-value键值对，其中key是一个void*类型的指针，可以代表任意类型的数据，但是value是一个联合体，可以在指针，整数和浮点数中取值

next属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题

参考

字典的实现
Redis内部数据结构详解(1)——dict
数组指针和指针数组的区别