redis的五种结构哈希表类型
前⾔
Redis是基于c语⾔编写的开源⾮关系型内存数据库，可以⽤作数据库、缓存、消息中间件，这么优秀的东西⼀定要⼀点⼀点的吃透它。
关于Redis的⽂章之前也写过三篇，阅读量和读者的反映都还可以，其中第⼀篇是Redis的缓存三⼤问题[]。
第⼆篇是Redis的内存管理和淘汰策略[]和持久化[]。
这是关于Redis的第三篇⽂章，主要讲解Redis的五种数据结构详解，包括这五种的数据结构的底层原理实现。
理论肯定是要⽤于实践的，因此最重要的还是实战部分，也就是这⾥还会讲解五种数据结构的应⽤场景。
话不多说，我们直接进⼊主题，很多⼈都知道Redis的五种数据结构包括以下五种：
1. String：字符串类型
2. List：列表类型
3. Set：⽆序集合类型
4. ZSet：有序集合类型
5. Hash：哈希表类型
但是作为⼀名优秀的程序员可能不能只停留在只会⽤这五种类型进⾏crud⼯作，还是得深⼊了解这五种数据结构的底层原理。
Redis核⼼对象
在Redis中有⼀个「核⼼的对象」叫做redisObject，是⽤来表⽰所有的key和value的，⽤redisObject结构体来表⽰String、Hash、List、Set、ZSet五种数据类型。
redisObject的源代码在redis.h中，使⽤c语⾔写的，感兴趣的可以⾃⾏查看，关于redisObject我这⾥画了⼀张图，表⽰redisObject的结构如下所⽰：
在redisObject中「type表⽰属于哪种数据类型，encoding表⽰该数据的存储⽅式」，也就是底层的实现的该数据类型的数据结构。因此这篇⽂章具体介绍的也是encoding对应的部分。
那么encoding中的存储类型⼜分别表⽰什么意思呢？具体数据类型所表⽰的含义，如下图所⽰：
可能看完这图，还是觉得⼀脸懵。不慌，会进⾏五种数据结构的详细介绍，这张图只是让你到每种中数据结构对应的储存类型有哪些，⼤概脑⼦⾥有个印象。
举⼀个简单的例⼦，你在Redis中设置⼀个字符串key 234，然后查看这个字符串的存储类型就会看到为int类型，⾮整数型的使⽤的是embstr 储存类型，具体操作如下图所⽰：
String类型
String是Redis最基本的数据类型，上⾯的简介中也说到Redis是⽤c语⾔开发的。但是Redis中的字符串和c语⾔中的字符串类型却是有明显的区别。
String类型的数据结构存储⽅式有三种int、raw、embstr。那么这三种存储⽅式有什么区别呢？
int
Redis中规定假如存储的是「整数型值」，⽐如set num 123这样的类型，就会使⽤ int的存储⽅式进⾏存储，在redisObject的「ptr属性」中就会保存该值。
SDS
假如存储的「字符串是⼀个字符串值并且长度⼤于32个字节」就会使⽤SDS（simple dynamic string）⽅式进⾏存储，并且encoding设置为raw；若是「字符串长度⼩于等于32个字节」就会将encoding改为embstr来保存字符串。
SDS称为「简单动态字符串」，对于SDS中的定义在Redis的源码中有的三个属性int len、int free、char buf[]。
len保存了字符串的长度，free表⽰buf数组中未使⽤的字节数量，buf数组则是保存字符串的每⼀个字符元素。
因此当你在Redsi中存储⼀个字符串Hello时，根据Redis的源代码的描述可以画出SDS的形式的redisObject结构图如下图所⽰：
SDS与c语⾔字符串对⽐
Redis使⽤SDS作为存储字符串的类型肯定是有⾃⼰的优势，SDS与c语⾔的字符串相⽐，SDS对c语⾔的字符串做了⾃⼰的设计和优化，具体优势有以下⼏点：
（1）c语⾔中的字符串并不会记录⾃⼰的长度，因此「每次获取字符串的长度都会遍历得到，时间的复杂度是O(n)」，⽽Redis中获取字符串只要读取len的值就可，时间复杂度变为O(1)。
（2）「c语⾔」中两个字符串拼接，若是没有分配⾜够长度的内存空间就「会出现缓冲区溢出的情况」；⽽「SDS」会先根据len属性判断空间是否满⾜要求，若是空间不够，就会进⾏相应的空间扩展，所以「不会出现缓冲区溢出的情况」。
（3）SDS还提供「空间预分配」和「惰性空间释放」两种策略。在为字符串分配空间时，分配的空间⽐实际要多，这样就能「减少连续的执⾏字符串增长带来内存重新分配的次数」。
当字符串被缩短的时候，SDS也不会⽴即回收不适⽤的空间，⽽是通过free属性将不使⽤的空间记录下来，等后⾯使⽤的时候再释放。
具体的空间预分配原则是：「当修改字符串后的长度len⼩于1MB，就会预分配和len⼀样长度的空间，即len=free；若是len⼤于1MB，free 分配的空间⼤⼩就为1MB」。
（4）SDS是⼆进制安全的，除了可以储存字符串以外还可以储存⼆进制⽂件（如图⽚、⾳频，视频等⽂件的⼆进制数据）；⽽c语⾔中的字符串是以空字符串作为结束符，⼀些图⽚中含有结束符，因此不是⼆进制安全的。
为了⽅便易懂，做了⼀个c语⾔的字符串和SDS进⾏对⽐的表格，如下所⽰：
c语⾔字符串SDS
获取长度的时间复杂度为O(n)获取长度的时间复杂度为O(1)
不是⼆进制安全的是⼆进制安全的
只能保存字符串还可以保存⼆进制数据
n次增长字符串必然会带来n次的内存分配n次增长字符串内存分配的次数<=n
String类型应⽤
说到这⾥我相信很多⼈可以说已经精通Redis的String类型了，但是纯理论的精通，理论还是得应⽤实践，上⾯说到String可以⽤来存储图⽚，现在就以图⽚存储作为案例实现。
（1）⾸先要把上传得图⽚进⾏编码，这⾥写了⼀个⼯具类把图⽚处理成了Base64得编码形式，具体得实现代码如下：
/**
* 将图⽚内容处理成Base64编码格式
* @param file
* @return
*/
public static String encodeImg(MultipartFile file) {
byte[] imgBytes = null;
try {
imgBytes = Bytes();
} catch (IOException e) {
e.printStackTrace();
}
BASE64Encoder encoder = new BASE64Encoder();
return imgBytes==null?de(imgBytes );
}
（2）第⼆步就是把处理后的图⽚字符串格式存储进Redis中，实现的代码如下所⽰：
/**
* Redis存储图⽚
* @param file
* @return
*/
public void uploadImageServiceImpl(MultipartFile image) {
String imgId = UUID.randomUUID().toString();
String imgStr= deImg(image);
redisUtils.set(imgId , imgStr);
/
/ 后续操作可以把imgId存进数据库对应的字段，如果需要从redis中取出，只要获取到这个字段后从redis中取出即可。
}
这样就是实现了图⽚得⼆进制存储，当然String类型得数据结构得应⽤也还有常规计数：「统计微博数、统计粉丝数」等。
Hash类型
Hash对象的实现⽅式有两种分别是ziplist、hashtable，其中hashtable的存储⽅式key是String类型的，value也是以key value的形式进⾏存储。字典类型的底层就是hashtable实现的，明⽩了字典的底层实现原理也就是明⽩了hashtable的实现原理，hashtable的实现原理可以与HashMap的是底层原理相类⽐。
字典
两者在新增时都会通过key计算出数组下标，不同的是计算法⽅式不同，HashMap中是以hash函数的⽅式，⽽hashtable中计算出hash值后，还要通过sizemask 属性和哈希值再次得到数组下标。
我们知道hash表最⼤的问题就是hash冲突，为了解决hash冲突，假如hashtable中不同的key通过计算得到同⼀个index，就会形成单向链表（「链地址法」），如下图所⽰：
rehash
在字典的底层实现中，value对象以每⼀个dictEntry的对象进⾏存储，当hash表中的存放的键值对不断的增加或者减少时，需要对hash表进⾏⼀个扩展或者收缩。
这⾥就会和HashMap⼀样也会就进⾏rehash操作，进⾏重新散列排布。从上图中可以看到有ht[0]和ht[1]两个对象，先来看看对象中的属性是⼲嘛⽤的。
在hash表结构定义中有四个属性分别是dictEntry **table、unsigned long size、unsigned long sizemask、unsigned long used，分别表⽰的含义就是「哈希表数组、hash表⼤⼩、⽤于计算索引值，总是等于size-1、hash表中已有的节点数」。
ht[0]是⽤来最开始存储数据的，当要进⾏扩展或者收缩时，ht[0]的⼤⼩就决定了ht[1]的⼤⼩，ht[0]中的所有的键值对就会重新散列到ht[1]中。
扩展操作：ht[1]扩展的⼤⼩是⽐当前 ht[0].used 值的⼆倍⼤的第⼀个 2 的整数幂；收缩操作：ht[0].used 的第⼀个⼤于等于的 2 的整数幂。
当ht[0]上的所有的键值对都rehash到ht[1]中，会重新计算所有的数组下标值，当数据迁移完后ht[0]就会被释放，然后将ht[1]改为ht[0]，并新创建ht[1]，为下⼀次的扩展和收缩做准备。
渐进式rehash
假如在rehash的过程中数据量⾮常⼤，Redis不是⼀次性把全部数据rehash成功，这样会导致Redis对外服务停⽌，Redis内部为了处理这种
情况采⽤「渐进式的rehash」。
Redis将所有的rehash的操作分成多步进⾏，直到都rehash完成，具体的实现与对象中的rehashindex属性相关，「若是rehashindex 表⽰为-1表⽰没有rehash操作」。
当rehash操作开始时会将该值改成0，在渐进式rehash的过程「更新、删除、查询会在ht[0]和ht[1]中都进⾏」，⽐如更新⼀个值先更新
ht[0]，然后再更新ht[1]。
⽽新增操作直接就新增到ht[1]表中，ht[0]不会新增任何的数据，这样保证「ht[0]只减不增，直到最后的某⼀个时刻变成空表」，这样rehash 操作完成。
上⾯就是字典的底层hashtable的实现原理，说完了hashtable的实现原理，我们再来看看Hash数据结构的两⼀种存储⽅式「ziplist（压缩列表）」
ziplist
压缩列表（ziplist）是⼀组连续内存块组成的顺序的数据结构，压缩列表能够节省空间，压缩列表中使⽤多个节点来存储数据。
压缩列表是列表键和哈希键底层实现的原理之⼀，「压缩列表并不是以某种压缩算法进⾏压缩存储数据，⽽是它表⽰⼀组连续的内存空间的使⽤，节省空间」，压缩列表的内存结构图如下：
压缩列表中每⼀个节点表⽰的含义如下所⽰：
1. zlbytes：4个字节的⼤⼩，记录压缩列表占⽤内存的字节数。
2. zltail：4个字节⼤⼩，记录表尾节点距离起始地址的偏移量，⽤于快速定位到尾节点的地址。
3. zllen：2个字节的⼤⼩，记录压缩列表中的节点数。
4. entry：表⽰列表中的每⼀个节点。
5. zlend：表⽰压缩列表的特殊结束符号'0xFF'。
再压缩列表中每⼀个entry节点⼜有三部分组成，包括previous_entry_ength、encoding、content。
1. previous_entry_ength表⽰前⼀个节点entry的长度，可⽤于计算前⼀个节点的其实地址，因为他们的地址是连续的。
2. encoding：这⾥保存的是content的内容类型和长度。
3. content：content保存的是每⼀个节点的内容。
4.
说到这⾥相信⼤家已经都hash这种数据结构已经⾮常了解，若是第⼀次接触Redis五种基本数据结构的底层实现的话，建议多看⼏遍，下⾯来说⼀说hash的应⽤场景。
应⽤场景
哈希表相对于String类型存储信息更加直观，存储更加⽅便，经常会⽤来做⽤户数据的管理，存储⽤户的信息。
hash也可以⽤作⾼并发场景下使⽤Redis⽣成唯⼀的id。下⾯我们就以这两种场景⽤作案例编码实现。
存储⽤户数据
第⼀个场景⽐如我们要储存⽤户信息，⼀般使⽤⽤户的ID作为key值，保持唯⼀性，⽤户的其他信息（地址、年龄、⽣⽇、电话号码等）作为value值存储。
若是传统的实现就是将⽤户的信息封装成为⼀个对象，通过序列化存储数据，当需要获取⽤户信息的时候，就会通过反序列化得到⽤户信息。
5.
6. 但是这样必然会造成序列化和反序列化的性能的开销，并且若是只修改其中的⼀个属性值，就需要把整个对象序列化出来，操作的动
作太⼤，造成不必要的性能开销。
若是使⽤Redis的hash来存储⽤户数据，就会将原来的value值⼜看成了⼀个k v形式的存储容器，这样就不会带来序列化的性能开销的问题。
分布式⽣成唯⼀ID
7. 第⼆个场景就是⽣成分布式的唯⼀ID，这个场景下就是把redis封装成了⼀个⼯具类进⾏实现，实现的代码如下：
// offset表⽰的是id的递增梯度值
public Long getId(String key,String hashKey,Long offset) throws BusinessException{
try {
if (null == offset) {
offset=1L;
}
// ⽣成唯⼀id
return redisUtil.increment(key, hashKey, offset);
} catch (Exception e) {
//若是出现异常就是⽤uuid来⽣成唯⼀的id值
int randNo=UUID.randomUUID().toString().hashCode();
if (randNo < 0) {
randNo=-randNo;
}
return Long.valueOf(String.format("%16d", randNo));
}
List类型
Redis中的列表在3.2之前的版本是使⽤ziplist和linkedlist进⾏实现的。在3.2之后的版本就是引⼊了quicklist。
ziplist压缩列表上⾯已经讲过了，我们来看看linkedlist和quicklist的结构是怎么样的。
linkedlist是⼀个双向链表，他和普通的链表⼀样都是由指向前后节点的指针。插⼊、修改、更新的时间复杂度尾O(1)，但是查询的时间复杂度确实O(n)。
linkedlist和quicklist的底层实现是采⽤链表进⾏实现，在c语⾔中并没有内置的链表这种数据结构，Redis实现了⾃⼰的链表结构。
Redis中链表的特性：
1. 每⼀个节点都有指向前⼀个节点和后⼀个节点的指针。
2. 头节点和尾节点的prev和next指针指向为null，所以链表是⽆环的。
3. 链表有⾃⼰长度的信息，获取长度的时间复杂度为O(1)。
Redis中List的实现⽐较简单，下⾯我们就来看看它的应⽤场景。
应⽤场景
Redis中的列表可以实现「阻塞队列」，结合lpush和brpop命令就可以实现。⽣产者使⽤lupsh从列表的左侧插⼊元素，消费者使⽤brpop命令从队列的右侧获取元素进⾏消费。
（1）⾸先配置redis的配置，为了⽅便我就直接放在l配置⽂件中，实际中可以把redis的配置⽂件放在⼀个redis.properties⽂件单独放置，具体配置如下：
spring
redis:
host: 127.0.0.1
port: 6379
password: user
timeout: 0
database: 2
pool:
redis支持的五种数据类型max-active: 100
max-idle: 10
min-idle: 0
max-wait: 100000
（2）第⼆步创建redis的配置类，叫做RedisConfig，并标注上@Configuration注解，表明他是⼀个配置类。
@Configuration
public class RedisConfiguration {
@Value("${dis.host}")
private String host;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。