电子商务网站的优势,江西建设网站,厦门人才网唯一官方网站登录入口,网站关键词快速排名优化Redis的Hash数据结构用于存储键值对#xff08;key-value形式#xff09;的集合#xff08;类似java中HashMap或对象#xff09;。为了在保证高效性能的同时节省内存#xff0c;Redis对Hash的底层实现进行了多种优化。特别是通过使用压缩列表#xff08;ziplist#xff…Redis的Hash数据结构用于存储键值对key-value形式的集合类似java中HashMap或对象。为了在保证高效性能的同时节省内存Redis对Hash的底层实现进行了多种优化。特别是通过使用压缩列表ziplist和哈希表hashtable两种不同的数据结构来适应不同场景下的需求。 下面先来认为一下哈希表之后在详细解释下Hash内存模型的特点吧。
一、哈希表
1、数组(Array)
数组是一种线性数据结构它以连续的内存块来存储相同类型的元素。每个元素可以通过其索引通常是基于0或1开始的整数直接访问。数组的大小是在创建时确定的并且通常不能轻易改变。
原理
内存分配当创建一个数组时操作系统会分配一块连续的内存区域这块区域的大小等于数组长度乘以每个元素所占的字节数。随机访问由于数组元素是连续存储的因此可以通过起始地址加上偏移量即索引乘以每个元素的大小来快速计算任何元素的地址从而实现O(1)时间复杂度的随机访问。插入与删除在数组中间插入或删除元素需要移动其他元素以保持数组的连续性这会导致O(n)的时间复杂度其中n是数组的长度。
主要特点 长度固定内存空间连续查询快插入和删除相对比较慢。
2、链表(Linked List)
链表是由一系列节点组成的集合每个节点包含数据部分和下一个节点的引用指针。链表不要求节点在内存中是连续存储的。
原理
内存分配链表中的节点可以在内存的任何位置分配因为每个节点都有一个指针指向下一个节点。这意味着链表可以动态增长或收缩。访问元素链表不支持随机访问要访问某个特定的元素必须从头节点开始遍历链表直到找到目标节点。因此查找操作的时间复杂度为O(n)。插入与删除如果已经定位到了要插入或删除的位置那么这些操作只需修改相邻节点的指针时间复杂度为O(1)。但是定位到该位置本身可能需要O(n)的时间。
特点 长度不固定内存不连续节点包含数据和方向指针查询比较慢插入和删除比较快。
分类 链表分为单向链表每个节点只有一个指向下一个节点的指针、双向链表每个节点有两个指针分别指向前后两个节点和循环链表最后一个节点指向第一个节点形成环形。
3、哈希表(Hash Table)
1、概述
哈希表是计算机科学中一种非常重要的数据结构它在解决大规模数据存储和查找问题上发挥着关键作用。 哈希表是一种用于存储键值对的数据结构它使用哈希函数将key映射到表中的一个位置来快速访问到记录value。哈希表旨在提供平均情况下的常数时间复杂度O(1)的查找、插入和删除操作。 哈希表是通过数组链表的方式实现的主结构是数组数组的每一个节点都是一张单独的链表。
2、主要特点
1、数组链表的结构主结构是数组数组的每一个节点都是一个链表。 2、操作key-value类型数据key用于确认表的位置value存储在这个位置中。 3、自动扩容查询、插入和删除都比较快。
3、工作原理
1、插入元素原理 第一步计算key的哈希码调用hashCode()方法计算返回int型整数的哈希码是自身。 第二步根据哈希码算出该key在哈希表中的位置index 如算法indexx%11 (假设当前数组长度是11实际数组的长度会自动扩容的) 第三步将数据value存入哈希表的index位置。 情况1一次添加成功该位置没有任何数据 情况2多次添加成功出现了冲突即数组中该位置已有元素则调用equals()和对应链表的元素进行逐个比较结果都是false创建新节点在该位置的链表末尾添加新元素 情况3不添加出现了冲突调用equals()和该位置的链表的元素逐个进行比较结果是true表明本次是重复插入不添加元素
结论哈希表的数据是无序的唯一的。最快插入数据需要三步。 说明下哈希表刚创建时期数组长度相对比较短。第二步hash算法需要把第一步的hashCode都映射到这些较短的位置上所以就会有很多重复。实际上第一步计算hashCode出来的重复概率非常非常低的经过第二步hash算法后重复概率才变高的。 2、查询元素原理 基本和插入元素逻辑相同。 第一步计算key的哈希码。 第二步根据哈希码算出该key在哈希表中的位置index。 第三步查询该位置index的元素。 情况1直接查询失败该位置没有任何数据 情况2多次查询失败该位置链表存在1个或多个元素逐个调用equals()方法比较结果都是false则说明不存在目标key存储 情况3查询成功该位置链表存在1个或多个元素逐个调用equals()方法比较存在返回true则说明存在目标key存储返回该位置的value值
删除元素逻辑和查询元素原理一致则不在赘述了。
4、动态扩容
1、哈希表的核心原理 哈希函数使用哈希函数将每个键转换为一个整数索引也称为哈希值。这个哈希值决定了键在哈希表中的存储位置。哈希函数的设计目标是尽量减少冲突即不同的键映射到同一个索引以提高查找效率。 冲突解决即使哈希函数设计得再好也难免会出现多个键映射到同一个索引的情况这被称为“哈希冲突”。为了处理冲突哈希表采用链地址法Separate Chaining即每个哈希表的槽位bucket实际上是一个链表。当发生冲突时新的键会被添加到链表的末尾。虽然链表查找的时间复杂度是 O(n)但在实际应用中哈希冲突的概率非常低因此平均查找时间仍然是 O(1)。
2、为什么要扩容
假设哈希表需要存储100万个键哈希表的大小为 163842^14。每个键通过哈希函数计算出一个0到16383之间的索引位置然后存储在对应的槽位中。由于哈希表的大小远小于键的数量哈希冲突是不可避免的且每个槽位的链表也会非常的长进而导致查询性能会下降前面我们介绍过哈希函数找到槽位后进一步在链表中找到key需要遍历链表元素进行equal比较如果链表越长比较次数就越多自然查询也就越慢。 为了避免这种情况哈希表会随着负载因子即键的数量与哈希表大小的比值超过一定阈值时触发 rehash 操作即将哈希表的大小扩大并重新分配所有键。
3、哈希表rehash机制
在大多数情况下当哈希表的装载因子超过某个阈值时哈希表会进行扩容并将所有元素从旧的哈希表迁移到新的、更大的哈希表中。这个过程是一次性的意味着它会在一个操作中完成所有的迁移工作。这种方法的优点是简单直接但缺点是在迁移期间可能会显著影响性能因为所有读写操作都需要等待迁移完成。
Redis为了减少rehash操作对性能的影响而采用的一种特定策略即渐进式rehash也称增量rehash。
4、Redis渐进式rehash机制
渐进式rehash是Redis为了优化性能而设计的一种特殊策略它有效地解决了大规模哈希表rehash时可能导致的性能问题。
1、渐进式rehash的工作原理 双哈希表在 rehash 过程中Redis同时维护两个哈希表旧哈希表ht[0]和新哈希表ht[1]。所有新的键都会直接插入到新哈希表中而旧哈希表中的键会逐步迁移到新哈希表。key会直接插入新哈希表且对旧哈希表的当前key槽数据迁移到新哈希表保证新旧哈希表中只会有一个key存在 逐步迁移Redis不会在一次操作中将所有键从旧哈希表迁移到新哈希表而是每次处理客户端请求时迁移一部分键。具体来说Redis会在每次执行命令时从旧哈希表中随机选择一些槽位并将这些槽位中的键迁移到新哈希表。这样可以确保 rehash操作不会影响 Redis的正常性能。 rehash完成当所有键都迁移到新哈希表后Redis会丢弃旧哈希表只保留新哈希表。此时rehash操作完成哈希表的大小已经扩大查找性能得到恢复。
2、渐进式rehash如何优化性能 避免一次性性能波动如果一次性完成rehash操作Redis 需要遍历所有键并重新计算哈希值这会导致性能显著下降尤其是在键数量非常多的情况下。渐进式 rehash将rehash操作分散到多个请求中确保了在高并发场景下Redis 的性能不会受到明显影响。 不影响正常操作在rehash过程中Redis仍然可以正常处理客户端请求。对于新插入的键Redis会直接将其插入到新哈希表中对于旧哈希表中的键Redis会先在旧哈希表中查找如果找不到再在新哈希表中查找。这种机制确保了 rehash 不会影响正常的读写操作。
3、Redis哈希表的具体实现
字典DictionaryRedis的哈希表是通过字典dict来实现的。字典内部包含两个哈希表ht[0] 和 ht[1]用于支持渐进式rehash。哈希函数Redis使用MurmurHash2或者更现代的MurmurHash3作为默认的哈希函数这些哈希函数具有良好的分布特性和较高的计算效率。冲突解决Redis 采用链地址法来处理冲突即每个桶包含一个链表链表中的每个节点存储一个键值对。
4、查找键的过程 当Redis进行rehash时需要查找一个键时它会按照以下步骤进行 1、计算哈希值首先Redis会使用哈希函数计算目标键的哈希值并确定该键应该存储在哪个槽位中。 2、检查新哈希表如果当前正在进行rehashRedis会先在新哈希表ht[1]中查找该键。如果找到了直接进行操作。 3、再检查旧哈希表如果在新哈希表中没有找到该键Redis会继续在旧哈希表ht[0]中查找。如果找到了返回结果如果没有找到则说明该键不存在。 4、处理冲突如果在某个槽位中发生了哈希冲突Redis会遍历该槽位对应的链表逐个比较键的值直到找到匹配的键或遍历完链表。
5、查找时间复杂度 理想情况下在没有哈希冲突的情况下查找时间复杂度为 O(1)因为 Redis 可以直接通过哈希值定位到键所在的槽位。 存在哈希冲突时如果发生了哈希冲突Redis 需要在链表中逐个比较键的值查找时间复杂度为 O(n)其中 n 是该槽位中键的数量即链表的长度。然而在实际应用中哈希冲突的概率非常低因此平均查找时间仍然是 O(1)。
6、哈希表的扩展策略
Redis 的哈希表会根据键的数量自动调整大小以确保负载因子保持在一个合理的范围内。具体的扩展策略如下 触发条件 当哈希表的负载因子即键的数量与哈希表大小的比值超过 max-load-factor默认是 1.0时触发 rehash 操作。当哈希表的负载因子低于 min-load-factor默认是 0.1时触发收缩操作即将哈希表缩小。 扩展倍数Redis 通常会将哈希表的大小扩展为原来的两倍即 2^n 的形式以确保哈希表的大小始终是2的幂次方。这样可以简化哈希函数的实现并且有助于减少哈希冲突。
7、内存碎片整理
虽然Redis的哈希表扩展机制能够有效减少哈希冲突但在长时间运行的情况下内存碎片由于扩容或收缩造成内存使用不充分出现未使用且已开辟的小内存片段可能会逐渐积累。为此Redis使用了高效的内存分配器如 jemalloc并且提供了内存碎片整理机制。通过定期回收未使用的内存页Redis可以确保在大规模数据集的情况下内存使用率仍然保持高效。
8、动态扩容总结
Redis 能够在几百万个键的情况下快速找到目标键主要得益于以下几点
哈希表Redis 使用哈希表作为其主要的数据结构通过哈希函数将键映射到固定的数组位置实现了O(1) 的平均查找时间。渐进式rehash当哈希表的负载因子过高时Redis会触发rehash操作但为了避免一次性rehash对性能的影响Redis采用了渐进式rehash机制将rehash操作分散到多个请求中逐步完成。双哈希表机制在 rehash 过程中Redis 同时维护两个哈希表确保在 rehash 期间仍然可以正常处理客户端请求。哈希冲突处理即使发生了哈希冲突Redis 也通过链地址法有效地解决了冲突确保了查找性能。
二、Redis的Hash结构
Redis的Hash数据结构用于存储键值对key-value形式的集合类似java中HashMap。通过使用压缩列表ziplist和哈希表hashtable两种不同的数据结构来适应不同场景下的需求。
1、压缩列表ziplist
当Hash中的元素数量较少且每个字段和值都较短时Redis使用压缩列表ziplist来存储 Hash。压缩列表是一种紧凑的内存表示形式能够将多个键值对打包到一个连续的内存块中减少了指针开销和内存碎片。
1、压缩列表的特点 紧凑存储压缩列表将多个键值对即key和value打包到一个连续的内存块中避免了指针开销。每个键值对的存储空间根据其实际大小动态调整支持变长编码。 有序性压缩列表中的键值对是按插入顺序排列的虽然Hash本身是无序的但压缩列表的内部结构是有序的这有助于提高查找效率。 内存高效由于压缩列表是紧凑的数组结构它减少了内存碎片并且不需要额外的指针开销。这使得压缩列表在处理小规模数据时具有很高的内存利用率。 前缀压缩对于相邻的字符串字段或值压缩列表会使用前缀压缩技术来减少重复字符串的存储空间。如果两个相邻的字符串有相同的前缀压缩列表只会存储一次前缀并在后续的字符串中引用该前缀。 局部重排当插入或删除键值对时压缩列表会尽量保持数据的紧凑性避免频繁的内存分配和释放。它通过局部重排即将新键值对插入到合适的位置并调整相邻键值对的存储位置来减少内存碎片。
2、压缩列表的工作原理 变长编码压缩列表使用变长编码来存储字段和值。例如小整数可以使用较少的字节来表示而大整数则使用更多的字节。这种变长编码方式减少了不必要的内存浪费。 前缀压缩对于相邻的字符串字段或值压缩列表会使用前缀压缩技术来减少重复字符串的存储空间。这在处理大量相似的字符串时特别有效能够显著节省内存。 局部重排当插入或删除键值对时压缩列表会尽量保持数据的紧凑性避免频繁的内存分配和释放。它通过局部重排即将新键值对插入到合适的位置并调整相邻键值对的存储位置来减少内存碎片。
3、压缩列表的内存优化 减少内存碎片压缩列表通过紧凑的数组结构减少了内存碎片特别适合处理小规模数据。它避免了传统链表中常见的内存碎片问题提高了内存利用率。 缓存友好由于压缩列表中的键值对是连续存储的访问这些键值对时可以充分利用 CPU 缓存减少缓存未命中的次数。这有助于提升性能。
2、哈希表hashtable
当Hash中的元素数量较多或者字段和值的长度较长时Redis会切换使用哈希表hashtable来存储Hash。哈希表是一种基于哈希函数的数据结构能够提供O(1)的平均查找、插入和删除操作。
1、哈希表的特点 快速查找哈希表通过哈希函数将字段映射到固定的桶中查找、插入和删除操作的平均时间复杂度为O(1)。这使得哈希表在处理大规模数据时具有很高的性能。 无重复字段哈希表保证Hash中没有重复的字段符合Hash的语义要求。 动态调整大小当哈希表的装载因子已用槽位数与总槽数的比例过高时哈希表会进行扩容以减少冲突并保持性能。Redis使用渐进式rehash来分摊rehash的工作量避免一次性迁移所有元素导致的性能下降。 冲突解决哈希表使用链地址法Separate Chaining来处理冲突。每个桶包含一个链表当多个字段被哈希到同一个桶时它们会被添加到该链表中。虽然链地址法可能会导致链表过长但Redis 通过渐进式rehash来减少冲突的发生。
2、哈希表的工作原理 哈希函数哈希表使用哈希函数将字段映射到固定的桶中。Redis使用MurmurHash2或 MurmurHash3作为默认的哈希函数这些哈希函数具有良好的分布特性和较高的计算效率。 渐进式rehash当哈希表的装载因子过高时Redis会创建一个新的、更大的哈希表并将元素逐步迁移到新的表中。这个过程是逐渐进行的每次执行命令时Redis会迁移一部分元素直到所有元素都迁移完毕。渐进式rehash确保了在高并发环境下Hash的操作性能仍然保持稳定。 冲突处理当多个字段被哈希到同一个桶时哈希表使用链地址法来处理冲突。每个桶包含一个链表链表中的每个节点存储一个字段值对。虽然链地址法可能会导致链表过长但 Redis通过渐进式rehash来减少冲突的发生。
3、哈希表的内存优化 减少冲突通过渐进式rehashRedis能够动态调整哈希表的大小减少冲突的发生从而提高查找效率并节省内存。 内存高效哈希表的每个节点只包含字段和值的指针避免了额外的内存开销。相比于压缩列表哈希表在处理大规模数据时更加高效特别是在字段和值的长度较长时。
3、混合结构自动转换
Redis的Hash实现了一个智能的混合结构能够在压缩列表ziplist和哈希表hashtable 之间自动转换以适应不同的应用场景。
1、自动切换原理 初始状态当Hash中的元素数量较少且每个字段和值都较短时Redis使用压缩列表ziplist来存储Hash。此时Hash具有最高的内存利用率和操作效率。 自动升级当Hash中的元素数量超过某个阈值或者字段和值的长度超过一定限制时Redis会立即将压缩列表转换为哈希表。这个转换过程是一次性的不会影响后续的操作。 不会反向转换Redis不会将哈希表转换回压缩列表因为一旦Hash的规模较大哈希表已经能够高效地处理这些元素。转换过程是一次性的也会造成性能的开销如果在临界值的地方修改hash数据就会造成数据结构频繁切换进而导致性能消耗很大所以也不会逆向切换了。
2、自动转换的条件 元素数量当Hash中的元素数量超过某个阈值时Redis会自动将压缩列表转换为哈希表。这个阈值可以通过配置参数hash-max-ziplist-entries来调整默认值为 512。 字段和值的长度即使Hash中的元素数量较少但如果某个字段或值的长度超过一定限制Redis也会将压缩列表转换为哈希表。这个长度限制可以通过配置参数 hash-max-ziplist-value来调整默认值为64字节。
4、内存优化的其他技术
除了压缩列表和哈希表的结合使用Redis还采用了其他一些内存优化技术来进一步提升 Hash的性能和内存利用率 渐进式rehash当哈希表需要扩容时Redis使用渐进式rehash来分摊rehash的工作量避免一次性迁移所有元素导致的性能下降。这确保了在高并发环境下Hash的操作性能仍然保持稳定。 惰性释放当Hash中的键值对被删除时Redis不会立即回收多余的内存而是保留下来用于后续可能的增长。这减少了频繁的内存分配和释放操作提升了性能。 前缀压缩对于相邻的字符串字段或值Redis使用前缀压缩技术来减少重复字符串的存储空间。这在处理大量相似的字符串时特别有效能够显著节省内存。 变长编码Redis使用变长编码来存储整数和浮点数减少了不必要的内存浪费。例如小整数可以使用较少的字节来表示而大整数则使用更多的字节。
5、Redis的hash结构总结
Redis的Hash通过结合压缩列表ziplist和哈希表hashtable两种不同的数据结构实现了高效的内存优化。当 Hash 中的元素数量较少且每个字段和值都较短时Redis使用压缩列表来存储Hash。当 Hash中的元素数量较多或者字段和值的长度较长时Redis使用哈希表来存储Hash。 Redis会在压缩列表和哈希表之间自动转换以适应不同的应用场景。当Hash中的元素数量超过某个阈值或者字段和值的长度超过一定限制时压缩列表会自动转换为哈希表。 当哈希表需要扩容时Redis使用渐进式rehash来分摊rehash的工作量避免一次性迁移所有元素导致的性能下降。
三、传统哈希表和redis哈希结构对比
1、概述
Redis 确实实现了哈希表的原理但它对传统哈希表进行了扩展和优化以适应其特定的需求和使用场景。因此可以说 Redis 的哈希表是一种基于传统哈希表原理的增强型数据结构但主要原理还是哈希表的概念。
2、对比分析
1、基本原理
传统哈希表使用哈希函数将键映射到一个固定的数组桶中当发生冲突时通常采用链地址法来处理。Redis哈希表同样使用哈希函数将键映射到桶中但引入了渐进式rehash、压缩列表等优化机制以提高性能和内存利用率。
2、扩容机制
传统哈希表在扩容时通常会一次性完成所有元素的重新哈希和迁移这可能会导致短暂的性能下降。Redis哈希表通过渐进式rehashRedis将rehash过程分摊到多个命令执行的过程中减少了对性能的影响确保了高并发环境下的稳定性和响应速度。
3、内存优化
传统哈希表通常不会对小规模数据进行特殊优化内存使用较为固定。Redis哈希表对于小规模数据Redis使用压缩列表ziplist或整数集合intset来存储数据从而节省内存。这些特殊的数据结构在数据量较小时非常高效但在数据量增大时会自动转换为标准的哈希表结构。
4、并发处理
传统哈希表在多线程环境中通常需要加锁来保证线程安全这可能会影响性能。Redis哈希表Redis是单线程的但在rehash期间它允许同时访问两个哈希表ht[0] 和 ht[1]并通过逐步迁移的方式确保数据的一致性和高性能。
5、应用场景
传统哈希表适用于一般的键值对存储和查找场景提供 O(1) 的平均时间复杂度。Redis哈希表除了基本的键值对存储和查找功能外还支持丰富的命令集如批量操作、事务、持久化等特别适合于缓存、会话管理、计数器等高性能应用场景。
3、总结
Redis 的哈希表并不是完全脱离了传统哈希表的概念而是基于传统哈希表的原理进行了多项优化和改进。这些优化使得 Redis的哈希表在高并发、低延迟的应用场景中表现出色同时保持了高效的内存利用率和良好的性能。可以说 Redis的哈希表是一种“增强型”的哈希表它结合了传统哈希表的优点并针对 Redis 的需求进行了专门的设计和优化。
附录
Redis短结构
“短结构”Small Encoding是指Redis为某些数据类型提供的一种优化的内存的方式旨在减少小数据的内存占用。Redis通过使用紧凑的数据结构来存储小规模数据避免了不必要的指针开销和内存碎片从而提高了内存利用率和性能。
*Redis的短结构主要应用于以下几种数据类型 1、Hash 2、List 3、Set 4、Sorted Set
Hash和List在元素数量较少且每个元素较短时使用压缩列表ziplist。Set在元素数量较少且所有元素都是整数时使用整数集合intset。Sorted Set在元素数量较少且每个元素的分数和成员较短时使用压缩列表ziplist。*
这些数据类型在元素数量较少且每个元素较小时Redis会使用一种紧凑的编码方式通常是压缩列表ziplist或整数集合intset来存储数据而不是立即使用更复杂的数据结构如哈希表、双向链表等。这种紧凑的编码方式被称为短结构small encoding。 本篇我们介绍了Hash的短结构模式zipList后面篇章会陆续介绍其他数据类型的短结构实现。
学海无涯苦作舟
