Java8 HashMap鍵與Comparable接口小結

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

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

Java8 HashMap鍵與Comparable接口

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

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

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

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

鍵不相等但又會產(chǎn)生哈希沖突的不同元素最終會以某種數(shù)據(jù)結構存儲在 HashMap 的同一個桶中（注意，在這種情況下，因為插入和查找的操作都要耗費更長的時間，所以整體的性能就會受到影響）。

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

我們使用一個 Person 對象作為 map 的鍵，以字符串作為值。下面是 Person 的具體實現(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");
}

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

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

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

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

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

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

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

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

容器（LinkedList、HashMap、Compare）

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

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

1.內部比較器|自然排序

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

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

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

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

public class CompareDemo {
    public static void main(String[] args) {
        Comparator<Student> comparator=new Home();
        //lambda表達式
        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應該注意的事項：

在這里插入圖片描述

手寫HashMap應該注意對key值進行比較，如果key相同則新的value覆蓋舊的value。table是上圖中橫向的數(shù)組，默認初始值為16，計算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){
                //進行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();
    }
}