redis--hash的实现
Redis数据结构---字典，哈希表，dict 或java中的map，数据使⽤key -> value的形式存储，整个redis数据库就是基于字典实现，api见hash REDIS的hash实现原理和java的HashMap⼗分相似，可参考阅读
理解redis的hash实现，就要先理解⼀下三个结构  dictEntry, ditht, dict
哈希表节点 dictEntry {
void  *key //键值
union{void *val; uint64_tu64; int64_ts64} v  //值可以是指针，可以是uint_64_t整数或者int64_t整数
struct dictEntry *next;  //指向下⼀个哈希节点，形成链表的结构（同java hashmap中的entry）
}
哈希表 dictht{
dictEntry **table;  //⼀个元素为dictEntry 的数组
long size; // 哈希表的⼤⼩
long sizemask; // 哈希表⼤⼩掩码，⽤于计算存储时所在的数组下标⼤⼩总是等于size-1
long used;  //当前哈希表已有的节点数量
}
哈希表有个负载因⼦的概念，load_factor = used/size  即已使⽤除以总数size的结果
⽽提供api给我们开发者，即直接使⽤的dict实现如下
字典 dict{
dictType *type //指针，特定类型的函数  redis中有定义，指向了⼀族函数，⽤以实现针对键值对的操作，这同list的dup free match⼀样，也是多太的⼀种，是dict可以存不同类型的键值对
void *privdata //私有数据⽤以使⽤dictType中定义的特定函数时传⼊的可选参数
dictht ht[2]  //元素为哈希表的数组，长度为2，即保存着2个哈希表
in trehashidx // rehash索引，当不在进⾏rehash时为-1
}
当向⼀个dict中set⼀个键值A对时，会先使⽤hash算法根据键值计算出⼀个数字，即哈希表中数组的下标，该键值对就存放在此位置上，
正则匹配哈希值
如果再有⼀个键值B对被set存放进⼊此dict时，hash算法根据键值计算出的数字同上，即为键冲突，也叫哈希冲突，这时hash表会使⽤头插法，将B的dictEntry的next设置为A，形成链表的数据结构
随着dict的操作，键值对会有增多和减少，为了是负载因⼦在合理范围内，会产⽣rehash，其步骤简单如下：
当没有rehash的普通情况下，dict中的ht[2] 数组总是使⽤ht[0] 对应的哈希表来保存数据，当需要扩容或缩减时，会为ht[1]分配对应的存储空间，其⼤⼩算法是
扩容时，⼤⼩是第⼀个⼤于ht[0]的size的 2的n次⽅，缩⼩时，是第⼀个⼩于ht[0]长度的2的n次⽅（可参考java的Hashmap中的tablesizefor 算法）
当ht[1]分配好空间后，会把ht[0]上的所有数据复制到ht[1]上，之后ht[0]变为空表，是否，把ht[1]移到ht[0]上继续使⽤
如果redis在执⾏BGSAVE或BAREWRITEAOF命令操作，会在当前redis服务现场中创建⼦进程，使⽤的是写时复制技术优化⼦进程的使⽤效率!
当没有⼦进程存在时，负载因⼦⼤于等于1时就会进⾏rehash，当存在⼦进程时，负载因⼦需要⼤于等于5才会进⾏rehash
当负载因⼦⼩于0.1时，也会进⾏收缩操作的rehash！
这样设计的⽬的就是尽量的使⼦进程⼯作期间，不要有rehash操作的产⽣，避免不必要的内存浪费
rehash使⽤的是渐进式rehash
它不会⼀次性的吧所有的ht[0] 中的数据⼀下⼦复制到ht[1]中，⽽是在增删改查操作发⽣时，每发⽣⼀次就复制⼀个值过去，同时对rehashidx做+1，避免了集中的⼤量的运算⽽导致redis夯死，值得注意的是，每次新增操作会把新增的值放⼊ht[1]中，同时复制⼀个ht[0]中数据到ht[1]中！同时，因为完整数据存在于2个hash表中，所有查询时是先查ht[0]，再查ht[1]！循序渐进的复制，最终复制完成

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。