1.为字典的 ht[1] 哈希表分配空间， 这个哈希表的空间大小取决于要执行的操作， 以及 ht[0] 当前包含的键值对数量 （也即是ht[0].used 属性的值）：
在Redis中，rehash是指当哈希表的负载因子（load factor）超过设定阈值时，为了保证哈希表的性能，系统会自动触发rehash操作。Rehash操作指的是将原来的哈希表重新建立一个更大的哈希表，并将原有的键值对重新映射到新的哈希表上。
Redis的字典使用哈希表作为底层实现，一个哈希表里面有多个哈希表节点,而每个哈希表节点保存了字典中的一个键值对（key-value）
Redis一共支持5种数据结构，hash是其中的一种，在hash扩容的时候采用的是渐进式rehash的方式。要想深入理解渐进式rehash，首先要了解以下Redis中hash的数据结构。
在上一节，我们了解了字典的rehash 过程，需要特别指出的是，rehash 程序并不是在激活之
字典，是一种用于保存键值对的抽象数据结构。由于 C 语言没有内置字典这种数据结构，因此 Redis 构建了自己的字典实现。
在字典结构体中，包含了一组字典函数(dictType)，通过封装的方法处理对应的操作，通常在字典初始化的时候对其进行配置。
在 dict.h 文件中，Hash 表是一个二维数组（dictEntry **table）。
字典（dictionary）， 又名映射（map）或关联数组（associative array）是一种抽象数据结构， 由一集键值对（key-value pairs）组成。
Redis Hashes 是我们日常使用中比较高频的 Redis 数据类型，内部使用 Redis 字典结构存储，底层实现之一为哈希表结构。
字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。
字典，又被称为符号表（symbol table）或映射（map），其实简单地可以理解为键值对key-value。
字典类型容量变化过程叫做rehash,需要满足一定的条件才能触发扩容机制 服务器当前没有进行BGWRITEAOF或者BGSAVE命令，且当前键值对个数超过一维数组的大小，才会触发扩容。
1. 数据结构 1.1 哈希表 typedef struct dictht{ dictEntry **table; unsigned long size; unsigned long si
有了《Redis源码解析——字典结构》的基础，我们便可以对dict的实现进行展开分析。（转载请指明出于breaksoftware的csdn博客）
Redis 是一个高性能的 key-value 内存数据库，与 Memcached 只能存储字符串数据类型不一样，它支持存储的数据结构类型包括：字符串（string）、链表（lists）、哈希表（hash）、集合（set）、有序集合（zset）等。
在 C 语言中，字符串可以用一个 \0 结尾的 char 数组来表示。 比如说，hello world 在 C 语言中就可以表示为 “hello world\0” 。
相信大家对hashMap都不陌生，其底层结构是数组加链表加红黑树（红黑树这里不展开），数组默认大小为16，通过key的hash值可以实现从键到值的快速访问。
说明：next 为指向下一个节点的指针，是我们熟悉的链表节点结构，单向链表，用于处理键哈希冲突问题。
此处我下载的是 redis-6.2.5 版本的，xdm 可以直接下载上图中的 **redis-6.2.6 **版本，
熟悉Redis的人都知道，它是单线程的。因此在使用一些时间复杂度为O(N)的命令时要非常谨慎。可能一不小心就会阻塞进程，导致Redis出现卡顿。
《Redis设计与实现》读书笔记（二） ——Redis中的字典（Hash） （原创内容，转载请注明来源，谢谢） 一、概述 字典，又称符号表、关联数组、映射，是一种保存键值对的抽象数据结构。每个键（key）和唯一的值（value）关联，键是独一无二的，通过对键的操作可以对值进行增删改查。 redis中字典应用广泛，对redis数据库的增删改查就是通过字典实现的。即redis数据库的存储，和大部分关系型数据库不同，不采用B+tree进行处理，而是采用hash的方式进行处理。 另外，毫无疑问，redis的hash
Redis Hash（散列表）是一种 field-value pairs（键值对）集合类型，类似于 Python 中的字典、Java 中的 HashMap。一个 field 对应一个 value，你可以通过 field 在 O(1) 时间复杂度查 field 找关联的 field，也可以通过 field 来更新或者删除这个键值对。
Redis 的数据库使用字典实现, 对数据库的增, 删, 查, 改也是构建在对字典的操作之上的.
1） 首先创建一个比现有哈希表更大的新哈希表（expand） 2） 然后将旧哈希表的所有元素都迁移到新哈希表去（rehash）
Redis 是一个键值对数据库，其键是通过哈希进行存储的。整个 Redis 可以认为是一个外层哈希，之所以称为外层哈希，是因为 Redis 内部也提供了一种哈希类型，这个可以称之为内部哈希。当我们采用哈希对象进行数据存储时，对整个 Redis 而言，就经过了两层哈希存储。
建议先阅读：神奇，Redis存储原理竟然是这样！ – Karos (wzl.fyi)，或者本页面的第一章
这周开始学习 Redis，看看Redis是怎么实现的。所以会写一系列关于 Redis的文章。这篇文章关于 Redis 的基础数据。阅读这篇文章你可以了解：
SCAN命令可以为用户保证：从完整遍历开始直到完整遍历结束期间，一直存在于数据集内的所有元素都会被完整遍历返回，但是同一个元素可能会被返回多次。如果一个元素是在迭代过程中被添加到数据集的，又或者是在迭代过程中从数据集中被删除的，那么这个元素可能会被返回，也可能不会返回。
HashTable：Redis中有一个「全局哈希表」，该哈希表中保存所有的键值对。对于Hash表的查找操作时间复杂度为O(1)
那个深夜，我登上了公司的服务器，在Redis 命令行里敲入 keys* 后，线上开始报警，服务瞬间被卡死，我只能举起双手，焦急地等待几千万key被慢慢扫描，束手无策万念俱灰的时候，我收到了leader的短信：你明天不用来上班了。
在 Redis 中所有的 key 都存储在一个很大的字典中，这个字典的结构和 Java 中的 HashMap 一样，是一维数组 + 二维链表结构，如下图，第一维数组的大小总是 2^n(n>=0) ，扩容一 次数组大小空间加倍，也就是 n++
redis旧版小hash使用的数据结构，紧密数组存储结构 用1字节存储总节点数（如果1字节满了，代表需要遍历到底才知道有多少节点） 每个节点存储自己占用的内存空间，修改删除后，标记为闲置空间，闲置空间不压缩不回收，留用节点扩展或者插入节点 这也代表插入没有足够闲置时要O(n)移动后续内存 数据也是占用zipmap内存，所以查找是O(n)（利用len做快表跳跃）
HashMap的容量是有限的。当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。
字典这种数据结构并不是 Redis 那几种基本数据结构，但是 hash ， sets 和 sorted sets 这几种数据结构在底层都是使用字典来实现的（并不仅仅是字典），现在看下它的实现原理。
在Redis中，如果哈希表的数组一直保持不变，就会增加哈希冲突的可能性，从而降低检索效率。为了解决这个问题，Redis会对数组进行扩容，通常是将数组大小扩大为原来的两倍。然而，这个扩容过程会引起元素在哈希桶中的分散，导致元素的移动。由于元素移动会涉及IO操作，所以这个重新哈希（ReHash）过程可能会导致许多请求被阻塞。
字典在Redis中的作用是非常巨大的，对Redis数据库的增删改查等操作都构建在对字典的操作之上，因此，了解字典的底层实现能让我们对Redis有更深的理解。下面分4个模块讲解Redis的字典实现（基本所有实现细节和重点都会谈到）：
首先简单介绍几个概念：哈希表（散列表）、映射、冲突、链地址、哈希函数。
哈希表具有O(1)复杂度和快速查找特性，但是Redis中写入大量数据后，就可能发现操作有时候会突然变慢了。这其实是因为你忽略了一个潜在的风险点，那就是哈希表的冲突问题和rehash可能带来的操作阻塞。
散列表(哈希表)，其思想主要是基于数组支持按照下标随机访问数据时间复杂度为O(1)的特性。可以说是数组的一种扩展。假设，我们为了方便记录某高校数学专业的所有学生的信息。要求可以按照学号(学号格式为:入学时间+年级+专业+专业内自增序号，如2011
本文跟大家聊一聊一个常见的面试题，那就是JDK1.8 HashMap扩容rehash算法是如何优化的？
Squirrel（松鼠）是美团技术团队基于Redis Cluster打造的缓存系统。经过不断的迭代研发，目前已形成一整套自动化运维体系，涵盖一键运维集群、细粒度的监控、支持自动扩缩容以及热点Key监控等完整的解决方案。同时服务端通过Docker进行部署，最大程度的提高运维的灵活性。分布式缓存Squirrel产品自2015年上线至今，已在美团内部广泛使用，存储容量超过60T，日均调用量也超过万亿次，逐步成为美团目前最主要的缓存系统之一。
redis的快主要体现在我们可以根据键值对能以微妙级别的速度找到数据，并快速完成操作。
Redis是目前最流行的内存数据库之一，而redis成为最流行的原因就是’快’，即在微妙级别就能够通过键找到对应的值并返回。那么很多人就会问redis为何这么快呢？除了其读写操作都在内存中执行和独特的网络模型设计，以及其巧妙的数据结构之外，还要归功于独特的键值对存储结构。对于redis的网络模型和具体的数据结构后续篇幅再进行讲解，此篇文章仅对于redis中键值对数据的存储进行分析。
就这种源码中的数据结构啊，我个人是比较推崇大家自己先看概念手写一个，能不能动咱另说，在写的过程中会领悟到很多直接看所领悟不到的细节。
字典相对于数组，链表来说，是一种较高层次的数据结构，像我们的汉语字典一样，可以通过拼音或偏旁唯一确定一个汉字，在程序里我们管每一个映射关系叫做一个键值对，很多个键值对放在一起就构成了我们的字典结构。
struct dict:为hash table的外层封装，主要一个作用是当当前使用dictht需要进行rehash的时候，其会创建新的dictht,并且会在词请求的时候，完成一部分的搬运工作
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
