Redis哈希对象的ziplist编码实现了O(1)复杂度吗

Stella981
• 阅读 508

问题:Redis中哈希对象有两种编码方式,分别是ziplist、hashtable方式。哈希对象,总得体现哈希算法,使得基本操作达到O(1)的效率。hashtable编码方式使用字典,也即是Java中hashMap的方式,这个我可以理解。但是,ziplist方式所有元素都是紧挨的,它是怎么实现hash,并使得查询等操作有O(1)的时间效率的呢?

让我们从方法调用开始分析。我们都知道,获取哈希对象中某个元素的命令是“HGET”,当哈希对象的编码方式是ziplist时,它的执行过程如下:

  • 首先调用ziplistFind函数,在压缩列表中查找指定键对应的节点。
  • 然后调用ziplistNext函数,将指针移动到键节点旁边的值节点,最后返回值节点。

从HGET命令在ziplist编码下的执行过程可以看出,问题的关键在ziplistFind方法中。
ziplistFind方法在Redis源码的src/ziplist.c中:

从黄建宏先生的源码注释( 源码看不懂:) )可以看出,该方法通过遍历列表实现查找,花费O(N2)时间。由此可以得到我们的结论:

使用ziplist编码方式的哈希对象不能实现O(1)复杂度的基本操作,而是通过遍历来查找元素。sat培训班不过,ziplist编码方式只有在所有键值长度小于64字节,且哈希对象保存的键值对数量小于512个时才使用,因此,它对效率的影响并没有想象中的那么大。

当Redis哈希对象使用另一种编码——hashtable编码时它保证了基本操作O(1)复杂度吗?
是的,它提供了。hashtable编码方式使用字典(类似于Java中的HashMap)作为底层数据结构,当进行查找时,调用的是dictFind方法,它的源码如下:

可以看到,它实现了O(1)的查找复杂度。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Karen110 Karen110
2年前
​一篇文章总结一下Python库中关于时间的常见操作
前言本次来总结一下关于Python时间的相关操作,有一个有趣的问题。如果你的业务用不到时间相关的操作,你的业务基本上会一直用不到。但是如果你的业务一旦用到了时间操作,你就会发现,淦,到处都是时间操作。。。所以思来想去,还是总结一下吧,本次会采用类型注解方式。time包importtime时间戳从1970年1月1日00:00:00标准时区诞生到现在
Wesley13 Wesley13
2年前
Java日期时间API系列31
  时间戳是指格林威治时间1970年01月01日00时00分00秒起至现在的总毫秒数,是所有时间的基础,其他时间可以通过时间戳转换得到。Java中本来已经有相关获取时间戳的方法,Java8后增加新的类Instant等专用于处理时间戳问题。 1获取时间戳的方法和性能对比1.1获取时间戳方法Java8以前
Stella981 Stella981
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Stella981 Stella981
2年前
Nginx + lua +[memcached,redis]
精品案例1、Nginxluamemcached,redis实现网站灰度发布2、分库分表/基于Leaf组件实现的全球唯一ID(非UUID)3、Redis独立数据监控,实现订单超时操作/MQ死信操作SelectPollEpollReactor模型4、分布式任务调试Quartz应用
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这