`
xpenxpen
  • 浏览: 725154 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

redis源码阅读笔记(3)——dict

阅读更多
1.高层视角解读
字典, 又称符号表(symbol table)、关联数组(associative array)或者映射(map), 是一种用于保存键值对(key-value pair)的抽象数据结构。
请先看关于字典的一组文章
http://www.redisbook.com/en/latest/toc.html里面的第4章——字典。
字典的数据结构如图所示。


2.底层代码
代码在dict.h, dict.c这两个文件里。稍微多了一点,1600行代码。
如果读者读过java里的HashMap的源代码的话,可以发现两者的实现思路竟是惊人的相似。

2.1 hashFunction是一个可以由用户自己实现的函数,相当于java里的Object.hashCode方法。

2.2 redis自带一个哈希算法MurmurHash算法。目前的最新版本为 MurmurHash3 , 而 Redis 使用的是 MurmurHash2 。
关于MurmurHash算法的更多信息可以参考该算法的主页: http://code.google.com/p/smhasher/
在java里有一个库guava也实现了MurmurHash算法
https://code.google.com/p/guava-libraries/wiki/HashingExplained

2.3 哈希冲突的处理和java一样,采用一个链表来解决冲突,将多个哈希值相同的节点串连在一起。
因为 dictEntry 节点组成的链表没有指向链表表尾的指针, 所以为了速度考虑, 程序总是将新节点添加到链表的表头位置(复杂度为 O(1)), 排在其他已有节点的前面。
java里也是这样。

2.4 rehash和java也是惊人的相似。
负载因子(load factor)>=1时才rehash,这个似乎不太好,java里是>=0.75,因为负载因子达到某个值以后哈希冲突的概率就相当大了。

2.5 渐进式rehash是redis特有的特性,可以防止一次性rehash造成服务器停止工作。但是这个特性也使得代码到处都要考虑当前是否正在进行渐进式rehash,增加了复杂度。

2.6 字典的收缩也是redis特有的特性。
何时收缩?
t_hash.c文件中hashTypeDelete被执行时(HDEL命令)
先执行dictDelete
再执行htNeedsResize判断,如果负载因子小于10%,则调用dictResize缩小哈希表。

2.7 字典里有2个哈希表,使得rehash的时候如果遍历哈希表需要同时遍历2个哈希表。

3. 疑难点解惑
Q:dictEntry **table中**的含义?
A:**在C语言里含义是指向指针的指针,在这里的技巧含义是等价于定义了一个动态数组table中,这个数组里每个元素都是一个指针,每个指针指向一个dictEntry结构体。
table[1]的写法等价于*(table+1),也就是访问数组中的第二个元素。
分享到:
评论

相关推荐

    redis源码阅读笔记(6)——ziplist

    Redis是一款高性能的键值对数据库,其内部使用了许多优化的数据结构来存储数据,其中ziplist是Redis为了节省内存而设计...在阅读Redis源码时,深入分析ziplist的实现细节将有助于我们更好地理解和调试Redis的内存管理。

    redis源码阅读笔记(10)——事件

    在Redis源码阅读笔记(10)——事件中,我们将探讨Redis如何利用事件模型来实现非阻塞I/O,以及相关的编程模型如Reactor模式和NIO。 Redis使用了一个基于epoll的事件处理器,epoll是Linux系统提供的一种高效I/O多路...

    redis源码阅读笔记(7)——对象

    这篇源码阅读笔记主要关注Redis中的对象系统,它是Redis实现高效数据操作的关键。 在Redis中,每个数据都有一个特定的对象类型,比如`OBJ_STRING`、`OBJ_HASH`等,这些类型定义了数据的存储方式和操作行为。对象...

    redis源码阅读笔记(1)——sds

    本篇笔记将聚焦于Redis源码中的“sds”(Simple Dynamic Strings,简单动态字符串)部分,这是Redis中处理字符串的基础数据结构。 首先,我们要明白sds是什么。在C语言中,字符串是以字符数组的形式存在的,而sds是...

    redis源码阅读中文分析注释

    redis源码阅读中文分析注释

    redis/phpredis源码及文档

    Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。 附件里面包括redis源码,phpredis源码,redis指令及文档

    redis安装遇到的问题——linux centos7.5

    Redis 安装遇到的问题——Linux Centos7.5 Redis 是一个开源的、基于内存的数据结构存储系统,常用于数据库、缓存、消息队列等场景。但是,在 Linux Centos7.5 环境中安装 Redis 时可能会遇到一些问题,这篇文章将...

    Redis全套学习笔记 (带章节目录) 完整版pdf

    Redis,即远程字典服务,是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。...本文适合Redis初学者和进阶者阅读,是一份全面而实用的学习笔记。

    狂神redis源码笔记.rar

    通过阅读“狂神redis源码笔记”和解压的“redis-study”文件,你将能够深入理解Redis的内部运作,掌握Java客户端的使用技巧,提升在实际项目中运用Redis的能力。这包括但不限于了解Redis的设计模式、源码实现细节、...

    scala连接redis哨兵模式 demo 使用scala的redis库(csdn)————程序.pdf

    3. SentinelMonitoredRedisClient类:这个类是rediscala库提供的一个特性,它允许应用程序在哨兵模式下监控Redis服务器。通过这个类,Scala程序可以实现对Redis哨兵系统提供的高可用性支持。 4. 配置哨兵服务器:在...

    redis的可视化工具——redisdesktopmanager

    8. **版本更新**:例如,提供的`redisdesktopmanager0.9.3.817.exe`是该工具的一个特定版本,每个新版本通常会修复已知问题,增加新功能,提升用户体验。 9. **安全性**:尽管提供图形界面,但用户仍需谨慎处理敏感...

    redis源码资源下载

    Redis(Remote Dictionary Server),即远程字典服务,是一个开源的、高性能的、基于内存的Key-Value数据库,它使用ANSI C语言编写,支持网络,并提供了多种语言的API。Redis以其丰富的数据结构、高性能、持久化特性...

    Redis全套学习笔记 完整版pdf.rar

    Redis全套学习笔记 完整版pdf.rar set:添加键值对 get:获取值 apend:追价值 strlen:获取值的长度 setnx:key不存在时,设置key的值 incr:原子递增1 decr:原子递减1 incrby/decrby:递增或者递减指定的数字 ...

    Redis全套学习笔记-带章节目录-114页.pdf

    Redis全套学习笔记 Redis是一种基于内存的NoSQL数据库,具有高性能、可扩展性和灵活性等特点。以下是Redis的详细知识点: 安装和启动 * 安装Redis可以通过下载软件包或使用yum、apt-get等安装工具进行安装。 * ...

    Redis Windows源码

    3. 源码编译与配置: 要在Windows上编译Redis源码,首先需要安装GCC编译器(如MinGW)和make工具。然后,使用`make`命令编译源码,配置时可能需要修改`src/Makefile`以适应Windows环境。编译完成后,将生成可执行...

    redis源码安装以及配置

    **一、Redis源码安装** 1. **下载源码** 首先,我们需要从Redis官方网站或者GitHub仓库下载源码。在这个例子中,我们使用的是`redis-2.8.9.tar.gz`。你可以通过命令行工具如`wget`或`curl`来下载,或者直接在网页...

    Redis全套学习笔记

    Redis 安装简单,可以通过源码编译或使用包管理器安装。启动Redis有前台和后台两种方式,后台启动更常见。Redis 可通过`redis-cli`命令行工具进行交互,提供一系列命令用于操作数据库。 2. Redis 数据类型: - **...

    狂神说-Redis完整版笔记

    【Redis完整版笔记】深入解析Redis作为NoSQL数据库的关键特性 Redis是一款高性能的Key-Value内存数据库,广泛应用于缓存、消息队列、计数器等多个场景。在NoSQL数据库的大潮中,Redis以其出色的速度和灵活性...

Global site tag (gtag.js) - Google Analytics