redis 数据结构 字典

xiaoxiao2021-03-01  8

哈希表和字典 结构:要点rehash时机redis内的使用

哈希表和字典

我就不明白了,c里面没有,c++的stl里有啊,redis为什么要自己实现

结构:

/** * 哈希节点 **/ typedef struct dictEntry{ void *key;//键,任意类型 union{//值,三选一,或者是自定义val,或者是无符号64位整型,或者有符号64位整型 void *val; uint64_tu64;// ts64是啥 int64_ts64;//同,ts64是啥 } struct dictEntry *next; } /** * 哈希表 **/ typedef struct dictht{ dictEntry **table;//指向dictEntry数组的指针,*dictEntry是指向一个哈希节点,**dictEntry是指向一个节点数组的 unsigned long size;//数组的大小 unsigned long sizemark;//和java的hashMap一样,有一个掩码,大小等于size-1,用于落桶的计算 unsigned long used;//当前已有节点个数 } /** * 字典 **/ typedef struct dict{ /** type和privatedata是类型特定的函数 **/ dictType *type;//一个dictType内保存一组用于特定类型的hash计算、键比较,复制键值,删除键值的方法 void *privatedata;//保存向dictType内函数传参的参数,更多细节,还需向后看 /** end **/ dictht ht[2];//两个hashTable,一般ht[0]用于正常存储,另一个在rehash的时候被需要,rehash是一个长期的过程,所以,存在一段时间内,两个ht内都有数据的情况 int rehashIndex;//rehash时使用,表明当前需要操作的dictEntry数组的下标,当不在rehash的时候,该值为-1 }

要点

哈希表使用链表法解决hash冲突的问题,而且链表使用头插法,将最近的冲突节点放到链表头部,复杂度为o(1),这里的链表是单链表 2 rehash,当达到负载因子的阈值的时候,启动rehash,redis的rehash不是一口气完成的,而是将其拆解到每一次对字典的操作(增删改查)当中,每一次rehash原哈希表的一个数组的链表到另一个哈希表中,这个时候rehashIndex的作用就是表明下一个将要进行rehash操作的数组下标。进行完rehash后,会将新的哈希表设为ht[0]使用

rehash时机

负载因子计算:和java 的hashmap一样,使用节点数/数组大小表示,需要注意的是,节点数不是已使用的桶(bucket)数量,也就是说,如果所有节点hash都一样,进而解决hash冲突放到同一个dictEntry的链表里,它们每一个都会被用于负载因子的计算。什么时候扩大:负载因子大于等于1,并且服务器没有执行BGSAVE,BGREWRITEAOF指令;或者服务器在执行BGSAVE或BGREWRITEAOF指令,并且负载因子大于等于5如何扩大:当前已有节点数*2的最近的2的幂次为什么要区别BGSAVE和BGREWRITEAOF指令?这两个指令会导致redis服务器启动子进程,而在子进程内,数据是和父进程共享的,只有需要改变时使用写时复制的方式将修改的数据新建一份,所以为了防止子进程新建数据,提高性能,会区别这两个指令。什么时候缩小:当负载因子小于0.1的时候如何缩小:当前已有节点数,的最近的2的幂次

redis内的使用

redis数据库本身,以及哈希键值等

转载请注明原文地址: https://www.6miu.com/read-3099949.html

最新回复(0)