ringbuffer原理_hashset数据结构

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

本篇介绍一种简单高效的数据缓存结构: RingBuffer, 这种结构实现起来只需要几行代码即可，但使用场景却很广泛，比如在Linux内核中网络数据包的缓存，系统日志的存储等多处使用过该结构。同时它也被广泛的应用于异步通信以及嵌入式设备中，提供高效的数据缓存读写操作。

1. 实现原理

RingBufferr实现比较简单，基本上只需要一个数组结构，外加两个用于存储位置信息的变量即可。其中的数组采用固定大小容量，便于重用内存，不会出现动态内存不断分配和销毁的情况，这对于一些GC类编程语言来说，大幅减少了内存管理的成本。

下面就是一个典型的RingBuffer图例，包含一个容量大小为6的数组，以及一个读和写指针。其中Write和Read用于管理读写的位置序列，读写开始后，不断增加该值来定位下一次的读写位置。

每次写数据：在Write对应位置写入新值，并向前移动对应的Write指针位置，如果遇到指针已经处于尾部，则移动到最开始位置，形成一个环形， 类似于双向链表。

每次读取数据：在Read位置读取当前值，并移动Read位置，同样如果遇到已经到达尾部，则返回到最开始的初始位置。

整个数据流的读写过程就是通过不断的操作Write和Read来实现数据的高效处理。

2. 读写操作实例

这里我们通过一个简单的实例来介绍如何操作RingBuffer来管理数据： 首先初始化一个空的数组，并设置Read=0和Write=0， 图例中黄色代表已写入的数据，绿色代表已读取的数据，红色代表异常情况:

（1） 写入三个元素分别是：1，2，3, 这时候读指针位置不变，写指针移动三个位置到索引为3的位置（数组索引位置从0开始）

（2）读取一个元素，读指针移动一个位置，写指针不变，获取数据值1。

（3）继续写入四个元素，分别是：4，5，6，7， 其中4，5，6分别放入剩余的数组空缺中，但是7 由于已经没有位置可写，则从0开始覆盖原有写入1的位置。注意这里我们没有设置write=0,而是直接在原Write值上继续加1，我们取模size即可获得新的写入位置（取模后重新返回头部）。

（4）当我们再次写入两个值：8，9的时候，由于与上一轮的Read发生了交叉，为了保证前后读写的顺序性，我们需要同时移动读指针的位置，使得读位置总是指向最旧的数据。

（5）这时候如果读取两个数据，则读指针只需要按照当前序列向前移动两个位置即可，分别获得值4，5 代表了最早的数据项，假如上面我们没有移动读指针，则读取的可能会是最新数据。

（6）如果我们这时候读取速度加快，假如读取5个值，可成功读取6，7，8，9，当读取到4值的时候由于此时，读写位置重叠（读数据不能超过写数据的位置，否则重复读取的问题），无法进一步读取数据。退出读取流程

后面的处理逻辑与上面保持一致即可，这里需要注意的是读写指针的序列值与实际读写数组序列值的映射关系，以及写操作会推动读指针向前移动的过程。

3. 代码实现

这里我们通过一个简单程序来实现上面的逻辑，采用Go语言实现，主要的处理逻辑部分很容易复制到其他的编程语言。

首先定义一个结构体来存储数据集合，并创建一个初始化函数，其参数就是该RingBuffer的容量大小。

type RingBuffer struct {
   data        []int
   size        int64
   writeCursor int64
   readCursor  int64
}

func NewRingBuffer(size int64) (*RingBuffer, error) {
   if size <= 0 {
      return nil, errors.New("size must be positive")
   }
   rb := RingBuffer{
      data: make([]int, size),
      size: size,
   }
   return &rb, nil
}

写入数据的流程通过Write函数来实现主要流程为：

1. 通过指针序列号，取模获取写位置索引

2. 写入数据到指定的索引位置

3. 比较读写位置的索引号，如果两个指针序列号相差一个周期，则读指针序列值+1

4. 写指针序列值+1

对于上面介绍的插入过程，我们其实可以设置不同的策略来应对读写位置重叠情况（写位置-读位置=容量）的情况，

1. 忽略新的插入

2. 覆盖旧的数据（上面的实例实现）

3. 阻塞写入，直到有空间写入新的数据

4. 重新分类数组，并复制到新的更大的数组

不同的情况可以满足不同的使用场景和需求，需要根据实际业务需求来选择。

func (rb *RingBuffer) Write(x int) {
   rb.data[rb.writeCursor%rb.size] = x
   if rb.writeCursor - rb.readCursor  == rb.size {
      rb.readCursor++
   }
   rb.writeCursor = rb.writeCursor + 1
}

读取指针，由于涉及到可能存在的读位置大于写位置的情况，所以我们引入错误来捕获这种异常情况，流程如下：

• 如果读指针大于等于写指针则报错误，数据不可读取

• 否则取模当前读指针，获取索引位置

• 获取该位置的数据

• 读指针序列值+1

func (rb *RingBuffer) Read() (int, error) {
   if rb.writeCursor > rb.readCursor {
      temp := rb.data[rb.readCursor%rb.size]
      rb.readCursor++
      return temp, nil
   }
   return 0, errors.New("read pointer great then write, wait seconds")
}

4. 使用场景

我们可以设想一下，假如我们使用链表或者容量可变的数组去存储上面的数据流，会出现哪些问题？

如果我们的数据流写入速度特别快，而读取的比较慢，则可能出现内存不断增长，甚至最终可能会导致服务OOM而崩溃.  而RingBuffer使用一个固定大小的数组，除了降低了动态内存分配的开销，还会限制最大内存占用容量，简直就是一举两得，除了可能会丢数据的问题。

其实算法的选择本身就是一种权衡选择，就像我们之前讲过的空间换时间的权衡，而在这里则是通过牺牲一部分数据完整性，来提升应用的可用性，想想布隆过滤器这种概率算法也应该是属于这一类。

对于并发访问的使用场景，我们可以通过锁或者信号量的机制提供安全的并发访问管理。另外也存在一些LockFree的RingBuffer实现，感兴趣的话可以自行搜索一下。

如果大家感兴趣可以订阅我的公众号： 银河系算法指南，获得更多有意思的算法知识。