存储具有多个查询条件的多个实体时要使用哪些数据结构？

Question

有一个存储单元,可容纳N个项目.最初这个单位是空的.该空间以线性方式布置,即一条线旁边的一个.每个存储空间都有一个数字,增加到N.

当有人丢弃他们的包裹时,会为其分配第一个可用空间.包裹也可以被拾取,在这种情况下空间变得空白.示例:如果总容量为4且1和2已满,则第3个进入的人将被分配空间3.如果1,2和3已满并且第2个空间变空,则下一个将来的人将是分配了空间2.

他们丢弃的包有2个独特的属性,分配给立即识别.首先,它们根据其内容进行颜色编码,然后为它们分配唯一的标识号(UIN).

我们想要的是查询系统:

1. 输入为彩色时,显示与此颜色关联的所有UIN.
2. 输入为彩色时,显示放置这些包的所有数字(存储空间编号).
3. 显示放置了给定UIN的项目的位置,即存储空间编号.

我想知道在这种情况下如何使用哪种数据结构,以便系统尽可能高效地工作？并且我没有给出最常见的这些操作,这意味着我将不得不针对所有情况进行优化.

请注意,即使查询过程不直接询问存储空间编号,但是当从商店中删除项目时,它将通过查询存储空间编号来删除.

Answer 1

为了获取存储空间数，我使用了最小堆方法PriorityQueue。删除和插入的时间复杂度为 O(log n)。

我使用了2个BiMap，自建的数据结构，用于存储UIN、颜色和存储空间编号之间的映射。这些 BiMap 在内部使用 HashMap 和大小为 N 的数组。

在第一个BiMap(BiMap1)中，aHashMap<color, Set<StorageSpace>>存储颜色到存储空间列表的映射。String[] colorSpace以及一个在存储空间索引处存储颜色的字符串数组。

在第二个BiMap(BiMap2)中，HashMap<UIN, storageSpace> stores the mapping between UIN and storageSpace. And a string arrayString[] uinSpace`将UIN存储在存储空间索引处。

使用这种方法可以直接进行查询：

1. 当输入为颜色时，显示与该颜色关联的所有UIN。 从 BiMap1 中获取存储空间列表，这些空间使用 BiMap2 中的数组来获取相应的 UIN。
2. 当输入为颜色时，显示这些包所放置的所有编号（存储空间编号）。使用BiMap1的HashMap来获取列表。
3. 显示具有给定 UIN 的项目的放置位置，即存储空间编号。使用 BiMap2 从 HashMap 中获取值。

现在，当我们需要删除一个存储空间时，两个 BiMap 都必须更新。在 BiMap1 中，从数组中获取条目，获取对应的 Set，并从该 Set 中删除空间号。从 BiMap2 中获取数组中的 UIN，将其删除，然后将其从 HashMap 中删除。

对于 BiMap 来说，删除和插入操作都是 O(1)。最小堆的工作时间为 O(Log n)，因此总时间复杂度为 O(Log N)