文档章节

redis源码阅读--hashTable

suit
 suit
发布于 2017/05/05 15:49
字数 590
阅读 11
收藏 2

公司有个项目用到hash,同事从redis的代码里抠了hashTable的源码出来,最近抽空看了一下,设计还是很精妙的。 现在把阅读的结果写写,以备后面复习可用(记得之前看过一次,后来长时间没看了就忘记了,这次再看基本要从头开始)

源码位置

图示

(摘自redis设计与实现) 参考这里 dict

设计思路

  • 这个hash(字典)他包含了两个table,为什么有两个呢?那是因为他要实现自动扩展,每次要add新元素的时候都要 判断一下是否需要扩展(expand)
  • 两个table再挂上2的倍数(size) 的桶,每个桶都是一个链表。
  • 当达到条件需要扩展的时候,一般是元素的个数和桶的比例差不多是1:1, 那就将第一个table生成第一个的size *2 为什么要是2的倍数呢?有几个好处:1.分布更均匀 2.碰撞几率更小 但是还有一个更重要的原因是: a%b可以替换成了a&(b-1) ,当hashtable的长度是2的幂的情况下。这样运算速度可以提高很多,具体可以参考这里
  • 当新的table生成后,桶数扩大了一倍,这样就大大地减少了碰撞,但是就带来了一个原来的数据是rehash的问题
  • 当rehash开始后,如果有增,删,查的操作,每次都搬一个桶到新的table上,如果已经开始rehash,那么,新增的元素就直接插到新的桶上
  • 当rehash全部完成后,旧talbe释放掉,新table接替旧table成为主力工作。
  • 还给hash设置了迭代器(iterators), 当有迭代器存在的时候,为了安全就不进行rehash的步骤。

参考资料

© 著作权归作者所有

上一篇: Hello OSC!
suit
粉丝 4
博文 24
码字总数 13208
作品 0
广州
程序员
私信 提问
qiujiayu/AutoLoadCache

AutoLoadCache 现在使用的缓存技术很多,比如Redis、 Memcache 、 EhCache等,甚至还有使用ConcurrentHashMap 或 HashTable 来实现缓存。但在缓存的使用上,每个人都有自己的实现方式,大部分...

qiujiayu
2018/09/29
0
0
高效的缓存管理解决方案 - AutoLoadCache

现在使用的缓存技术很多,比如Redis、 Memcache 、 EhCache等,甚至还有使用ConcurrentHashMap 或 HashTable 来实现缓存。但在缓存的使用上,每个人都有自己的实现方式,大部分是直接与业务代...

qiujiayu
2015/12/02
0
10
redis debug object 源码分析

问:redis的debug object命令算出来的serializedlength是如何算出的? 解答: 见redis源码中的debug.c 函数 void debugCommand(redisClient c) 的这一段代码: off_t rdbSavedObjectLen(robj...

苗永超
2016/01/27
293
2
hashMap与hashTable的区别

首先请先阅读这两个的源码。 一、hashMap、hashTable都是Map接口的实现类,但是hashMap类继承自抽象类abstractMap类,hashTable继承自 Dictionary类,该类在jdk中这样描述: 可见该类已经过时...

J星星点灯
2018/02/03
0
0
Redis为何这么快--数据存储角度

本文内容思维导图如下: 一、简介和应用 Redis是一个由ANSI C语言编写,性能优秀、支持网络、可持久化的K-K内存数据库,并提供多种语言的API。它常用的类型主要是 String、List、Hash、Set、...

我叫刘半仙
2018/10/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

HBase新建表报错 org.apache.hadoop.hbase.TableExistsException

之前安装了旧版本的hbase, 没有清理其在Zookeeper上的内容。 解决办法 stop-hbase.sh zkCli.sh >>> rmr /hbase >>> quit start-hbase.sh...

dreamness
18分钟前
1
0
大数据技术的应用现状与展望

本文是我即将由嵌入式底层驱动行业转入大数据研究领域的综述文章,案例摘自《程序员》电子期刊,由于初学者知识面较窄,查看文献量较少,因此后续还会在此基础上,继续跟踪并深入研究,为论文...

陈小君
24分钟前
1
0
NCRE考试感想 三级信息安全(上)

时间节点 报名时间:2017-06 考试时间:2017-09 查询成绩:2017-11   考试简述 满分100分,时间120分钟。题型有三种,选择题、综合题、应用题。   备考经验 题库是WLJY的,买了激活码。为了...

志成就
31分钟前
1
0
百度地图显示我的位置

<!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><title></title><script type="text/javascript" src="jquery-1.8.2.min.js"></script></head><body><sec......

塔塔米
36分钟前
1
0
mysql mysql常用的常用函数

1. 数学函数 函 数 作 用 ABS(x) 返回x的绝对值 CEIL(x),CEILIN(x) 返回不小于x的最小整数值 FLOOR(x) 返回不大于x的最大整数值 RAND() 返回0~1的随机数 RAND(x) 返回0~1的随机数,x值相同返...

edison_kwok
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部