hash对象的理解?

简介: 《基础》

在Redis中,value可以是一个hash表,底层编码可以是ziplist,也可以是hashtable(默认情况下,当元素小于512个时,底层使用ziplist存储数据)

ziplist

元素保存的字符串长度较短且元素个数较少时(小于64字节,个数小于512),出于节约内存的考虑,hash表会使用ziplist作为的底层实现,ziplist是一块连续的内存,里面每一个节点保存了对应的key和value,然后每个节点很紧凑地存储在一起,优点是没有冗余空间,缺点插入新元素需要调用realloc扩展内存。(可能会进行内存重分配,将内容拷贝过去,也可能在原有地址上扩展)。

hashtable

元素比较多时就会使用hashtable编码来作为底层实现,这个时候RedisObject的ptr指针会指向一个dict结构,dict结构中的ht数组保存了ht[0]和ht[1]两个元素,通常使用ht[0]保存键值对,ht[1]只在渐进式rehash时使用。hashtable是通过链地址法来解决冲突的,table数组存储的是链表的头结点(添加新元素,首先根据键计算出hash值,然后与数组长度取模之后得到数组下标,将元素添加到数组下标对应的链表中去)。

struct dict {
    int rehashindex;
    dictht ht[2]; 
}
struct dictht {
    dictEntry** table; // 二维
    long size; // 第一维数组的长度 
    long used; // hash 表中的元素个数 ...
}
typedef struct dictEntry {
  //键  
  void *key;
  //值,可以是一个指针,也可以是一个uint64_t整数,也可以是int64_t的整数
  union {
    void *val;
    uint64_tu64;
    int64_ts64;
  } v;
  //指向下一个节点的指针
  struct dictEntry *next;
} dictEntry;点击复制代码复制出错复制成功

渐进式rehash

进行当负载因子>=1时,会进行哈希表扩展操作(如果是在执行BGSAVE或BGREWRITEAOF命令期间,那么需要>=5才会进行扩展)。

进行当负载因子<0.1时,会进行哈希表收缩操作。

因为直接一次性完成rehash会对性能产生影响,所以可以渐进式rehash,具体执行步骤是:

初始化

1.首先将对dict结构中ht[1]哈希表分配空间(大小取决于最接近实际使用空间的2的n次方幂),然后将rehashindex属性设置为0。

转移

2.这种渐进式rehash转移元素不是全部转移,如果在rehash时全部转移,可能会导致rehash期间Redis实例无法处理后面的请求,所以采取的策略是每次用到某个下标下的键值对才进行转移这个下标下所有的键值对。然后每次对ht[0]中的元素查找,修改,添加时,除了执行指定操作外,还会将对应下标的所有键值对rehash到ht[1],并且会将rehashindex+1。

更改指针指向

3.当ht[0]中所有键值对都是rehash到ht[1]中后,那么会ht[1]和ht[0]的指针值进行交换,将rehashindex设置为-1,代表rehash完成。 (整个rehash期间,查找,更新,删除会先去ht[0]中执行,没有才会到ht[1]中执行,新添加键值对是会被保存到ht[1]中)。

相关文章
|
1月前
|
存储 负载均衡 算法
Hash介绍与应用详解
哈希算法在计算机科学中有着广泛而重要的应用,从数据存储、数据完整性校验到密码安全和分布式系统中的负载均衡,哈希函数都发挥着关键作用。通过本文的介绍和示例代码,希望您能更好地理解哈希的基本概念和实际应用,并在您的项目中有效地应用这些知识。
170 3
|
5月前
|
存储 Java
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD
|
7月前
|
Shell
|
存储 算法
hash
一.什么是hash 百度百科上的定义是: 是把任意长度的输入通过散列算法变换成固定长度的输出,该输出就是散列值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
108 0
|
存储 算法 数据安全/隐私保护
Hash 的定义
Hash,一般翻译做散列、杂凑,或音译为哈希。
158 0
|
前端开发 JavaScript
hash、chunkhash和contenthash
webpack 通用配置优化
131 0
hash、chunkhash和contenthash
|
存储 编译器
查找——HASH
查找——HASH
248 0
查找——HASH
|
存储 Linux C++
map和hash_map的区别
map和hash_map的区别
172 0
下一篇
DataWorks