本文脑图

redis基本数据结构

本文脑图

前言

Redis它是一个基于C语言的开源非关系内存数据库，可用作数据库、缓存和信息中间件。客户必须一点一点地理解这样优秀的东西。

这是关于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第二版的设计与实现

也许看完这张照片后，我仍然感到困惑。不要惊慌，将详细介绍五个数据结构，这张图片只是让你找到每个数据结构对应的存储类型，可能有一个印象。

举个简单的例子，你在Redis设置字符串key 234，然后检查字符串的存储类型int非整数型使用非整数型embstr存储类型，具体操作如下图所示：

String类型

String是Redis最基本的数据类型也在上面的介绍中提到Redis是用c语言开发的。但是RedisC语言中的字符串和字符串有明显的区别。

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编码格式 *@paramfile *@return */ publicstaticStringencodeImg(MultipartFilefile){ byte[]imgBytes=null; try{ imgBytes=file.getBytes(); }catch(IOExceptione){ e.printStackTrace(); } BASE64Encoderencoder=newBASE64Encoder(); &nbp;    return imgBytes==null?null:encoder.encode(imgBytes );
    }

（2）第二步就是把处理后的图片字符串格式存储进Redis中，实现得代码如下所示：

    /**
     * Redis存储图片
     * @param file
     * @return
     */
    public void uploadImageServiceImpl(MultipartFile image) {
        String imgId = UUID.randomUUID().toString();
        String imgStr= ImageUtils.encodeImg(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保存的是每一个节点的内容。

说到这里相信大家已经都hash这种数据结构已经非常了解，若是第一次接触Redis五种基本数据结构的底层实现的话，建议多看几遍，下面来说一说hash的应用场景。

应用场景

哈希表相对于String类型存储信息更加直观，擦欧总更加方便，经常会用来做用户数据的管理，存储用户的信息。

hash也可以用作高并发场景下使用Redis生成唯一的id。下面我们就以这两种场景用作案例编码实现。

存储用户数据

第一个场景比如我们要储存用户信息，一般使用用户的ID作为key值，保持唯一性，用户的其他信息（地址、年龄、生日、电话号码等）作为value值存储。

若是传统的实现就是将用户的信息封装成为一个对象，通过序列化存储数据，当需要获取用户信息的时候，就会通过反序列化得到用户信息。

但是这样必然会造成序列化和反序列化的性能的开销，并且若是只修改其中的一个属性值，就需要把整个对象序列化出来，操作的动作太大，造成不必要的性能开销。

若是使用Redis的hash来存储用户数据，就会将原来的value值又看成了一个k v形式的存储容器，这样就不会带来序列化的性能开销的问题。

分布式生成唯一ID

第二个场景就是生成分布式的唯一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的配置，为了方便我就直接放在application.yml配置文件中，实际中可以把redis的配置文件放在一个redis.properties文件单独放置，具体配置如下：

spring
 redis:
  host: 127.0.0.1
  port: 6379
  password: user
  timeout: 0
  database: 2
  pool:
   max-active: 100
   max-idle: 10
   min-idle: 0
   max-wait: 100000

（2）第二步创建redis的配置类，叫做RedisConfig，并标注上@Configuration注解，表明他是一个配置类。

@Configuration
public class RedisConfiguration {

@Value("${spring.redis.host}")
private String host;
@Value("${spring.redis.port}")
private int port;
@Value("${spring.redis.password}")
private String password;
@Value("${spring.redis.pool.max-active}")
private int maxActive;
@Value("${spring.redis.pool.max-idle}")
private int maxIdle;
@Value("${spring.redis.pool.min-idle}")
private int minIdle;
@Value("${spring.redis.pool.max-wait}")
private int maxWait;
@Value("${spring.redis.database}")
private int database;
@Value("${spring.redis.timeout}")
private int timeout;

@Bean
public JedisPoolConfig getRedisConfiguration(){
 JedisPoolConfig jedisPoolConfig= new JedisPoolConfig();
 jedisPoolConfig.setMaxTotal(maxActive);
 jedisPoolConfig.setMaxIdle(maxIdle);
 jedisPoolConfig.setMinIdle(minIdle);
 jedisPoolConfig.setMaxWaitMillis(maxWait);
 return jedisPoolConfig;
}

@Bean
public JedisConnectionFactory getConnectionFactory() {
 JedisConnectionFactory factory = new JedisConnectionFactory();
 factory.setHostName(host);
 factory.setPort(port);
 factory.setPassword(password);
 factory.setDatabase(database);
 JedisPoolConfig jedisPoolConfig= getRedisConfiguration();
 factory.setPoolConfig(jedisPoolConfig);
 return factory;
}

@Bean
public RedisTemplate getRedisTemplate() {
 JedisConnectionFactory factory = getConnectionFactory();
 RedisTemplate redisTemplate = new StringRedisTemplate(factory);
 return redisTemplate;
}
}

（3）第三步就是创建Redis的工具类RedisUtil，自从学了面向对象后，就喜欢把一些通用的东西拆成工具类，好像一个一个零件，需要的时候，就把它组装起来。

@Component
public class RedisUtil {

@Autowired
private RedisTemplate redisTemplate;
/**
* 存消息到消息队列中
* @param key 键
* @param value 值
* @return
*/
public boolean lPushMessage(String key, Object value) {
 try {
   redisTemplate.opsForList().leftPush(key, value);
   return true;
 } catch (Exception e) {
   e.printStackTrace();
   return false;
 }
}

/**
* 从消息队列中弹出消息 - 
* @param key 键
* @return
*/
public Object rPopMessage(String key) {
 try {
   return redisTemplate.opsForList().rightPop(key);
 } catch (Exception e) {
   e.printStackTrace();
   return null;
 }
}

/**
* 查看消息
* @param key 键
* @param start 开始
* @param end 结束 0 到 -1代表所有值
* @return
*/
public List