什麼數據結構用於查找2棵樹的交集

我有兩棵樹，其中包含節點，在創建它們之後，我將第一棵樹的所有節點都放到鏈表中，第二棵樹放到一個哈希表中，作爲地圖的關鍵字。我想從樹中找到兩個節點，它們具有相同的變量：states（long type）。因此，在創建之後我打電話：什麼數據結構用於查找2棵樹的交集

List<Node> list; 
HashMap<Node, Node> hashtable; 

...create nodes, take them to the collections 

for(Node n : list){ 
    if(hashtable.containsKey(n)){ 
     //doSomething   
    } 
}

我使用的HashMap，becouse它是非常快的，艱難的，我有400萬（400萬美元）的節點。我已經覆蓋Node類的equals方法，但似乎像containskey方法檢查hashcodes，但據我瞭解，它只需檢查等於方法link to java reference。所以問題是我應該使用什麼數據結構來檢查這個事情，或者我應該如何重寫代碼？

繼承人是我的equals方法：

@Override 
    public boolean equals(Object obj) { 
    if(obj instanceof Node){ 
     Node node = (Node)obj; 
     return (states == node.getStates()); 
    } 
    return false; 
}

來源

2012-04-08 Ferenc Dajka

你必須重寫equals()使相等的對象時，必須具有相同的哈希代碼重寫hashCode()方法。參考http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html#equals(java.lang.Object）。

來源

2012-04-08 15:46:37

我使用父節點和節點的狀態變量來創建散列，然後它們是唯一的，如果我只使用狀態變量，那麼有很多具有相同狀態的節點，所以我有在hashmap中大約有50000個節點，而不是200萬個。但如果它們的狀態相同，我仍然希望節點相等。 – 2012-04-08 15:52:58

我的意思是我想只使用散列排序地圖中的節點 – 2012-04-08 15:54:52

這並不取消關於符合equals（）和hashCode（）的要求。所以你有兩個「Node」的樹並且想要找到交集。爲此，我建議你使用優秀的Apache utils。請參閱[鏈接]（http://commons.apache.org/collections/apidocs/org/apache/commons/collections/CollectionUtils.html#intersection（java.util.Collection，％20java.util.Collection）） – 2012-04-08 16:01:23

什麼數據結構用於查找2棵樹的交集

回答

相關問題