环形数组：介绍、应用、下标计算

╰+攻爆jí腚メ 2024-03-25 16:47 101阅读 0赞

### **一、环形数组介绍** ###

对于普通数组来说，头尾的下标都是固定的，头下标为0,尾下标为length-1。

而环形数组(circular array)通常使用两个额外的数字去标识数组的头下标和尾下标。

环形数组的逻辑结构如下图：

![367417e845357f2fdcb01daf529f62aa.png][]

环形数组的逻辑结构

这个像甜甜圈一样的逻辑结构即为环形数组，而在物理上它的形式还是个普通的数组。

环形数组的结构特点：

长度固定，下标永不越界，通常用两个指针标识数组的真实头尾下标。

#### 环形数组优点： ####

结构较灵活，越界时可以根据业务需求选择处理方式。

结构空间利用率高，并且数组充分利用了局部性原理及CPU缓存，性能好。

#### 环形数组缺陷： ####

头尾之间的元素不好维护，从中间删除某个元素会出现数组空隙。

这不是一个必须的结构，但是特定时候使用有奇效。

**小结：**

环形数组就是一个允许越界的数组结构。其可以在越界后通过取余的方式得到一个数组中存在的下标。

### 二、应用和场景 ###

环形数组默认头尾下标都是0，它可以轻易的实现栈和队列。

#### 栈 ####

做栈操作的话：

新增元素：头下标+1;删除元素：头下标元素弹出、头下标-1。

#### 队列 ####

做队列操作的话：

新增元素，头下标+1;删除元素：尾下标元素弹出、尾下标+1;

而真正重点其实在**下标越界**的处理上。

如果发现首尾重合或元素满了便阻塞操作，这就可以是个**阻塞栈、阻塞队列**;

如果发现首尾重合或元素满了便覆盖数据，这就可以是个**环、可以是缓存**;

当然上述只是提出一个可实现的思路，工程中的阻塞队列等并不一定都是这么实现的，重点是理解这个结构都能干什么。

不过JAVA中JUC包的ArrayBlockingQueue核心就是一个带有takeIndex和putIndex的环形数组，这个设计保证了在队列元素数量固定的限制条件下，有效的利用数组空间并用lock实现了阻塞，构造了一个简单的生产消费模式。（具体细节差异读者可自行阅读源码）

#### Ringbuffer缓冲 ####

数组本身访问就会得到优化，可以充分利用cpu并对缓存友好。这个特性可以完成一些高性能要求的使用场景，作为一个环形缓存使用的话，可以写数组头部且淘汰尾部数据，写满了或者删光了，可以直接阻塞处理，避免了锁争用，而且空间占用控制简单。这个利用很广，Distruptor、新版本canal等很多组件都有类似使用。

#### 时间轮 ####

kafka、zookeeper中采用时间轮来进行计数，本质也是个环形数组。

### 三、下标计算 ###

#### 下标加法 ####

比如数组长度是6,当前索引位置在4，向前两位则下标应变为0。

![5a2bd006defbb6e1024bf584b8630120.png][]

逻辑结构

![1131e67d8c4a4891bda98318b3335275.png][]

物理结构

正向比较简单，将当前索引和移动步数相加后的结果对数组length取余即可。

(4+2)%6 = 0

如果从位置0再前进10位则为：

(0+10)%6= 4

看起来非常OK。

#### 下标减法 ####

因为负数取余也是负数的问题，反向就有点烧脑了。（取模没有这个问题，比如python的%）

比如当前位置为1,我需要对其位置-2,那么向后两位下标应该是5。

如果还按照正向计算的话：

(1-2) % 6 = -1

![c61816289f29de01a6418195808ecb8a.png][]

减法逻辑结构

如果是python的话，这个下标-1已经可用了。不过java是没法接受负数下标的，我们只好画图研究一下：

![f2b66243641e97e10725aed4cc24ed7b.png][]

可以发现负数下标再加一个长度的距离就可以变为对应的正数下标！

也就是：

(1-2)%6=-1

\-1+6=5

这就正确了。

###    四、化简和总结 ###

根据以上观察，我们得到的临时结论为：

> 正向前进下标=(当前下标+前进步数) % 总长度  
> 反向前进下标=((当前下标-后退步数) % 总长度) + 总长度

可以尝试做一个化简：

因为步数会根据前进和后退自行调整正负号，所以：

> 正向前进下标=(当前下标+步数) % 总长度  
> 反向前进下标=(当前下标+步数) % 总长度 +总长度

同时，我们可以思考，当数组长度为6时,我们前进6步和前进12步的位置是相同的，前进5步和前进11步位置也是相同的。所以我们可以直接把步数+长度再对长度取余，就能得到真实的前进步数，这样不管是正向前进还是反向前进，公式可以统一变为：

再进行推广可以发现：

> 最终下标= （(当前下标+步数) % 总长度 +总长度）% 总长度

喜欢请点个关注，谢谢～

来源：[环形数组：介绍、应用、下标计算 - 知乎][-]

[367417e845357f2fdcb01daf529f62aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c5e29eeeebac406883c7caa0d91c6eef.png
[5a2bd006defbb6e1024bf584b8630120.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/84440283c41d4d8fa7ea960ffaa57050.png
[1131e67d8c4a4891bda98318b3335275.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/98e38d8c3f9748e8afbae6cf8a2fe2e6.png
[c61816289f29de01a6418195808ecb8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d523335462e34cf589db698e1242b4ce.png
[f2b66243641e97e10725aed4cc24ed7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e9e77f825c1743c082c4a666f42451f7.png
[-]: https://zhuanlan.zhihu.com/p/398066452