Redis数据结构（二）字典
Redis字典其实就是Hash表，其实现和JAVA语言中的hashmap结构大同小异，按Key-Value方式存储键值对，但是又存在一定的差异。
java中的hashmap结构即包含hash表，又实现了rehash自我扩充；
而redis字典则通过dictht结构实现hash表，通过字典（dict）实现rehash（字典中包含一个dictht数组dictht ht[2]）。
Redis字典的实现
Redis字典所使用的哈希表由dict.h/dictht结构定义：
typedef struct dictht{
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
}dictht;table为一个dictEntry结构的数组，每个dictEntry结构保存着一个key-value对。size为table数组的大小（注意不是key-value对的个数）；used才是key-value对的个数；sizemask为size-1，用途后面会提到；
dictEntry结构定义如下：
typedef struct dictEntry{
void *key;
union{
void *val;
uint64_t u64;
int64_t s64;
} v;
struct dictEntry *next;
}key即为键，v即为值，由定义可以看出，v既可以是一个指针，也可以是一个uint64_t整数或者int64_t整数。
next属性指向下一个dictEntry，形成链表结构。在字典结构中，每一个key-value中的key的hash值映射到table的下标，如果有多个key的hash值映射到table的同一个下标，则这些key-value对将通过 next指针形成一个链表，存到table的当前下标中。
Redis中的字典由dict.h/dict结构表示：
typedef struct dict{
dictType *type;
void *privdata;
dictht ht[2];
int rehashidx;
} dict;注意到，其中：
dictht即为前面介绍的哈希表结构； type指针为一个dictType结构，该结构保存了一些用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数； privdata则保存了需要传递给type中特定函数的可选参数；dictType结构如下：
typedef struct dictType{
//计算hash值
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;Redis哈希算法
（未完待续。。。）
本站文章为和通数据库网友分享或者投稿，欢迎任何形式的转载，但请务必注明出处.
同时文章内容如有侵犯了您的权益，请联系QQ：970679559，我们会在尽快处理。