Redis之常用数据结构哈希表

目录
  • 1.哈希冲突
  • 2.链式哈希
  • 3.rehash
  • 4.渐进式 rehash
  • 5.rehash 触发条件

哈希表是一种保存键值对（key-value）的数据结构

哈希表优点在于，它能以 O(1) 的复杂度快速查询数据。

怎么做到的呢？

将 key 通过 Hash 函数的计算，就能定位数据在表中的位置，因为哈希表实际上是数组，所以可以通过索引值快速查询到数据。

在哈希表大小固定的情况下，随着数据不断增多，那么哈希冲突的可能性也会越高。

Redis 采用了**「链式哈希」**来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接起，以便这些数据在表中仍然可以被查询到

1.哈希冲突

哈希表实际上是一个数组，数组里的每一个元素就是一个哈希桶

当一个键值对的键经过 Hash 函数计算后得到哈希值，再将(哈希值 % 哈希表大小)取模计算，得到的结果值就是该 key-value 对应的数组元素位置，也就是第几个哈希桶

当有两个以上数量的 kay 被分配到了哈希表中同一个哈希桶上时，此时称这些 key 发生了冲突

2.链式哈希

链式哈希是怎么实现的？

实现的方式就是每个哈希表节点都有一个 next 指针，用于指向下一个哈希表节点，因此多个哈希表节点可以用 next指针构成一个单项链表，被分配到同一个哈希桶上的多个节点可以用这个单项链表连接起来，这样就解决了哈希冲突。

随着链表长度的增加，在查询这一位置上的数据的耗时就会增加，因为链表的查询的时间复杂度是 O(n)。

3.rehash

Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht[2]）

之所以定义了 2 个哈希表，是因为进行 rehash 的时候，需要用上 2 个哈希表
在正常服务请求阶段，插入的数据，都会写入到「哈希表 1」，此时的「哈希表 2 」 并没有被分配空间。

随着数据逐步增多，触发了 rehash 操作，这个过程分为三步：

1.给「哈希表 2」 分配空间，一般会比「哈希表 1」 大 2 倍；
2.将「哈希表 1 」的数据迁移到「哈希表 2」 中；
3.迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建一个空白的哈希表，为下次 rehash 做准备。

第二步很有问题，如果「哈希表 1 」的数据量非常大，那么在迁移至「哈希表 2 」的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求

4.渐进式 rehash

为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况

渐进式 rehash 步骤如下：

1.给「哈希表 2」 分配空间；
2.在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上；
3.随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。

把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作

1.查找一个 key 的值的话，先会在「哈希表 1」 里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。

2.新增一个 key-value 时，会被保存到「哈希表 2 」里面，而「哈希表 1」 则不再进行任何添加操作，这样保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1 」就会变成空表

5.rehash 触发条件

触发条件跟**负载因子（load factor）**有关系。

主要有两个：

1.当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
2.当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作

到此这篇关于Redis之常用数据结构哈希表的文章就介绍到这了,更多相关Redis哈希表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Redis五种数据结构在JAVA中如何封装使用

    Redis五种数据结构在JAVA中如何封装使用

    目录 数据结构 string字符串 string字符串简介 string字符串在Java中的封装 list列表 list列表简介 队列 栈 list列表在Java中的封装 hash(字典) hash字典简介 hash字典在Java中的封装 set(集合) set集合简介 set集合在Java中的封装 zset(有序列表) zset有序列表 zset有序列表在Java中的封装 数据结构 Redis有五种基础数据结构,分别为: 1.string(字符串) 2.list(列表) 3.hash(字典)

  • Redis底层数据结构之dict、ziplist、quicklist详解

    Redis底层数据结构之dict、ziplist、quicklist详解

    目录 1 Redis dict 1.1 扩缩容的条件 1.2 渐进式rehash操作 2 Redis ziplist 2.1 ziplist结构 2.2 entry结构 3 Redis quicklist 此前我们学习了常见的Reids数据类型,这些数据类型都需要底层的数据结构的支持,现在我们来看看Redis常见的底层数据结构:dict.ziplist.quicklist. 1 Redis dict dict就是"字典"的意思,它是Redis中的一种使用的非常多的底层的数据结构,除了h

  • Redis的六种底层数据结构(小结)

    Redis的六种底层数据结构(小结)

    目录 1.简单动态字符串(SDS) 2.链表 3.字典 哈希表 哈希表节点 字典 4.跳跃表 跳跃表节点(zskiplistNode) 跳跃表(zskiplist) 5.整数集合 6.压缩列表 1.简单动态字符串(SDS) Redis 虽然是用 C 语言写的,但Redis没有直接使用C语言传统的字符串表示(以空字符 ‘\0’ 结尾的字符数组),二是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将 SDS 作为 Redis的默认字符串表示.在R

  • 多维度深入分析Redis的5种基本数据结构

    多维度深入分析Redis的5种基本数据结构

    目录 一.简介 二.string(字符串) 1.string(字符串)相关介绍 1.1 string(字符串)的内部结构 1.2 string(字符串)的扩容 2.string(字符串)的指令 2.1 单个键值对增删改查操作 2.2 批量键值对 2.3 过期set命令 2.4 不存在创建存在不更新 2.5计数 三.list(列表) 1.list(列表)相关介绍 1.1 list(列表)的内部结构 1.2 list(列表)的使用场景 2.list(列表)的指令 2.1 右进左出-队列 2.2 右进

  • Redis数据结构SortedSet的底层原理解析

    Redis数据结构SortedSet的底层原理解析

    目录 概述 一些常用命令 实现 跳跃表 跳表的插入 压缩列表 概述 一些常用命令 存储:zadd key score value 获取:zrange key start end 获取:同时获取分数:zrange key start end with score 删除:zrem key value 存储的时候我们可以发现,是有一个score(分数)的,这个就是用来排序的字段. 实现 先说结论,SortedSet底层,根据配置会在不同的时候选用两种不同的数据结构zset,或ziplist进行存储:

  • redis数据结构之压缩列表

    redis数据结构之压缩列表

    目录 压缩列表是列表键和哈希键的底层实现之一.当一个列表键只包含少量列表项,并且每个列表项要么就是小整数,要么就是长度比较短的字符串,redis就会使用压缩列表来做列表键的底层实现 当一个哈希键只包含少量键值对,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做哈希键的底层实现. 压缩列表是Redis为了节约内存而开发的是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数

  • Redis之常用数据结构哈希表

    目录 1.哈希冲突 2.链式哈希 3.rehash 4.渐进式 rehash 5.rehash 触发条件 哈希表是一种保存键值对(key-value)的数据结构 哈希表优点在于,它能以 O(1) 的复杂度快速查询数据. 怎么做到的呢? 将 key 通过 Hash 函数的计算,就能定位数据在表中的位置,因为哈希表实际上是数组,所以可以通过索引值快速查询到数据. 在哈希表大小固定的情况下,随着数据不断增多,那么哈希冲突的可能性也会越高. Redis 采用了**「链式哈希」**来解决哈希冲突,在不扩容

  • C++数据结构哈希表详解

    目录 实现 散列函数 开散列方法 闭散列方法(开地址方法) 删除* 实现 哈希表,即散列表,可以快速地存储和查询记录.理想哈希表的存储和查询时间都是 O(1). 本<资料>中哈希表分以下几部分:散列函数.存储和查找时的元素定位.存储.查找.删除操作因为不常用,所以只给出思想,不给出代码. 根据实际情况,可选择不同的散列方法. 以下代码假设哈希表不会溢出. // N表示哈希表长度,是一个素数,M表示额外空间的大小,empty代表"没有元素". const int N=9997

  • C语言数据结构哈希表详解

    C语言数据结构哈希表详解

    /* * 程序名:hash.c,此程序演示哈希表的实现,数据元素单链表带头结点. * */ #include <stdio.h> #include <stdlib.h> #include <string.h> // 哈希表中数据元素的结构体. typedef struct Element { unsigned int key; // 关键字. int value; // 数据元素其它数据项,可以是任意数据类型. // char value[1001]; // 数据元素其

  • TypeScript 基础数据结构哈希表 HashTable教程

    目录 前言 1. 哈希表介绍和特性 2. 哈希表的一些概念 3. 地址冲突解决方案 3.1 方案一:链地址法 3.2 方案二:开放地址法 4. 哈希函数代码实现 5. 哈希表封装 5.1 整体框架 v1 版 5.2 添加 put 方法 v2 版 5.3 添加 get 方法 v3 版 5.4 添加 delete 方法 v4 版 6. 哈希表的自动扩容 前言 哈希表是一种 非常重要的数据结构,几乎所有的编程语言都有 直接或者间接 的应用这种数据结构. 很多学习编程的人一直搞不懂哈希表到底是如何实现的

  • 简单讲解哈希表

    简单讲解哈希表

    目录 一.哈希表的概念 1.查找算法 2.哈希表 3.哈希数组 4.关键字 5.哈希函数 6.哈希冲突 7.哈希地址 二.常用哈希函数 1.直接定址法 2.平方取中法 3.折叠法 4.除留余数法 5.位与法 三.常见哈希冲突解决方案 1.开放定址法 1)原理讲解 2)动画演示 2.再散列函数法 1)原理讲解 2)动画演示 3.链地址法 1)原理讲解 2)动画演示 4.公共溢出区法 1)原理讲解 2)动画演示 四.哈希表的实现 1.数据结构定义 2.哈希表初始化 3.哈希函数计算 4.哈希表查找

  • java数据结构和算法中哈希表知识点详解

    树的结构说得差不多了,现在我们来说说一种数据结构叫做哈希表(hash table),哈希表有是干什么用的呢?我们知道树的操作的时间复杂度通常为O(logN),那有没有更快的数据结构?当然有,那就是哈希表: 1.哈希表简介 哈希表(hash table)是一种数据结构,提供很快速的插入和查找操作(有的时候甚至删除操作也是),时间复杂度为O(1),对比时间复杂度就可以知道哈希表比树的效率快得多,并且哈希表的实现也相对容易,然而没有任何一种数据结构是完美的,哈希表也是:哈希表最大的缺陷就是基于数组,因

  • 详解Redis数据结构之跳跃表

    1.简介 我们先不谈Redis,来看一下跳表. 1.1.业务场景 场景来自小灰的算法之旅,我们需要做一个拍卖行系统,用来查阅和出售游戏中的道具,类似于魔兽世界中的拍卖行那样,还有以下需求: 拍卖行拍卖的商品需要支持四种排序方式,分别是:按价格.按等级.按剩余时间.按出售者ID排序,排序查询要尽可能地快.还要支持输入道具名称的精确查询和不输入名称的全量查询. 这样的业务场景所需要的数据结构该如何设计呢?拍卖行商品列表是线性的,最容易表达线性结构的是数组和链表.假如用有序数组,虽然查找的时候可以使用

  • Java深入了解数据结构之哈希表篇

    Java深入了解数据结构之哈希表篇

    目录 1,概念 2,冲突-避免 3,冲突-避免-哈希函数设计 4,冲突-避免-负载因子调节 5,冲突-解决-闭散列 ①线性探测 ②二次探测 6,冲突-解决-开散列/哈希桶 7,完整代码 1,概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键 码的多次比较.顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( ),搜索的效率取决于搜索过程中 元素的比较次数. 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素. 如果构造一

  • Java数据结构之实现哈希表的分离链接法

    Java数据结构之实现哈希表的分离链接法

    哈希表的分离链接法 原理 Hash Table可以看作是一种特殊的数组.他的原理基本上跟数组相同,给他一个数据,经过自己设置的哈希函数变换得到一个位置,并在这个位置当中放置该数据.哦对了,他还有个名字叫散列 0 1 数据1 数据2 就像这个数组,0号位置放着数据1,1号位置放数据2 而我们的哈希表则是通过一个函数f(x) 把数据1变成0,把数据2变成1,然后在得到位置插入数据1和数据2. 非常重要的是哈希表的长度为素数最好!! 而且当插入数据大于一半的时候我们要进行扩充!!! 冲突问题产生 现在

  • C++中使用哈希表(unordered_map)的一些常用操作方法

    目录 1.建立基本数据类型的哈希表 2.向哈希表中添加元素 1).insert函数 2).用数组方法直接添加 3.成员函数 begin(),end()函数 find()查找函数 count()查找函数 size()函数 empty()函数 clear()函数 swap()函数 哈希表的遍历 第一种遍历 第二种遍历 补充:实际应用 总结 1.建立基本数据类型的哈希表 unordered_map<int,int> m; //<string,string>,<char,char&g

随机推荐