- 字典是一个用于保存键值对的数据结构
- 字典的键为独一无二的
- redis的数据库就是使用字典实现的
- hash键的底层实现
hash表结构
哈希表结构
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码,用于计算索引值,总之等于size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}
table是一个数组,数组中的每个元素都是指向dictEntry结构的指针,每个dictEntry保存这一个键值对
hash节点
typedef struct dictEntry {
//键
void *key;
//值
union {
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下一个hash节点,形成链表
struct dictEntry *next;
} dictEntry;
其中next可以连接相同的节点,可以通过这个指针将相同哈希值的多个键值对节点连接起来,来解决哈希冲突的问题
字典结构
字典由如下结构表示:
typedef struct dict {
//类型特定函数
dictType *type;
//私有数据
void *privData;
//哈希表
dictht ht[2];
//rehash索引
//当rehash不进行时,值为-1
int trehashidx;
}
- ht属性是一个包含两个项的数组,一般情况下,使用ht[0],ht[1]只用来进行rehash操作
- trehashidx记录了rehash的进度
hash算法
hash算法根据键值,计算出哈希值,在结合sizemask的值,计算出索引值
向hash表添加一个键值对时,先根据hash算法计算出键值对的哈希值和索引值
再根据索引值确定新的哈希表节点放到指定索引上
解决键冲突
- 当两个以上的键被分配了相同的索引值,即为哈希碰撞
- redis使用链地址法来处理hash冲突,每个hash表项都有一个next指针,相同的索引值的会组成一个单项链表
- 为了提高速率,每次发生hash冲突时,会将新的节点放在单向链表的表头
rehash
当hash表的装载因子大于1时,redis会将hash表进行rehash操作
步骤:
- 首先会初始化ht[1],表的大小由现有键值对的大小等因素决定
- 将ht0表中的所有的键值对重新计算hash值和索引值,写入ht1
- 当完成后,将释放ht0,将ht1作为ht0,并初始化一个空表尾ht1
rehash的条件
- 不存在bgsave或者bgrewriteaof任务时,当装载因子大于1时
- 存在bgsave和bgrewriteaof任务时,当装载因子大于5时
- 之所以根据bgsave和bgrewriteaof任务是否存在,来确定不同负载因子的值,是因为,bgsave和bgrewriteaof会产生子进程处理
- 由于大多操作系统采用写时复制机制来优化子进程效率,所以在bgsave和bgrewriteaof任务时提高负载因子会避免不必要的内存写入操作
渐进式的rehash
当存在大量的键值对时,rehash会带来大量的运算,并且在此期间不能响应请求,所以采用渐进式的rehash方法
- 当redis对键值进行增,删改查时,redis除了执行制定操作时,还会将对应的hashindex上的键值对全部rehash到ht1上
- 对rehash的值会反映在rehashidx上,当该值为-1时,表示已经完成rehash
- 在此期间,对于创建键值操作,会直接在ht1表上创建;查找时,ht0中不存在时,会再查找ht1中