赞
踩
目录
扩展或收缩哈希表需要将ht[0]里面的所有键值对rehash到ht[1]里面,但是,这个rehash动作并不是一次性、集中式地完成的,而是分多次、渐进式地完成的。
- struct sdshdr {
- //SDS所保存字符串的长度
- int len;
-
- // 记录buf数组中未使用字节的数量
- int free;
-
- // 字节数组,用于保存字符串
- char buf[];
- };
列表键的底层实现就是一个链表,链表中的每个节点都保存了一个数值
- typedef struct list {
- // 表头节点
- listNode * head;
- // 表尾节点
- listNode * tail;
- // 链表所包含的节点数量
- unsigned long len;
- // 节点值复制函数
- void *(*dup)(void *ptr);
- // 节点值释放函数
- void (*free)(void *ptr);
- // 节点值对比函数
- int (*match)(void *ptr,void *key);
- } list;
-
- typedef struct listNode {
- // 前置节点
- struct listNode * prev;
- // 后置节点
- struct listNode * next;
- // 节点的值
- void * value;
- }listNode;
Redis的字典使用哈希表作为底层实现,一个哈希表(dictht)里面可以有多个哈希表节点(dictEntry ),而每个哈希表节点(dictEntry )就保存了字典中的一个键值对。
Redis字典所使用的哈希表由dict.h/dictht结构定义:
- Redis字典所使用的哈希表由dict.h/dictht结构定义:
- typedef struct dictht {
- // 哈希表节点组成的数组
- dictEntry **table; //
- // 哈希表大小
- unsigned long size;
- //哈希表大小掩码,用于计算索引值 总是等于size-1
- unsigned long sizemask;
- // 该哈希表已有节点的数量(非null节点)
- unsigned long used;
- } dictht;
-
-
- 哈希表节点使用dictEntry结构表示,每个dictEntry结构都保存着一个键值对:
- typedef struct dictEntry {
- // 键
- void *key;
- // 值
- union{
- void *val;
- uint64_tu64;
- int64_ts64;
- } v;
- // 指向下个哈希表节点,形成链表 (hash 冲突,链地址法)
- struct dictEntry *next;
- } dictEntry;
字典,是基于 hash 表的结构上,再次进行的一层封装
- Redis中的字典由dict.h/dict结构表示:
- typedef struct dict {
- // 类型特定函数
- dictType *type;
- // 私有数据
- void *privdata;
- // 哈希表数组,包含两个 dictht
- dictht ht[2];
- // rehash索引当rehash不在进行时,值为-1
- int rehashidx;
- } dict;
-
-
- type属性是一个指向dictType结构的指针,每个dictType结构保存了一簇用于操作特定类型键值对的函数,Redis会为用途不同的字典设置不同的类型特定函数。
- ·而privdata属性则保存了需要传给那些类型特定函数的可选参数。
- 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);
当要将一个新的键值对添加到字典里面时,程序需要先根据键值对的键计算出哈希值和索引值,然后再根据索引值,将包含新键值对的哈希表节点放到哈希表数组的指定索引上面
随着操作的不断执行,哈希表保存的键值对会逐渐地增多或者减少,为了让哈希表的负载因子(load factor)维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者太少时,程序需要对哈希表的大小进行相应的扩展或者收缩。 扩展和收缩哈希表的工作可以通过执行rehash(重新散列)操作来完成,Redis对字典的哈希表执行rehash的步骤如下:
当以下条件中的任意一个被满足时,程序会自动开始对哈希表执行扩展操作:
哈希表渐进式rehash的详细步骤:
- typedef struct zskiplistNode {
- // 层
- struct zskiplistLevel {
- // 前进指针
- struct zskiplistNode *forward;
- // 跨度
- unsigned int span;
- } level[];
-
- // 后退指针
- struct zskiplistNode *backward;
-
- // 分值(例:你的账号排名)
- double score;
-
- // 成员对象 (例: 你的游戏账号)
- robj *obj;
- } zskiplistNode;
- typedef struct zskiplist {
- //
- 表头节点和表尾节点
- structz skiplistNode *header, *tail;
- //
- 表中节点的数量
- unsigned long length;
- //
- 表中层数最大的节点的层数
- int level;
- } zskiplist;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。