使用双键创建哈希图

Question

我正在寻找适合我的问题的数据结构。我希望能够使用两个键尽可能有效地选择节点对象。插入和删除也需要高效。基本上每个节点对象都有一对两个键。这些对是唯一的，但各个密钥却不是。我需要能够选择一组具有两个键之一的特定值的节点。

示例：

Node1 具有键 a1 和 b1

Node2 具有键 a1 和 b2

Node3 具有键 a2 和 b2

我希望能够选择具有键 a1,b1 的节点，而且还能够选择将 b2 作为 key2。

我当然可以制作两个 HashMap（每个键一个），但这是一种丑陋的解决方案，因为当我添加或删除某些内容时，我必须在两个映射中都执行此操作。由于会进行大量的添加和删除操作，因此我更愿意一次性完成此操作。有人对如何做到这一点有任何想法吗？

显然，使用一个将两个键合并在一起的键并不能解决问题，因为我还需要能够搜索单个键，而不必搜索整个地图。那效率不会很高。问题是效率问题。我可以只搜索映射中的每个条目以查找特定键，但我想使用哈希，以便我可以立即使用两个键之一选择多个节点对象。

我不是在寻找像 MultiKeyMap 这样的东西，因为在这个数据结构中，第一个键始终保持不变，您只能添加键，而不是用不同的键替换第一个键。我希望能够在第一个和第二个键之间切换。

我确实不想也不想使用相同的密钥存储多个对象。如果您查看示例，您会发现这两个键在一起始终是唯一的。这可以被视为单个键，因此我不会在同一键下存储多个对象。但是，如果您查看各个键，这些键并不是唯一的，因此我确实想存储各个键引用的多个对象。

Answer 1

如果您可以使用库，请查看 Guava 的 Table 接口。它将行和列与一个值关联起来。行和列可能是您的第一个和第二个键。您还可以按行或按列进行搜索。

此接口的实现之一是 hash基于。

Answer 2

您必须创建一个关键类（相等被视为 Point )：

public class Key {

    int field1;
    int field2;

    public boolean equals(Object o) {
        if (o == null || !(o instanceof Key)) return false;
        Key other = (Key) o;
        return field1 == other.field1 && field2 == other.field2;
    }

    public int hashCode() {
        return field1*field2; // doesn't matter if some keys have same hash code
    }

}

用于选择第一个字段中具有特定值的键：

public List<Key> getKeysWithField1EqualsTo(int value) {
    List<Key> result = new ArrayList<>();
    for (Key k: map.keySet()) {
        if (k.field1 == value) result.add(k);
    }
    return result;
}

Answer 3

由于这对于您当前的问题来说相当具体，因此您很可能需要开发自己的集合。我会包装两个 MultiMaps 从 Apache Commons 到我自己的集合类中，该集合类同时处理两个多映射的更新，并使用我的类执行插入和查询。

Answer 4

编写一个简单的类，该类能够包含两个值（键）并重写 equals(..) 和 hashCode() 以进行映射使用的相等检查。使用这个简单的类作为地图的键。

在这里您可以找到一个哈希图兼容的配对类（第二个答案）：

C++ Pair等价于什么？在Java中？

Answer 5

由于 HashMap 只能对每个对象的一个​​散列进行排序，因此您将永远无法“开箱即用”选择不同的列表。我建议使用具有两个键的元组，然后迭代 HashMap 并仅选择那些具有 tuple.key1=X 的元素。

Answer 6

HashMap 可以将任何对象作为键，所以为什么不创建一个具有 2 个字段的类并将此类视为您的键。您还可以重写 Equals 方法来告诉它键如何相等

Answer 7

我认为我们可以这样做：对于每个键，我们可以计算相应的哈希码。

key1 -> hashcode1
key2 -> hashcode2

然后我们有一个二维数组，有 N 列和 N 行。

key1 -> rowIndex: hashcode1 MOD N
key2 -> columnIndex: hashcode2 MOD N

然后我们将该项目存储在array[rowIndex][columnIndex]中。

在此实现中，您可以获得具有目标 key1 和任意 key2 的所有条目。您还可以获取具有目标 key2 和任意 key1 的所有条目。

当存在大量冲突时，该数组可能会扩展，就像对普通哈希图所做的那样。