这个队列最大的特点在于它在不伤害性能的前提下大规模地减少了内存的分配以及释放，从而非常优雅的内存使用。

这个队列的建议使用环境

• 程序对内存的使用很敏感

传统线程安全队列存在的问题

不定长队列：不定长队列存在的问题是如果消费者的速度远小于生产者的速度，那么会导致大量的元素堆积，造成大量的内存被浪费。

循环队列：循环队列存在的问题是队列中各个 slot 的元素使用时间是不均衡的，也就是说可能 slot 1 使用的时间比较长，但是 slot 2 可能使用的时间比较短，导致 slot 2 不能被后续线程提前使用。

所以映射队列解决的问题不光是能够更少地使用内存，同时能够让队列中的资源能够更加高效地被利用。一个非常自然的想法是维护一个自己的内存池，每份内存加个标签表示是否正在被使用。也就是说我们插入索引时首先向内存池申请，寻找到一份空闲的内存，然后将要被放入到队列中的元素拷贝到这份内存，最后放入循环队列等待调用。

这个方法我尝试过，但行不通。为什么，因为每个线程执行任务的花费的时间可能差距很大，这会造成内存池的空洞。为什么？因为没有线程能保证先开始的先结束，尤其是在遇到 B+ 树页面分裂的时候，所以我们自己的内存池在使用一段时间后会可能变成下面这个样子。

为了解决以上的问题，映射队列横空出世。

elements_：存放实际队列元素

avail_：空闲元素的位置，avail_[0]表示第一个空闲元素在elements_中的位置，也就是说，elements_[avail_[0]]才表示空闲元素的具体位置

work_：使用中元素的位置，和avail_相对应

front_：avail_和work_的指针，avail_[front_]表示下一个空闲元素的位置，work_[front_]表示可以被使用的元素的位置

avail_back_：avail_的指针，avail_[avail_back_]表示最后一个空闲元素的位置

work_back_：work_的指针，work_[work_back_]同样表示可以被使用的元素的位置

• 这个队列如何工作？

首先，队列会这样被初始化。假设队列有N个元素，则avail_中的元素依次初始化为0，１，……N-1，而work_中的元素都初始化为-1。

当我们的线程池中的线程发现work_[work_back_]大于等于0时，则结束等待，获取实际元素，并且记录下此时work_[work_back_]的值，同时将work_[work_back_]赋值为-1，并且work_back_+1，然后进行具体工作的执行。

当工作执行完毕后，利用我们之前记录的work_[work_back_]的值，将其赋值给avail_[avail_back_]，然后avail_back_+1。

至此一次完整的放置任务、执行任务的过程就结束了。

这个队列成功地解决了所有在上面被描述过的问题：

1. 队列占用内存很少
2. 不损失性能

我们已经介绍完了为什么会有映射队列以及它相对于不定长队列、循环队列的优势。评论里有同学说可以用链表，我发现一个空闲链表加上一个工作链表确实可以发挥映射队列的功能，而且很好理解也很好实现，但是一次完整的操作需要加锁4次，解锁4次，而映射队列只需要3次，所以又发现了一个映射队列的优点。

与传统的队列不同，映射队列有4个API，分成两对。分别是：

其中Get和Push由用户调用，Pop和Put由线程池调用。

下面我们具体介绍映射队列的每个API。