有哪些Java库提供随机访问队列实现？

Question

我正在Java中实现对事件流的滑动窗口。因此，我需要一种数据结构，使我能够执行以下操作：

1. 当出现新事件时，在数据结构的末尾添加；
2. 当旧事件被处理时，从数据结构的开头删除；
3. 对数据结构的元素进行标准随机访问（size()，get(i)），通常是List的“读”操作；
4. 对于上述所有操作都是有效率的；
5. 没有大小限制。

不需要其他访问。也不需要线程安全。

我目前使用ArrayList完成这个任务。但我希望有更高效的方法；remove(0)方法（第2步）在ArrayList中效率低下。

1.和2.是标准的队列操作。然而，JDK中Queue的实现（如ArrayDeque）不允许在3.中使用get(i)。

因此，我想知道是否有任何适用于商业用途的库具有这样的实现。

如果没有，我想我会写自己的...

- Calum

---

这些操作相对频繁吗？你可能需要在空间上做一些妥协以换取时间——例如，你可以使用一个循环链表并带有索引以便快速检索（索引：我忘记这种结构的名称了；一个指向0和n/2的指针的二叉树，每个指针都存储其一半中点的指针等等）。 - Alex Feinman

Answer 1

我遇到了这个问题，尝试通过复制ArrayDeque的源代码并添加类似以下内容来解决：

E get(index){ return elements[(head + index) % size];}

- Jacky Li

---

谢谢，我也刚刚移植了ArrayDeque，这样我就可以在Android API Level 8上使用它了。我只需要添加以下方法：public E get(int index) {return elements[(head + index) % size()];} - gsgx

实际上，我发布的代码有时会导致空指针。这段代码可以工作，但我不知道为什么：public E get(int index) {return elements[(head + index) % elements.length];} - gsgx

@gsingh2011：内部，队列由预先分配大小的数组（即“元素”）支持。 因此，elements.length返回内部数组的大小而不是队列本身的size（）。 - FuzzY

Answer 2

似乎这是一个 循环缓冲区 的任务 - 只要队列有固定的容量就可以了。我不知道是否有标准实现。但是，这里有一个不错的自己编写的方法。

- sfussenegger

---

忘了说它应该是无界的 - 现在已经更新了问题。 - Calum

如果需要的话，您可以增加容量 - 就像ArrayList一样。不过这样会很昂贵。 - sfussenegger

当你需要更多容量时，将数组大小加倍仍然使插入的平摊时间为常数，因此只有在需要硬延迟保证时才会变得“昂贵”。问题是关于Java的，其中GC通常比数组加倍对于不可预测的延迟更重要。我认为循环缓冲区是符合要求的正确答案。 - Jamey Sharp

Answer 3

如果您有足够大的数组，您可以使用基本数组来实现队列，只需使用索引作为列表头，并使用模运算符，以便在需要时进行包装。

因此，您基本上拥有支持插入和删除功能的循环数组。

更新：

复制一个数组到一个更大的数组是一个快速操作，所以当接近末尾时，只需将大小翻倍，然后将数组复制为插入的一步。总体而言，您仍将具有非常快的访问速度，因为增加和复制不应该成为规范。

- James Black

---

更具体地说，当您需要更多容量时，将数组大小加倍仍然使插入的平摊时间为常数。这是一种可靠的方法。 - Jamey Sharp

Answer 4

这个队列的事件进出速度有多快？

一方面，您可以使用“足够大”的循环缓冲区。

虽然它在技术上是“有界”的，但您可以根据需要将其扩展为“无界”的。

同样，当它很“安静”时，您可以通过减小总容量来“缩小”它。

但对于许多应用程序而言，具有100、1000或甚至10000项容量的循环缓冲区实际上是无限制的。

- Will Hartung

Answer 5

我所能想到的唯一一个会实现这样接口的库是LinkedList，但说实话我不确定它的性能特征如何。

- Jasoon

---

这样做不利于高效的随机访问 - 即调用 get(i)。 - Calum

非常正确。我很想看看这里会出现什么，因为我不确定如何有效地将高效的随机访问与标准FIFO队列所获得的速度相结合... - Jasoon

JDK中的ArrayDeque（一个队列）实际上有一个元素数组（可以调整大小）和头部和尾部字段。因此，它是一种合适的实现，但它不以随机访问方式公开元素 - 它只公开头部和尾部。 - Calum

使用LinkedList的一种可能方法——它是一个Deque，但作为List可以使用Collections.shuffle()进行洗牌——因此根据需要进行随机访问，可以执行单个洗牌操作，然后弹出/删除/迭代所需数量的随机项。 https://dev59.com/K3fZa4cB1Zd3GeqPVsEO#19259094 - JeremyDouglass

Answer 6

只是提供一种替代方法，以避免自己编写代码，请谨慎考虑：根据您需要多频繁地进行随机访问get(i)以及您需要什么性能（以及您的队列大小通常会有多大），您可以在需要访问元素时始终使用ArrayDeque.toArray()[i]。 toArray()在内部使用System.arraycopy()，对于小型队列大小和偶尔使用应该非常快。了解为什么需要随机访问队列以及它的频率可能有所帮助--也许有一种不需要随机访问的实现算法的不同方式。

- Chris B.

Answer 7

如果确实必须是无界的，那么像ConcurrentSkipListMap这样的东西可能会很有用，如果你为每个事件分配一个递增的序列作为地图中的键。 它提供了pollFirst/LastEntry等方法。 如果你可以牺牲它的无界性，那么环形缓冲区可能是你需要的。

- Derek Lewis

Answer 8

二项堆可以实现O(1)的平摊插入和O(log n)的平摊删除最小值；我相信它也可以实现O(log**2 n)的平摊随机访问。队列推送将元素插入堆中，使用连续的整数作为键。

使用红黑树，您可以在所有插入、删除最小值和随机访问的情况下，以O(log n)的悲观时间复杂度进行队列推送。这是因为树将具有一组连续的整数作为键，而队列的第k个元素将是树中具有第k个键的元素。

- Adrian Panasiuk