java - 如何在java中实现队列？越快越好

Question

这是面试官提出的一个问题，在java中实现队列。基本上，这个队列只需要提供 Enqueue/Dequeue 操作。

执行速度更快的实现将获得更高的分数。假设每个方法将以相同的频率被调用。因此，每种方法都应该同样快。

Answer 1

听起来他在寻找像中断库这样的环形缓冲区。

它可以比 ArrayBlockingQueue 快 10 倍。

我写了一个库，它不是那么快，但解决了一个不同的问题，即队列持久性。它也可以比 ArrayBlockingQueue 更快，但保留所有数据并且可以在进程之间共享。Java编年史

---

“ 假设每个方法都以相同的频率被调用。” 如果这是真的，你只需要一个 1 的环形缓冲区。最简单的是 AtomicReference。注意：这是无锁和无 gc 的。

public class AtomicReferenceQueue<T> {
    private final AtomicReference<T> ringBufferOfOne = new AtomicReference<T>();

    /**
     * @return true if added.
     */
    public boolean add(T t) {
        return ringBufferOfOne.compareAndSet(null, t);
    }

    public void offer(T t) throws InterruptedException {
        while (!ringBufferOfOne.compareAndSet(null, t))
            if (Thread.interrupted())
                throw new InterruptedException();
    }

    public T poll() {
        return ringBufferOfOne.getAndSet(null);
    }

    public T take() throws InterruptedException {
        T t;
        while ((t = ringBufferOfOne.getAndSet(null)) == null)
            if (Thread.interrupted())
                throw new InterruptedException();
        return t;
    }
}

事实上，在微秒级别上确保完全相同的频率是不可能的。如果入队频率几乎总是低于出队频率（而且你不介意烧掉一个 cpu ;），这个“环形缓冲区”会工作得最好