使用雙鍵創建散列表

我正在爲我的問題尋找合適的數據結構。我希望能夠使用兩個鍵儘可能高效地選擇節點對象。插入和刪除也需要高效。基本上每個節點對象都有一對兩個鍵。這些配對是獨一無二的，但個別密鑰卻不是。我需要能夠爲兩個鍵之一選擇一組具有特定值的節點。使用雙鍵創建散列表

實施例：

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

使用雙鍵創建散列表

回答

相關問題