Java8 HashMap鍵與Comparable接口小結(jié)

更新時間：2022年01月29日 10:28:59 作者：mitsuhide1992

這篇文章主要介紹了Java8 HashMap鍵與Comparable接口小結(jié)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

Java8 HashMap鍵與Comparable接口

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

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

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

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

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

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

我們使用一個 Person 對象作為 map 的鍵，以字符串作為值。下面是 Person 的具體實(shí)現(xiàn)，有一個 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...
? ? }
? ? // ...
}

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

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

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

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

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

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

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

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

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

容器（LinkedList、HashMap、Compare）

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

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

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

要當(dāng)前比較的類型實(shí)現(xiàn)一個借口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.外部比較器|自定義排序

使用任何一個實(shí)現(xiàn)類實(shí)現(xiàn)一個接口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)該注意對key值進(jìn)行比較，如果key相同則新的value覆蓋舊的value。table是上圖中橫向的數(shù)組，默認(rèn)初始值為16，計(jì)算key在數(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();
    }
}