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

Question

有一个存储单元，可容纳 N 件元素。最初这个单元是空的。空间以线性方式布置，即一个挨着另一个排成一条直线。每个存储空间都有一个编号，递增直到N。

当有人放下他们的包裹时，它会被分配到第一个可用空间。包裹也可以被取走，在这种情况下空间就空了。示例:如果总容量为 4。并且 1 和 2 已满，则第三个进来的人将被分配到空间 3。如果 1、2 和 3 已满而第二个空间空出，则下一个进来的人将是分配空间 2.

它们掉落的包裹有 2 个独特的属性，分配给立即识别。首先，根据内容对它们进行颜色编码，然后为它们分配一个唯一标识号 (UIN)。

我们要的是查询系统:

1. 当输入为颜色时，显示与该颜色关联的所有UIN。
2. 当输入为彩色时，显示所有这些包被放置的编号(存储空间编号)。
3. 显示具有给定 UIN 的项目的放置位置，即存储空间编号。

我想知道在这种情况下如何使用哪些数据结构，以便系统尽可能高效地工作？而且我没有给出这些操作中哪一个操作最频繁，这意味着我将不得不针对所有情况进行优化。

请注意，虽然查询过程不是直接查询存储空间号，但是当一个项目从商店中移除时，它是通过查询存储空间号来移除的。

Answer 1

您提到了三个要进行的查询。让我们一一处理。

我想不出有一种数据结构可以同时帮助您处理所有三个查询。所以我要给出一个具有三个数据结构的答案，你将必须维护所有三个 DS 的状态以保持应用程序正常运行。将其视为从您的应用程序获得所需功能的相当快的性能的成本。

---

When the input is color, show all the UIN associated with this color.

使用将 Color 映射到一组 UIN 的 HashMap。每当一个项目:

• 已添加 - 查看颜色是否存在于 HashMap 中。如果是，则将此 UIN 添加到集合中，否则使用新集合创建一个新条目，然后添加 UIN。

• 已删除 - 找到此颜色的集合并从集合中删除此 UIN。如果集合现在为空，您可以完全删除此条目。

---

When the input is color, show all the numbers where these packages are placed.

维护一个 HashMap，将 UIN 映射到放置传入包裹的编号。从我们在前一个案例中创建的 HashMap 中，您可以获得与给定 Color 关联的所有 UIN 的列表。然后使用此 HashMap，您可以获得该颜色集中存在的每个 UIN 的编号。

所以现在，当要添加一个包时，您必须将条目添加到特定颜色桶中的先前 HashMap 以及此 HashMap。删除时，您必须从此处.Remove() 条目。

---

最后，

Show where an item with a given UIN is placed.

如果您完成了前面的操作，那么您已经拥有将 UIN 映射到数字的 HashMap。这个问题只是前一个问题的子问题。

---

正如我在顶部提到的，第三个 DS 将是一个 Min-Heap of ints。堆将在开始时使用前 N 个整数进行初始化。然后，随着包的到来，堆将被轮询。返回的数字将代表要放置此包的存储空间。如果存储单元已满，则堆将为空。每当删除一个包时，它的编号将被添加回堆中。因为它是一个最小堆，最小的数字会冒泡到顶部，满足你的情况，当 4 和 2 为空时，下一个要填充的空间将是 4。

---

让我们对这个解决方案进行大 O 分析以完成。

• 初始化时间: 此设置的时间为 O(N)，因为我们必须初始化 N 的堆.其他两个 HashMap 一开始是空的，因此不会产生时间成本。

• 添加包的时间: 将包括获取数字然后在 HashMap 中进行适当输入的时间。从堆中获取数字最多需要 O(Log N) 时间。 HashMaps 中条目的添加将是 O(1)。因此，最坏情况下的总时间为 O(Log N)。

• 删除包的时间:最坏的情况下也是 O(Log N)，因为从 HashMap 中删除的时间为 O(1)只有同时，将释放的数字添加回最小堆的时间上限为 O(Log N)。