time - 建议一种查找时间复杂度最小的好方法

Question

我有一个包含 3 个标识符字段和 1 个值字段的结构。我有这些对象的列表。打个比方，标识符字段就像对象的主键。这3个字段唯一标识一个对象。

Class
{
   int a1;
   int a2;
   int a3;
   int value;
};

我会有一个包含 1000 个该数据类型对象的列表。我需要通过将 a1、a2 和 a3 的值传递给查找函数来检查这些身份键值的特定值，该函数将检查是否存在具有 a1、a2 和 a3 的特定值的任何对象并返回该值。实现此目的以实现最佳查找时间的最有效方法是什么？

我能想到的一个解决方案是有一个长度为 1000 的 3 维矩阵并填充其中的值。其查找时间为 O(1)。但缺点是。 1.我需要知道数组的长度。 2. 对于更高的身份字段(比如 20)，那么我将需要一个 20 维矩阵，这对内存来说是一个过度的消耗。对于我的实际实现，我有 23 个身份字段。

您能否建议一种存储这些数据的好方法，这将为我提供最佳的查找时间？

Answer 1

创建一个包含所有身份字段的键类，并定义适当的 equals 函数和哈希方法，然后使用 HashMap 从键类映射到其关联值。在预期的情况下，这将为您提供每次查找的 O(1) 时间复杂度，并且它只需要与观察到的实际按键组合数量成比例的空间(通常是数量的两倍，尽管您可以调整时间/空间的常数您想要的权衡)，而不是与所有可能的按键组合成比例的空间。