redis的数据结构与哈希冲突

一、 Redis的快 ，到底快在哪里

是key-value型的非关系型数据库, 接收到一个键值对操作后，能够以微秒级别的速度找到数据，并完成操作。

二、为何能有这么突出的表现

1. 内存型数据库，所有操作在内存中完成，内存中的访问速度本身就快
2. 高效的数据结构，操作键值对实际是对数据结构进行增删改查操作

三、Redis键值对中值的5种数据类型

• String 字符串
• List 列表
• Hash 哈希
• Sorted Set 有序集合
• Set 集合
  

  四、6种底层数据结构

1. 简单动态字符串
2. 双向链表
3. 压缩列表
4. 哈希表
5. 跳表
6. 整数数组

我们把List、Hash、Sorted Set、Set 这种底层有多种实现结构的类型叫做集合类型，特点是一个键对应了一个集合的数据。

五、键与值用什么结构组织

为了实现从键到值的快速访问，redis用一个全局的哈希表来保存所有的键值对。

一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。所以一个哈希表是由多个哈希桶组成，每个哈希桶中保存了键值对的数据。

接下来我们看看redis是怎么把数据存储在哈希表中的：

如上图所示，假设这个全局哈希表中有6个哈希桶，每个桶中的entry元素都保存了*key 和 *value 指针，分别来指向实际的键和值。

已知,键只有string一种类型，而值就可以是【三】中提到的5种类型

即：我们通过计算键的哈希值，可以找到在哈希表中哈希桶的位置，从而访问对应的entry元素。 这个查过过程主要依赖于哈希计算，和数据量的多少没有直接关系，时间复杂度为0(1)，这里就正面回应了【一】中的表述。

六、快速的Redis的慢操作

当往redis写入大量数据后，可能发现有时候操作变慢了，这是为什么呢？

此处有个潜在的风险，那就是哈希表的冲突问题和rehash带来的操作阻塞

哈希冲突

通常来讲，哈希桶的个数通常会少于key的个数，那么必然会有相同的key落入同一个哈希桶，这种现象称为哈希冲突

如何解决哈希冲突

为了同一个哈希桶能存放下多个元素，让多个元素通过*next指针连接，这样就形成了一个链表，称为哈希冲突链

rehash操作

哈希冲突链上的元素越来越多，访问时又只能逐一查找再操作，这样会导致某个l链上的元素查找时间过长，对于追求快的redis来讲是不能接受的，所以在此基础上又做了优化

rehash就是增加现有的哈希桶数量，让逐渐增加的entry元素能分散在多个桶之间，减少单个桶中的冲突。

为了使rehash操作更高效，redis默认使用了两个全局的哈希表，哈希表1和哈希表2。刚开始插入数据时使用哈希表1，redis2并没有分配空间。当数据逐渐增加多，redis才开始执行rehash操作，分三步：

1. 给哈希表2分配更大的空间，例如当前哈希表1大小的2倍
2. 把哈希表1的数据重新映射并拷贝到哈希表2中
3. 释放哈希表1的空间

从哈希表1 切换到哈希表2 保存更多的数据，而原来的哈希表1 留作下一次rehash扩容备用；

整个过程简单，但是第二步中一次拷贝大量的数据，会操作redis线程阻塞，无法服务其余请求，那么redis也就无法快速访问了。

渐进式哈希

在第二步拷贝数据的时候，不一次性拷贝，而是redis正常处理请求时，每处理一个请求，就从哈希表1中的第一个索引位置开始，顺带将这个位置的所有元素拷贝到哈希表2中，等处理下一个请求时，再顺带拷贝哈希表1中的下一个索引位置的元素。

将一次性大量的拷贝开销，分摊到多次请求处理的过程中，避免了耗时操作，保证了数据的快速访问。

七、时间复杂度

String 通过计算哈希值，直接能定位到哈希桶的位置，找到桶即可进行增删改查，那么哈希表的0(1)的操作复杂度就是它的复杂度。

对于集合类型，明显使用哈希表实现的集合 比 链表实现的访问效率更高； 单个元素操作要比全部读写所有元素的效率高

整数数组 和 双向链表

操作特征都是顺序读写，通过数据下标或者链表的指针逐个元素访问。基本时间复杂度就是O(1) 。

压缩列表

在表头有三个字段 zlbytes、zltail、zllen ,分别表示列表长度、列表尾的偏移量、列表中entry个数，在表尾还有一个zend,表示列表结束。

在压缩列表中，查找表头、表尾元素，时间复杂度是O(1), 其余元素便只能逐个操作 此时的复杂度是O(N)

跳表

有序链表，只能足一查找元素，导致操作缓慢，于是就出现了跳表。 其实就是在链表的基础上，增加多级索引，通过索引位置间的跳转，实现数据的快速定位。

这个查找过程，在多级索引上挑来跳去，最后定位到元素，当数据量大时，调表的时间复杂度是O(logN)

时间复杂度总结

四字口诀

• 单元数操作是基础
• 范围操作非常耗时
• 统计操作通常高效
• 例外情况只有几个

1. 单元素操作，指每一种集合类型对单个数据实现的增删改查操作；

   1. Hash类型：HGET HSET HDEL
   2. Set类型：SADD SREM SRANDMEMBER
   3. 当进行多个元素操作时，例如HMSET操作M个元素时复杂度就是O(M)

2. 范围操作，指集合类型中的遍历操作，可以返回集合中的所有数据,比较耗时

   1. Hash类型: HGETALL
   2. Set类型： SMEMBERS
   3. List类型：LRANGGE
   4. Zset类型：ZRANGE

3. 统计操作：集合类型对集合中所有元素个数的记录

   1. 当集合是压缩列表、双向列表、整数数组时，有记录个数的元素，因此可以高效访问

4. 压缩列表和双向链表会标记表头表尾的偏移量，所以LPOP\LPUSH\RPOP\RPUSH这4个操作，直接通过偏移量就可以操作，所以复杂度只有O(1)

八、问一问

1. 拷贝过程中，数据的读写会阻塞吗？ 读、写分别是怎么正确的响应的呢?

读先从哈希1中查找，没有再去哈希2中查找；写是只允许写入哈希2中； 拷贝完成后，才会删除哈希1中的数据，释放空间。

2. 压缩列表和整数数组在查找复杂度上并没有优势，为什么要使用他们作为底层结构呢？

   1. 内存利用率， 数组和压缩列表都是非常紧凑的数据结构，它比链表占用的内存要更少。redis是内存型数据库，大量数据存储在内存中，要尽可能的提高内存的利用率
   2. 数组对cpu告诉缓存支持更好，redis在设计时， 集合数据元素较少的情况下，默认采用紧凑型排列的范式存储，同时利用cpu高速缓存 去提升访问速度。 当数据元素超过设定的阈值后，避免查询复杂度太高，才转为哈希和跳表等数据结构存储，保证查询效率。

3. 渐进rehash时，迁移数据的方式

   1. 根据键值对操作进行数据迁移
   2. 还有一个定时任务，没有键值对操作时，周期性的搬移数据到新的表中，缩短rehash的过程。

本作品采用《CC 协议》，转载必须注明作者和本文链接