做网站南充,wordpress主题国内模板,番禺大石网站建设,沈阳关键词推广hash实现 redis的hash数据结构和java的HashMap虽然不同#xff0c;但是有异曲同工之妙#xff0c;value是键值对#xff0c;相当于HashMap#xff0c;对于hash碰撞也是采用的类似于HashMap的处理方式#xff0c;数组链表#xff0c;更适合存储对象#xff0c;将一个对象… hash实现 redis的hash数据结构和java的HashMap虽然不同但是有异曲同工之妙value是键值对相当于HashMap对于hash碰撞也是采用的类似于HashMap的处理方式数组链表更适合存储对象将一个对象存储在hash类型中会占用更少的内存且可以更方便的存取整个对象 编码格式 编码对象OBJ_ENCODING_ZIPLIST使用ziplistOBJ_ENCODING_HT使用的hash table set有两种编码格式 ziplist 一开始存储使用的ziplist但是当满足一定条件时会转换为hash table hash table #根据该配置项来进行编码转换的# ziplist的节点数量限制hash-max-ziplist-entries 512# 键或者值的长度限制hash-max-ziplist-value 64 源码结构 // 哈希表数据结构typedef struct dict { // 类型 dictType *type; // 私有数据存储一些额外的数据 void *privdata; // 哈希表 // ht[0]:用来存放真是的数据 // ht[1]:用于扩容/缩容 dictht ht[2]; // 哈希表重置下标指定的是哈希数组的数组下标 //rehash 如果为-1表示没有进行rehash用来记录迁移的索引位置 long rehashidx; /* rehashing not in progress if rehashidx -1 */ // 如果大于0则暂停rehash int16_t pauserehash; /* If 0 rehashing is paused (0 indicates coding error) */} dict;typedef struct dictht { // 哈希表数组保存的是dictEntry结构的数据就像HashMap中的Entry一样存储的KV键值对 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码用于计算索引值 unsigned long sizemask; // 哈希表已有节点数量 unsigned long used;} dictht;typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; double d; } v; // 下一个哈希节点链表为了解决哈希冲突问题形成链表 struct dictEntry *next;} dictEntry; redis哈希冲突将新节点添加在链表的表头 过程分析 添加元素 向字典中添加元素将会为字典中的ht[0]分配空间默认情况下table数组为4(DICT_HT_INITIAL_SIZE)新添加元素的键值会经过哈希算法确定哈希表数组的位置进行添加如果两个不同的键经过哈希算法产生相同的哈希值就会发生哈希冲突采用链表的方式新元素会放到链表头节点(与java7类似因为新增加的节点大概率会被再次访问) 扩容 扩容的时候会将ht[0]的所有键值都迁移到h[1]中当节点全部迁移完毕后释放ht[0]的占用空间并将ht[1]设置为ht[0]由于redis中可能存的数据量比较大所以进行rehash的时间可能会很长而rehash又是一个阻塞的操作所以redis采用的是渐进式的迁移方式rehashidx就是为这个操作而设置的属性用来记录索引位置的默认为-1当进行迁移的时候设置为0每次接收到增加删除查找更新命令时除了执行该命令外还需要将rehashidx索引上的节点迁移到ht[1]迁移之后rehashidx1当所有的数据都迁移到ht[1]中时rehashidx会被重新设置为-1 https://zhhll.icu/2021/数据库/非关系型数据库/redis/底层实现/5.hash实现/ 本文由 mdnice 多平台发布
