Java8 HashMap鍵與Comparable接口

最容易使 HashMap 發(fā)生哈希沖突的方法是什么呢？我們可以創(chuàng)建一個(gè)類，讓它的哈希函數(shù)返回一個(gè)最糟糕的結(jié)果 —— 比如一個(gè)常數(shù)。

這也是我在面試的時(shí)候經(jīng)常問(wèn)面試者的問(wèn)題

哈希方法返回常數(shù)會(huì)造成什么結(jié)果？有很多次面試者會(huì)回答說(shuō) map 集合里會(huì)有且僅有一個(gè)元素，因?yàn)?map 中的舊元素總會(huì)被新的覆蓋。這個(gè)回答當(dāng)然是錯(cuò)誤的。

哈希沖突并不會(huì)導(dǎo)致 HashMap 覆蓋一個(gè)已經(jīng)存在于集合中的元素，這種情況只會(huì)在使用者試圖向集合中放入兩個(gè)元素，并且它們的鍵對(duì)于 equal() 方法是相等的時(shí)候才會(huì)發(fā)生。

鍵不相等但又會(huì)產(chǎn)生哈希沖突的不同元素最終會(huì)以某種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)在 HashMap 的同一個(gè)桶中（注意，在這種情況下，因?yàn)椴迦牒筒檎业牟僮鞫家馁M(fèi)更長(zhǎng)的時(shí)間，所以整體的性能就會(huì)受到影響）。

首先，我們用一個(gè)小程序來(lái)模擬哈希沖突。下面的寫法可能比較夸張，因?yàn)樗斐傻臎_突比現(xiàn)實(shí)中多得多，但這個(gè)程序?qū)τ谧C實(shí)哈希沖突的條件還是很重要的。

我們使用一個(gè) Person 對(duì)象作為 map 的鍵，以字符串作為值。下面是 Person 的具體實(shí)現(xiàn)，有一個(gè) firstName 字段，一個(gè) lastName 字段和一個(gè) ID 屬性，其中 ID 屬性以 UUID 對(duì)象表示。

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...
? ? }
? ? // ...
}

現(xiàn)在我們可以開始制造一些沖突。 

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");
}

上面的代碼在一臺(tái)高性能計(jì)算機(jī)上運(yùn)行了兩個(gè)半小時(shí)。其中，最后的查找操作耗費(fèi)了大約 40 毫秒?，F(xiàn)在我們對(duì) Person 類進(jìn)行修改：使它實(shí)現(xiàn) Comparable 接口，并且添加了下面的方法：

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

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

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

原來(lái)如此！所以，對(duì)于沒(méi)有實(shí)現(xiàn) Comparable 的鍵，最終的樹是不平衡的；而對(duì)于實(shí)現(xiàn)了 Comparable 的鍵，其二叉樹就會(huì)是高度平衡的。事實(shí)是這樣嗎？不是。HashMap 內(nèi)部是紅黑樹，也就是說(shuō)它總是平衡的。我通過(guò)反射機(jī)制，查看了最終的樹結(jié)構(gòu)。對(duì)于擁有 50000 個(gè)元素（不敢讓數(shù)字更大了）的 HashMap 來(lái)說(shuō)，兩種不同的情況下（實(shí)現(xiàn)或是不實(shí)現(xiàn) Comparable 接口）樹的高度都是 19 。

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

總而言之，在 Java 8 的 HashMap 里，如果一個(gè)桶里存放了大量的元素，它在達(dá)到閾值時(shí)就會(huì)被轉(zhuǎn)換為一棵紅黑樹，對(duì)于實(shí)現(xiàn)了 Comparable 接口的鍵來(lái)說(shuō)，插入或刪除的操作會(huì)比沒(méi)有實(shí)現(xiàn) Comparable 接口的鍵更簡(jiǎn)單。

通常，如果一個(gè)桶不會(huì)發(fā)生那么多次沖突的話，這整個(gè)機(jī)制不會(huì)帶來(lái)多大的性能提升，但起碼現(xiàn)在我們對(duì) HashMap 的內(nèi)部原理有了更多了解。

容器（LinkedList、HashMap、Compare）

HashSet的底層是HashMap，TreeSet的底層是TreeMap。

TreeSet中存放自定義類時(shí)應(yīng)該先指定比較的規(guī)則（compare）

1.內(nèi)部比較器|自然排序

要當(dāng)前比較的類型實(shí)現(xiàn)一個(gè)借口Comparable接口,重寫compareTo方法,方法的內(nèi)部制定比較規(guī)則， 硬編碼習(xí)慣,不夠靈活,每次修改源代碼。

public class Student implements Comparable<Student>{ 
    .........
    //重寫compareTo方法
    @Override
    public int compareTo(Student o) {
        return this.stuName.length()-o.stuName.length();
    }
}

2.外部比較器|自定義排序

使用任何一個(gè)實(shí)現(xiàn)類實(shí)現(xiàn)一個(gè)接口Comparator,重寫compare方法,方法的內(nèi)部制定比較規(guī)則。

public class CompareDemo {
    public static void main(String[] args) {
        Comparator<Student> comparator=new Home();
        //lambda表達(dá)式
        comparator=(Student o1, Student o2)->{return o1.getStuName().length()-o2.getStuName().length();};
        //指定使用參數(shù)比較器
        //TreeSet(Comparator<? super E> comparator)
        TreeSet treeSet=new TreeSet(comparator);
        treeSet.add(new Student("張三爸",40,158));
        treeSet.add(new Student("張三",20,168));
        treeSet.add(new Student("張三爺爺",60,178));
        System.out.println(treeSet);
    }
}
class Home implements Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2) {
        return o1.getStuName().length()-o2.getStuName().length();
    }
}

HashMap應(yīng)該注意的事項(xiàng) ：

手寫HashMap應(yīng)該注意對(duì)key值進(jìn)行比較，如果key相同則新的value覆蓋舊的value。table是上圖中橫向的數(shù)組，默認(rèn)初始值為16，計(jì)算key在數(shù)組中的位置時(shí)使用：key.hashcode%table.length,這種方式效率較低，一般使用 key.hashcode&(table.length-1)。

class MyHashMap{
    private Node [] table;
    private int size;
    public void put(Object key, Object value) {
        if(table==null){
            table=new Node[16];
        }
        int hash=getHash(key);
        Node node=table[hash];//獲取他在數(shù)組上的位置
        Node newNode=new Node(hash,key,value,null);
        if(node==null){
            table[hash]=newNode;
            size++;
        }else{
            while(true){
                //進(jìn)行key值的比較
                if(node.getKey().equals(key)){
                    node.setValue(value);
                    break;
                }
                if(node==null){
                    break;
                }
                node=node.getNext();
            }
            node.setNext(newNode);
            size++;
        }
    }
    public int getHash(Object key){
        return key.hashCode()&(table.length-1);
    }
    @Override
    public String toString() {
        StringBuilder sbr=new StringBuilder("{");
        for(Node node:table){
            while(node!=null){
                sbr.append(node.getKey()+"--->"+node.getValue()+",");
                node=node.getNext();
            }
        }
        sbr.setCharAt(sbr.length()-1,'}');
        return sbr.toString();
    }
}

• Properties：用來(lái)代替hashMap，實(shí)現(xiàn)了Map接口，線程安全的
• HashTable：可以代替hashMap,線程安全

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。