Redis dict_jollyjumper的博客-程序员宅基地

技术标签: hashtable  Linux  Redis  dict  

今天看了redis dict部分的源码(dict.h,dict.c),跟大家分享一下。

这两个文件包含了redis的hashtable的接口和实现。

Redis中hashtable的主要特点是增量rehash,rehash毕竟是一个耗时的操作,redis把它分摊到hashtable的各个小操作中,从而让字典操作性能曲线比较平滑。

既然要增量rehash,就要在一个dict中保留两个hashtable,分批次从hashtable[0]搬运元素到hashtable[1]中。

dict的iterator,iterator分为安全的iterator和不安全的iterator,安全的iterator锁定dict,不让它进行rehash及新增元素,直到它释放为止(dict中对安全iterator进行计数)。(这个做法颇有启发)

redis中hashtable的数组总是2的幂,按照数据结构的理论,理想的应该是素数,作者可能是为了方便或是hash计算时更快速。

dict 中提供了两个hash函数,unsigned int dictGenHashFunction(const void *key, int len);这是大名鼎鼎的MurmurHash2,unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len);这是字符串中常用的hash算法(djb hash),只是不区分大小写,从seed开始,hash*33+char。当然也有获得和设置hash seed的接口。

主要的结构如下:

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;


typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    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;
    } v;
    struct dictEntry *next;
} dictEntry;

有一些简单接口用宏包装,rehash触发的条件是used / size > 5。

一般的操作都会做一步rehash即把一个bucket从ht[0]放到ht[1]中,但是replace接口会做两次,因为会先调用find,再调用Add。

有专门的rehash接口,指定rehash几步,还可以指定花多少时间用于rehash,它实际上是每rehash100步检查下时间知道时间超出。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/jollyjumper/article/details/9107933

智能推荐

西门子200实现远程监控和程序调试_weixin_33806300的博客-程序员宅基地

2019独角兽企业重金招聘Python工程师标准>>> ...

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。_Tom Hardy的博客-程序员宅基地

题目描述输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)题目分析这里有一个陷阱,栈的弹出序列不一定是栈的压入序列的倒序,因为有可能在压入的过...

0429建立Extended Statistics函数索引问题_weixin_33994444的博客-程序员宅基地

[20160429]建立Extended Statistics 和函数索引问题.txt --11G支持相关数据的统计分析,比如如果两个字段存在相关性通过分析,能够得到更加良好的统计信息,以及生成好的执行计划. --但是如果结合函数索引呢?通过一个简单的例子来说明: --前次做的测试: http://blog.it...

43个功能测试点总结_iteye_15968的博客-程序员宅基地

43个功能测试点总结 软件测试  功能测试就是对产品的各功能进行验证,根据功能测试用例,逐项测试,检查产品是否达到用户要求的功能。针对Web系统的常用测试方法如下:  1. 页面链接检查:每一个链接是否都有对应的页面,并且页面之间切换正确。可以使用一些工具,如LinkBotPro、File-AIDCS、HTML Link Validater、Xenu等工具。LinkBotPro不支持...

UBOOT UART设置(基于mini2440)_羽落飞扬剑舞意的博客-程序员宅基地

基于mini2440的UBOOT UART设置1. 标准9针串口引脚定义根据图3.40的引脚顺序号,如果是作为RS-232C接口,则各引脚定义如表3.2所示。表3.2RS-232C引脚意义表各引脚的电气特性为:在TxD和RxD上,逻辑“1”为-3V~-15V; 逻辑“0”为+3V~+15V。在RTS、CTS、DSR、DTR和DCD等控制线上,信号有效为+3V~+

浅谈MFC类CrackMe中消息处理函数查找方法_weixin_30755709的博客-程序员宅基地

最近一个学姐发给我了一份CrackMe希望我解一下,其中涉及到了MFC的消息函数查找的问题,就顺便以此为例谈一下自己使用的消息函数查找的方法。本人萌新,如果有任何错漏与解释不清的地方,欢迎各路大佬指正。这个CrackMe是一个典型的MFC类型的程序,其框体如下:一、目标以及方法首先我们确认我们的目标是找到两个”注册”按钮的对应消息处理函数,那么有什么手段可以达到我们的目标?在MFC...

随便推点

开源ETL工具kettle系列之增量更新设计技巧_青龙白虎米老鼠的博客-程序员宅基地

ETL中增量更新是一个比较依赖与工具和设计方法的过程,Kettle中主要提供Insert / Update 步骤,Delete 步骤和Database  Lookup  步骤来支持增量更新,增量更新的设计方法也是根据应用场景来选取的,虽然本文讨论的是Kettle的实现方式,但也许对其他工具也有一些帮助。本文不可能涵盖所有的情况,欢迎大家讨论。应用场景增量更新按照数据种类的不同大概可以分成:

PTA基础编程题目集7-4~7-6(C++)_return-0的博客-程序员宅基地

7-4 BCD解密 (10 分)BCD数是用一个字节来表达两位十进制的数,每四个比特表示一位。所以如果一个BCD数的十六进制是0x12,它表达的就是十进制的12。但是小明没学过BCD,把所有的BCD数都当作二进制数转换成十进制输出了。于是BCD的0x12被输出成了十进制的18了!现在,你的程序要读入这个错误的十进制数,然后输出正确的十进制数。提示:你可以把18转换回0x12,然后再转换回12。输入格式:输入在一行中给出一个[0, 153]范围内的正整数,保证能转换回有效的BCD数,也就是说这

获取设备IMEI ,手机名称,系统SDK版本号,系统版本号_weixin_33735077的博客-程序员宅基地

1、获取设备IMEI TelephonyManager tm = (TelephonyManager) getSystemService(Context.TELEPHONY_SERVICE); String IMEIs = tm.getDeviceId() ;需要的权限 <uses-permission androi...

Github配置_Andrew_Zhu的博客-程序员宅基地

-----如果你的代码不知道放哪里好,放到github是一个不错的选择。下面奉上一文入门级别的配置篇。(以下配置同时适用于window和linux) 在github注册完后,首先创建一个仓库(repositry),在你的个人页面右边"Your Repositories"模块,点击 New repository,这里我们把project name 填写

snmp_diexian5592的博客-程序员宅基地

snmpd作为一个服务,本身有系统的一些信息,外部可以通过snmp -get ,walk来获取,而snmptrap理解为一个陷阱,等着掉进来猎物,就是一个收数据的服务,但是收到的数据和snmpd中呈现的数据时互不相关的,两个是独立的,snmptrap收到的数据打到一个日志文件中,通过snmptt可以进行简单的过滤操作,使得拿到的数据更加的符合要求。snmptrap数据收集流程s...

【hihocoder】1515 - 分数调查 (带权并查集)_Dicer_的博客-程序员宅基地

题目链接文章推荐:点击查看用val[x]存放x与根节点的差。感觉带权并查集的find函数跟merge函数有很多递归回溯的思想。 还有大佬说向量偏移之类的,我觉得应该就是利用关系之间的传递性。AC代码:#include <bits/stdc++.h>using namespace std;const int N = 2e5;int n, m, q, x, ...