Redis数据结构(二)字典-阿里云开发者社区

开发者社区> 数据库> 正文

Redis数据结构(二)字典

简介: Redis字典其实就是Hash表,其实现和JAVA语言中的hashmap结构大同小异,按Key-Value方式存储键值对,但是又存在一定的差异。 java中的hashmap结构即包含hash表,又实现了rehash自我扩充; 而redis字典则通过dictht结构实现hash表,通过字典(dict)实现rehash(字典中包含一个dictht数组dictht ht[2])

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;
  • ht数组则包含2个dictht结构,平时只使用ht[0],在rehash的时候使用ht[1];
  • rehashidx则为一个标志位,如果当前没有在进行rehash,则值为-1;redis通过渐进方式进行rehash,rehash期间,每执行一次操作,则rehashidx值加1;

Redis哈希算法

(未完待续。。。)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
数据库
使用钉钉扫一扫加入圈子
+ 订阅

分享数据库前沿,解构实战干货,推动数据库技术变革

其他文章