Redis 三 - 字典

Redis 三 - 字典

主要涉及到 dict.cdict.h 文件

定义

哈希表:

1
2
3
4
5
6
7
8
9
10
11
/* 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 {
/* Hash Table Array */
dictEntry **table;
/* Hash Table Size */
unsigned long size;
/* For calculate index */
unsigned long sizemask;
unsigned long used;
} dictht;

table 属性是一个数组,数组中的每个元素都是一个指向 dictEntry 结构体的指针,每个 dictEntry 保存着一个键值对:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct dictEntry {
/* The Key */
void *key;
/* The Value */
/* The Value Can be a pointer,
or a uint64_t interger,
or a int64_t interger,
or a double value */
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
/* The Pointer to The Next Node */
struct dictEntry *next;
} dictEntry;

字典由 dict 结构体表示:

1
2
3
4
5
6
7
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;

ht[0] 用于存储数据,ht[1] 用于 rehash 的时候使用,当没有进行 rehash 的时候,rehashidx 的值为 -1

dictType 保存了一簇用于操作特定类型键值对的函数:

1
2
3
4
5
6
7
8
typedef struct dictType {
unsigned int (*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;

普通状态下的词典:

计算哈希值和索引值:

计算键的哈希值:

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

计算索引值:

1
idx = h & d->ht[table].sizemask;

Hash 算法

Redis 目前使用两种不同的哈希算法:

1. MurmurHash2 32 bit 算法:这种算法的分布率和速度都非常好。Redis,Memcached,Cassandra,HBase,Lucene, Hadoop, Nginx 等都在用 MurmurHash 算法,主要是因为算法快,速度快: 与 MD5 这些讲究安全性的摘要算法比,Redis 们内部为主键做个 Hash 而已,就不需要安全性了,因此 Google 家的 MurmurHash 这种 non-cryptographic 的速度会快几十倍

有些人看到 murmur 就想到了陌陌就想到了别的,其实是 multiply and rotate 的意思,因为算法的核心就是不断的

1
2
x *= m; 
x = rotate_left(x,r);

2. 基于 djb 算法实现的一个大小写无关散列算法:具体信息请参考 http://www.cse.yorku.ca/~oz/hash.html

解决键冲突

使用链地址法

rehash

参考

推荐文章