昆山普立斯特做的有网站,南通城乡建设局网站招聘,各大网址收录查询,子域名网址查询HASH
哈希#xff0c;在redis底层实现的时候#xff0c;数据的结构叫做dict
这个Dict就是一个用于维护key和value映射关系的数据结构#xff0c;与很多语言中的Map类型相似。
本质上也是一个数组链表的形式存在#xff0c;不同的点在于#xff0c;每个dict中是可以存在…HASH
哈希在redis底层实现的时候数据的结构叫做dict
这个Dict就是一个用于维护key和value映射关系的数据结构与很多语言中的Map类型相似。
本质上也是一个数组链表的形式存在不同的点在于每个dict中是可以存在两个数组链表形式的哈希表。
就是为了在扩容的时候避免一次性对所有的key进行重哈希计算操作而是将重哈希操作分散到之后每次的增删改查中。 这样一来每次重哈希的时候也不影响单个请求与redis“快速相响应时间”的设计原则是相符的。
结构
dict为了实现增量式重哈希在数据结构里面包含两个哈希表。重哈希期间也就是扩容时候将数据从第一个哈希表向第二个哈希表迁移。
包含的结构类型有三种从大到小的结构类型依次是 dict - dictht - dictEntry
具体的结构定义如下
dict
哈希本身的包装类也就是我们操作的Hash
typedef struct dict {dictType *type; // 类型特性的函数保存了操作特定类型kv的函数void *privdata; // 私有数据传递给类型特定函数的可选的参数dictht ht[2]; // 哈希表两个dictht哈希表默认就用一个另外一个是在rehash(扩容)的时候用的ht[0]-在使用的hashtableht[1]-备用的hashtableint trehashidx; // rehash索引默认是-1因为没有进行rehash
}dictht
真正的hash表
typedef struct dictht {dictEntry **table; // 数组放我们的一个一个的key-value对就是放在数组里unsigned long size; // 数组大小unsigned long sizemask; // 掩码根据key hash计算数组里面的索引值size-1unsigned long used; // 已有的节点数量
} dictht;dictEntry
key-value 键值结构对并且里面包含链表的指针
typedef struct dictEntry {void *key; // key值union { // value值void *val;uint64_tu64;int64_ts64;
} v;struct dictEntry *next; // 指向下一个节点单向链表结构解决hash冲突问题的
} dictEntry;dictType
这个结构严格上来说并不是dict本身数据结构的一部分而是一些封装好的操作方法
typedef struct dictType {// hash方法根据关键字计算哈希值unsigned int (*hashFunction)(const void *key);// 复制keyvoid *(*keyDup)(void *privdata, const void *key);// 复制valuevoid *(*valDup)(void *privdata, const void *obj);// 关键字比较方法int (*keyCompare)(void *privdata, const void *key1, const void *key2);// 销毁keyvoid (*keyDestructor)(void *privdata, void *key);// 销毁valuevoid (*valDestructor)(void *privdata, void *obj);} dictType;结构总结
一个dict中会包含两个dicthtdict hash tabledictht中会包含所有的 dictEntry(键值对)两个dictht在扩容的时候会用到第二个
hash计算
hash dict-tpe-hashFunction(key); // Mermerhash2是hash值的计算算法 index hash dict-ht[0].sizemask; // hash值跟hashtable的sizemask掩码做一个二进制与运算算出来的结果一定是数组-size-范围内的一个数字掩码size-1算出来一定是最大也就是size-1
hash冲突
冲突是hash表常见的一个问题数组大小是固定的不同的keykey多个不同的但是不同的key算出来的hash值也是不同的不同的hash值算出来的数组里的index位置有可能是一样的
但是一直往里面写入key的时候很可能会有一个问题那就是不同的key但是算出来的index索引是一样的这就是key冲突问题了这个时候就得基于dictEntry的单向链表来挂载一个位置的多个key了
数组扩容
如果要是放的数据太多了数组放不下了这就得扩容扩容的时候每个key都得重新计算索引位置了这就是rehash扩容的时候ht[1]就是新的一个哈希表他的大小是第一个大于等于ht[0].used * 2的2n次方如果是缩容那就是第一个大于等于ht[0].used的2n次方
ht[0].used 15 * 2 30找到第一个大于等于30的2n次方2的5次方3232就是我们的下一次要扩容的数组大小
搞了一个新hash表以后就可以把ht[0]里的所有key都rehash到ht[1]里了崇安计算索引值解决key冲突问题全部迁移完毕之后就会释放掉ht[0]了把ht[1]设置为ht[0]然后在ht[1]创建空的hash表
rehash扩容缩容的触发
如果说同一个位置他的元素的个数实在是太多了单向链表太长了hget的时候keyhashindex一下子发现这个数组那里那个位置单向链表实在是太长了O(n)时间复杂度去遍历单向链表一个一个去寻找这个key
老hashtable放的数据太多了多到一定程度了就会触发rehash多到多少才会去触发rehash呢 触发rehash是跟负载因子有关系的这个负载因子计算公式是已有节点数量/哈希表数组大小就是load_factor ht[0].used / ht[0].size当我们的负载因子达到一定的程度的时候就会触发rehash动作
如果要是redis没有执行rdb和aof的持久化动作redis负载不会太高可控一些此时一直到负载因子为1就进行rehash扩容也就是数组满了再说但是如果rdb和aof再执行动作这个时候只要负载因子超过5这意思就是说rdb和aof执行的过程中你就别扩容了
rdb和aof执行的时候是要开子进程来执行的很耗费内存和cpu所以这个时候就要避免进行hash表扩容了此时无非就是说很多写入都是用单向链表挂再一个位置就行了没问题的
渐进式迁移
如果负载因子小于0.1了就要对hash表进行收缩操作扩容也好缩容也把对于ht[1]的新size的计算公式都给大家讲过了当你创建好了一个ht[1]之后迁移渐进式的迁移机制来做的
另外就是说在rehash的时候如果hash表里数据太多了你要一下子执行rehash会导致负载太高对性能有影响所以此时不是一下子全部进行rehash的一下子rehash的数量太多了会导致负载很高redis服务器的性能不对的是渐进式的分批次逐步的执行rehash动作
hashidx默认是-1改为0以后就开始rehash了每次执行hash表操作就会把indexn的所有元素迁移到ht[1]里去然后hashidx这样随着你不停的执行hash表操作就会逐步的把ht[0]各个索引位置的元素迁移到ht[1]里去了一直到所有元素都迁移完毕然后就会把rehashidx改为-1
在rehash期间新的hash操作都是针对ht[1]写入的同时迁移ht[0]在读取的时候会在ht[0]里找一下找不到再去ht[1]里找这就ok了
负载因子触发rehash新数组的size计算公式rehashidx渐进式迁移
