爲什麼HashMap使用TreeNode而不是Comparable鍵？

我知道在Java 8中HashMap針對分佈不均的hashCode進行了優化。並且在超過閾值的情況下，它重建從鏈接列表到樹狀結構中的節點。此外，它是stated，此優化不適用於不可比較的密鑰（在leas性能沒有改進）。在下面的例子中，我把不Comparable鍵進入HashMap爲什麼HashMap使用TreeNode而不是Comparable鍵？

import java.util.HashMap; 
import java.util.Map; 
import java.util.concurrent.TimeUnit; 
import java.util.stream.IntStream; 

class Main { 
    public static void main(String[] args) throws InterruptedException { 
     Map<Key, Integer> map = new HashMap<>(); 

     IntStream.range(0, 15) 
       .forEach(i -> map.put(new Key(i), i)); 

     // hangs the application to take a Heap Dump 
     TimeUnit.DAYS.sleep(1); 
    } 
} 

final class Key { 
    private final int i; 

    public Key(int i) { 
     this.i = i; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (this == o) return true; 
     if (o == null || getClass() != o.getClass()) return false; 
     Key key = (Key) o; 
     return i == key.i; 
    } 

    @Override 
    public int hashCode() { 
     return 1; 
    } 
}

但檢查堆轉儲表明節點被重新組合成樹。

我的問題是，爲什麼節點被重建成樹，如果它不會提高性能和標準，在這種情況下的節點進行比較，找出其中的關鍵應該是正確的節點，並留下嗎？

來源

2017-07-15 Artem Petrov

我認爲你有點誤解了答案的意思。 Comparable不是需要，它只是一個優化，可能在散列相等時使用 - 以決定將條目移動到左側還是右側（perfectly balanced red-black tree node）。後來如果按鍵是不是可比，那它會用System.identityHashcode。

弄清楚哪個鍵應該是正確的節點，並留下

它轉到正確的 - 更大的鍵轉到正確的，但隨後的樹可能需要平衡。 一般來說，你可以查找的Tree如何成爲perfectly balanced red black tree確切的算法，如here

來源

2017-07-15 11:12:04 Eugene

AFAIK它不使用標識哈希代碼，只是關鍵對象的哈希碼。 –

@JornVernee It * does *。查看'HashMap'裏面的'tieBreakOrder'方法 – Eugene

@Eugene這是散列碼相同的情況下的回退（散列碰撞不一定是這種情況，儘管我猜這是在這個例子中）。如果你看看它在'putTreeVal'中的使用位置，你會發現它試圖在這之前使用密鑰的哈希碼。 –

爲什麼HashMap使用TreeNode而不是Comparable鍵？

回答

相關問題