使用双重键创建哈希表

Question

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

例如：

Node1拥有a1和b1两个键

Node2拥有a1和b2两个键

Node3拥有a2和b2两个键

我希望能够选择具有a1,b1键的节点，同时也能选择所有具有b2作为第二个键的节点。

当然，我可以制作两个HashMap（每个键一个），但这种方法有些丑陋，因为当我添加或删除某些内容时，我必须在两个映射中都执行此操作。由于会经常添加和删除内容，所以我更喜欢一次完成此操作。有人有关于如何做到这一点的想法吗？

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

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

我需要存储具有相同键的多个对象和不同键的多个对象。如果您看一下示例，就会发现两个键加在一起总是唯一的。因此，这可以视为单个键，因此我不会在同一个键下存储多个对象。但是，如果查看单个键，则这些键不是唯一的，因此我希望存储由单个键引用的多个对象。

- Danielle

---

你是否在寻找类似于这个的东西？ - aishwarya

你想要存储具有相同键的多个对象吗？ - Vishal Pawar

Answer 1

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

该接口的实现之一是基于哈希的。

- Luciano

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;
}

- Alberto

Answer 3

由于这个问题比较特定，你很可能需要开发自己的集合。我会将两个来自Apache Commons的MultiMap封装到我的集合类中，以便同时处理两个多重映射的更新，并使用我的类进行插入和查询。

- Sergey Kalinichenko

Answer 4

编写一个简单的类，能够包含两个值（键），并重写equals（..）和hashCode（）以进行地图使用的相等性检查。将此简单类用作地图的键。

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

{{link1：Java中C ++ Pair 的等效物是什么？}}

- Dennis

---

这并不能解决原帖作者的问题（他需要用一个关键词搜索并获取多个值）。 - Sergey Kalinichenko

Answer 5

由于HashMap每个对象只能按照一个哈希值进行排序，因此您将永远无法直接选择不同的列表。我建议使用具有两个键的元组，然后遍历HashMap并仅选择具有tuple.key1 = X的元素。

- Willem Mulder

Answer 6

HashMap可以将任何对象作为键，因此为什么不创建一个具有2个字段的类，并将该类视为您的键。您还可以覆盖Equals方法以告诉它如何判断键是否相等。

- Adel Boutros

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的条目。

当发生大量冲突时，此数组可能会扩展，就像您使用普通哈希映射一样。

- nisxiya