O（1）中values.contains（object）的高效java映射？

最近，我開始編寫一個工具來建模圖形（節點和邊，既用對象代表，又用鄰接矩陣或簡單數字表示），以便在畢業學校旁邊的軟件開發中獲得一些實踐。我想要一個節點知道它的鄰居和它發生的邊緣。做這件事的一個顯而易見的方法是採取一個HashSet和一個HashSet。我想然而做的是有一個方法O（1）中values.contains（object）的高效java映射？

Node_A.getEdge(Node B)

返回在O節點A和B之間的邊緣（1）。我正在考慮通過使用一個HashMap替換上面提到的兩個HashSet來實現這一點，該HashMap將鄰居映射到連接節點和鄰居的邊緣。例如，調用

Node_A.hashmap.get(B)

應該返回這裏連接A和B.我的問題是，是否有辦法有

HashMap.keySet().contains(Node A); 
HashMap.values().contains(Edge e);

爲O都工作的邊緣（1）？如果標準庫不是這種情況，那麼是否有實現爲keySet（）和values（）添加，刪除，包含，調整大小？

來源

2012-10-20 G. Bach

只要您正確實施了'hashcode'和'equals（）''''keySet（）'和'entrySet（）'，''就具有'O（1）'的複雜性。只有'valueSet'具有'O（n）'複雜性。 –

@AmitD我打錯了，我的意思是values（）而不是entrySet（）。你的意思是我從keySet（）取回的Set在O（1）中添加，刪除，包含，大小還是你的意思是方法keySet（）本身在O（1）中運行？ –

儘量不要過分想這個。例如你說的是通過Node_A.getEdge(Node B)得到A和B之間的邊緣。但通常它是A-> B-被認爲是邊緣的信息。（所以你需要你應該檢索的信息。）

你說你想O（1），可以理解，顯然存儲一個鄰接矩陣只會給你O（n），所以你不能使用它;但已經是第二最明顯的選擇存儲在每個節點對象內的相鄰節點的列表將給你你想要的。（注意：這與全局鄰接列表不同，它會給你O（n））。

來源

2012-10-20 18:59:20

實際上，使用鄰接矩陣會給我O（1）時間來查看兩個特定節點之間是否存在邊，但在檢查節點的鄰居時當然是正確的。我的麻煩主要來自於我想擁有代表邊的對象，因爲後來它們應該被賦予任意屬性，如果只隱含關於哪些節點通過邊連接的信息，這將變得麻煩。我可能是在反覆說這個，因爲我需要做的就是使用HashSet和HashMap，但是它的內存不便宜：P –

O（n）鄰接矩陣表示檢索節點的所有鄰居（不檢查兩個節點是否是相鄰的）。是的，如果需要附加屬性，將邊緣存儲爲對象就可以了，只需讓每個節點都有一個邊緣對象列表。 –

@ G.Bach實際上，將連接節點存儲在邊緣（在這種情況下，「包含（邊緣）」實現很簡單）可能更有效，因爲每個節點邊緣都會有一個額外的對象字段而不是'Map.Entry'（一個'Object' + 2對象字段）+一個'Map'（一個'Object'，一個對象字段，一個'Map.Entry'數組）/ n個邊。 –

正如AmitD所說的，HashSet和HashMap對於contains，get和put都有不變的時間。對於HashMap.valueSet().contains(Edge e)的情況，您可以嘗試在Google Guava圖書館中查看HashBiMap。

來源

2012-10-20 19:00:02 zvez

謝謝，我會看看這個;乍一看，它看起來不會是我正在尋找的，因爲我基本上試圖最小化空間需求，並且使用由兩個HashMaps支持的數據結構比我目前擁有的更昂貴。 –

@ G.Bach它並不昂貴，因爲HashSet是由HashMap支持的。 –

@FrankPavageau啊，我沒有意識到 - 我必須更深入地看待Zvezdochet的推薦！ –

O（1）中values.contains（object）的高效java映射？

回答

相關問題