在巨大的内存空间中搜索空闲位置

Question

实际问题如下：在拥有百万个停车位的停车库中，您将使用什么数据结构来查找免费停车位

我的想法：

• 我可以使用LinkedHashMap并继续将空闲点移动到队列的前面，但我认为这不是正确的解决方案

有什么想法吗？

Answer 1

您已经知道您的停车场结构的大小（一百万个车位），这在物理上是有意义的。因此，如果你需要的所有信息都是一个地块是否空置，那么使用一个位数组，其中空置为假，占用为真

boolean slots[] = new boolean[1000000];

如果您需要存储更多信息，如插槽中的汽车信息、插槽与最近入口的距离等，请使用：

 Slot[] slots = new Slot[1000000];

插槽类将类似于

public class Slot{
    Car car;//object for car in slot
    boolean occupied;//whether slot is vacant: may be redundant
    Cost cost;//a set of fields: distance from entrance; parking fee for "good" slots, etc.
}

所以你继续。。。

Answer 2

PriorityQueue，其中优先级定义为停车位和入口之间的距离。

Answer 3

我会使用一个位集，其中每个位代表一个停车位。值1表示空闲，0表示已使用。线性搜索空闲点就可以了。非常容易实现，asm足够快。

Answer 4

改进kasavbere的解决方案，如果可以的话，我建议使用BitSet/BitArray类。BitSet使用长数组，每个长值表示64个插槽。与布尔值相比，这有效地将数组的总大小减少了8倍[布尔值数组通常每个元素占用1个字节]。BitSet还提供了从特定索引中获取下一个集合或空闲槽的方法，所以您不必为此编写自己的方法。

Answer 5

我们可以使用队列。

队列包含开始时的所有百万个条目。如果需要停车位，则出列。如果停车位变得免费，请查询。

Answer 6

1. 维持一个基本上容纳1-n辆汽车的阵列，其中n是停车场的大小。维护停车场编号的最小堆（PriorityQueue）。每次有新车进入，都要检查阵列是否已满，而不是在队列中轮询最近的批号。轮询从队列中删除最小的一个，并将其用作数组的索引

一旦一辆车离开了这个位置，就把这个位置重新添加到队列中。未来的民意调查将返回下一个最近的可用停车场。