使用双键创建散列表

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

实施例：

Node1上具有键a1和b1

节点2具有密钥A1及B2

节点3具有密钥A2和B2

我想是例如能够选择具有密钥a1，b1的节点，但也选择具有b2的所有节点作为密钥2。

我当然可以制作两个HashMaps（每个键一个），但这是一种丑陋的解决方案，因为当我添加或删除某些东西时，我必须在两个地图中执行此操作。由于会有大量的添加和删除操作，我宁愿一次去做。有没有人有关于如何做到这一点的任何想法？

很明显，将两个键合并在一起的单个键不能解决问题，因为我还需要能够搜索单个键而不必搜索整个地图。这不会很有效。问题是效率问题。我可以在地图上的每个条目中搜索特定的键，但是我想使用散列，以便可以使用两个键之一即时选择多个节点对象。

我不是在寻找类似于MultiKeyMap的东西，因为在这个数据结构中第一个键总是保持不变，你只能添加键而不能用另一个键替换第一个键。我希望能够在第一个和第二个键之间切换。

我确实不想用相同的密钥存储多个对象。如果你看一下这个例子，你可以看到这两个键总是唯一的。这可以看作是一个单一的密钥，因此我不会在同一个密钥下存储多个对象。但是，如果您查看各个键，这些键并不是唯一的，因此我确实需要存储由各个键引用的多个对象。

来源

2011-12-21 Danielle

你在找什么像[这个]（http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/MultiKeyMap.html）？ – aishwarya 2011-12-21 14:18:17

是否要用同一个密钥存储多个对象？ – 2011-12-21 14:34:03

如果你可以用一个图书馆，看一看番石榴的Table接口。它将一行和一列与一个值相关联。行和列可能是您的第一个和第二个键。您也可以按行或按列进行搜索。

该接口的实现之一是hash based。

来源

2011-12-21 14:21:00 Luciano

编写一个简单的类，它可以包含两个值（键），并覆盖equals（..）和hashCode（）以进行地图使用的相等性检查。使用这个简单的类作为地图的关键。

在这里你可以找到一个HashMap兼容对类（第2个答案）：

What is the equivalent of the C++ Pair<L,R> in Java?

来源

2011-12-21 14:18:31 Dennis

这并不能解决OP的问题（他需要在一个密钥上搜索并获取多个值）。 – dasblinkenlight 2011-12-21 14:23:09

由于这个问题对您的问题非常具体，因此您很可能需要开发自己的收藏。我会将Apache Commons中的两个MultiMaps包装到我自己的集合类中，该类同时处理两个多地图的更新，并使用我的类执行插入和查询。

来源

2011-12-21 14:22:02 dasblinkenlight

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

来源

2011-12-21 14:22:05

HashMaps可以将任何对象作为Key，所以为什么不创建一个带有2个字段的类并将此类视为您的键。你也可以重写Equals方法来告诉它的钥匙怎么也等于

来源

2011-12-21 14:23:44

你必须创建一个键类（平等被视为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 
    } 

}

对于在一个特定的值选择键第一场：

来源

2011-12-21 14:26:44 Alberto

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

key1 -> hashcode1 
key2 -> hashcode2

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

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

然后，我们将商品存储在array[rowIndex][columnIndex]中。

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

当存在很多冲突时，这个数组可能会扩展，就像您对普通hashmap所做的一样。

来源

2015-08-11 02:35:21 nisxiya

使用双键创建散列表

回答

相关问题