Java 8 HashMap鍵與Comparable接口

這篇文章主要介紹了 Java 8 在 HashMap 哈希沖突處理方面的新特性。

相對之前的版本，Java 8 在許多方面有了提升。其中有很多類被更新了，HashMap 作為最常使用的集合類之一也不例外。這篇文章將介紹 Java 8 中的 HashMap 在處理哈希沖突時的新特性。

讓我們從頭開始。最容易使 HashMap 發生哈希沖突的方法是什么呢？我們可以創建一個類，讓它的哈希函數返回一個最糟糕的結果 —— 比如一個常數。這也是我在面試的時候經常問面試者的問題：哈希方法返回常數會造成什么結果？有很多次面試者會回答說 map 集合里會有且僅有一個元素，因為 map 中的舊元素總會被新的覆蓋。這個回答當然是錯誤的。哈希沖突并不會導致 HashMap 覆蓋一個已經存在于集合中的元素，這種情況只會在使用者試圖向集合中放入兩個元素，并且它們的鍵對于 equal() 方法是相等的時候才會發生。鍵不相等但又會產生哈希沖突的不同元素最終會以某種數據結構存儲在 HashMap 的同一個桶中（注意，在這種情況下，因為插入和查找的操作都要耗費更長的時間，所以整體的性能就會受到影響）。

首先，我們用一個小程序來模擬哈希沖突。下面的寫法可能比較夸張，因為它造成的沖突比現實中多得多，但這個程序對于證實哈希沖突的條件還是很重要的。

我們使用一個 Person 對象作為 map 的鍵，以字符串作為值。下面是 Person 的具體實現，有一個 firstName 字段，一個 lastName 字段和一個 ID 屬性，其中 ID 屬性以 UUID 對象表示。

public class Person {
    private String firstName;
    private String lastName;
    private UUID id;
    public Person(String firstName, String lastName, UUID id) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.id = id;
    }
    @Override
    public int hashCode() {
        return 5;
    }
    @Override
    public boolean equals(Object obj) {
        // ... pertty good equals here taking into account the id field...
    }
    // ...
}

現在我們可以開始制造一些沖突。

private static final int LIMIT = 500_000;
private void fillAndSearch() {
     Person person = null;
     Map<Person, String> map = new HashMap<>();

     for (int i=0;i<LIMIT;i++) {
        UUID randomUUID = UUID.randomUUID();
        person = new Person("fn", "ln", randomUUID);
        map.put(person, "comment" + i);
     }
     long start = System.currentTimeMillis();
     map.get(person);
     long stop = System.currentTimeMillis();
     System.out.println(stop-start+" millis");
}

上面的代碼在一臺高性能計算機上運行了兩個半小時。其中，最后的查找操作耗費了大約 40 毫秒。現在我們對 Person 類進行修改：使它實現 Comparable 接口，并且添加了下面的方法：

@Override
public int compareTo(Person person) {
    return this.id.compareTo(person.id);
}

再一次運行之前的程序，這一次在我的機器上它耗費的時間少于 1 分鐘。其中，最終的查找操作耗費的時間接近為 0 毫秒 —— 比之前提高了 150 倍！

就像前面說的，Java 8 做了很多優化，其中也包括HashMap 類。在 Java 7 中，兩個不同的元素，如果它們的鍵產生了沖突，那么會被存儲在同一個鏈表中。而從 Java 8 開始，如果發生沖突的頻率大于某一個閾值（8），并且 map 的容量超過了另一個閾值（64），整個鏈表就會被轉換成一個二叉樹。

原來如此！所以，對于沒有實現 Comparable 的鍵，最終的樹是不平衡的；而對于實現了 Comparable 的鍵，其二叉樹就會是高度平衡的。事實是這樣嗎？不是。HashMap 內部是紅黑樹，也就是說它總是平衡的。我通過反射機制，查看了最終的樹結構。對于擁有 50000 個元素（不敢讓數字更大了）的 HashMap 來說，兩種不同的情況下（實現或是不實現 Comparable 接口）樹的高度都是 19 。

那么，為什么之前的實驗結果會有那么大的差別呢？原因在于，當 HashMap 想要為一個鍵找到對應的位置時，它會首先檢查新鍵和當前檢索到的鍵之間是否可以比較（也就是實現了 Comparable 接口）。如果不能比較，它就會通過調用 tieBreakOrder(Object a,Object b) 方法來對它們進行比較。這個方法首先會比較兩個鍵對象的類名，如果相等再調用 System.identityHashCode 方法進行比較。這整個過程對于我們要插入的 500000 個元素來說是很耗時的。另一種情況是，如果鍵對象是可比較的，整個流程就會簡化很多。因為鍵對象自身定義了如何與其它鍵對象進行比較，就沒有必要再調用其他的方法，所以整個插入或查找的過程就會快很多。值得一提的是，在兩個可比的鍵相等時（compareTo 方法返回 0）的情況下，仍然會調用 tieBreakOrder 方法。

總而言之，在 Java 8 的 HashMap 里，如果一個桶里存放了大量的元素，它在達到閾值時就會被轉換為一棵紅黑樹，對于實現了 Comparable 接口的鍵來說，插入或刪除的操作會比沒有實現 Comparable 接口的鍵更簡單。通常，如果一個桶不會發生那么多次沖突的話，這整個機制不會帶來多大的性能提升，但起碼現在我們對 HashMap 的內部原理有了更多了解。

來自： http://www.tuicool.com//articles/YnqAZf3