摘要：中的使用散列來高效的查找和存儲值。理解中的方法是頂層對象中的方法因此中所有的對象都會帶有方法。中給出了覆蓋方法的最佳實踐把某個非零的常數值比如保存在一個名為的類型中。

Java中的HashMap使用散列來高效的查找和存儲值。HashMap內部使用Map.Entry的形式來保存key和value,使用put(key,value)方法存儲值,使用get(key)方法查找值。

Java中的hashCode()方法,是頂層對象Object中的方法,因此Java中所有的對象都會帶有hashCode()方法。
在各種最佳實踐中,都會建議在編寫自己的類的時候要同時覆蓋hashCode()和equals()方法,但是在使用散列的數據結構時(HashMap,HashSet,LinkedHashSet,LinkedHashMap),
如果不為鍵覆蓋hashCode()和equals()方法,將無法正確的處理該鍵。

hashCode()方法返回一個int值,這個int值就是用這個對象的hashCode()方法產生的hash值。

在散列表中查找一個值的過程為,先通過鍵的hashCode()方法計算hash值,然后使用hash值產生下標并使用下標查找數組,這里為什么要用數組呢,因為數組是存儲一組元素最快的數據結構,因此使用數組來表示鍵的信息。

由于數組的容量(也就是表中的桶位數)是固定的,所以不同的鍵可以產生相同的下標,也就是說,可能會有沖突,因此數組多大就不重要了,任何鍵總能在數組中找到它的位置。

數組并不直接保存值,因為不同的鍵可能產生相同的數組下標,數組保存的是LinkedList,因此,散列表的存儲結構外層是一個數組,容量固定,數組的每一項都是保存著Entry Object(同時保存key和value)的LinkedList。

由于下標的沖突,不同的鍵可能會產生相同的bucket location,在使用put(key,value)時,如果兩個鍵產生了相同的bucket location,由于LinkedList的長度是可變的,所以會在該LinkedList中再增加一項Entry Object,其中保存著key和value。

鍵使用hashCode()方法產生hash值后,利用hash值產生數組的下標,找到值在散列表中的桶位(bucket),也就是在哪一個LinkedList中,如果該桶位只有一個的Object,則返回該Value,如果該桶位有多個Object,那么再對該LinkedList中的Entry Object的鍵使用equals()方法進行線性的查詢,最后找到該鍵的值并返回。

最后對LinkedList進行線性查詢的部分會比較慢,但是,如果散列函數好的話,數組的每個位置就只有較少的值,因此不是查詢整個LinkedList,而是快速地跳到數組的某個位置,只對很少的元素進行比較,這就是HashMap會如此快的原因。

在知道了散列的原理后我們可以自己實現一個簡單的HashMap(例子來源于《Java編程思想(第四版)》)

public class SimpleHashMap extends AbstractMap {
    //內部數組的容量
    static final int SIZE = 997;

    //buckets數組,內部是一個鏈表,鏈表的每一項是Map.Entry形式,保存著HashMap的值
    @SuppressWarnings("unchecked")
    LinkedList>[] buckets = new LinkedList[SIZE];

    public V put(K key, V value) {
        V oldValue = null;
        //使用hashCode()方法產生hash值,使用hash值與數組容量取余獲得數組的下標
        int index = Math.abs(key.hashCode()) % SIZE;
        //如果該桶位為null,則插入一個鏈表
        if (buckets[index] == null) {
            buckets[index] = new LinkedList<>();
        }
        //獲得bucket
        LinkedList> bucket = buckets[index];
               
        MapEntry pair = new MapEntry<>(key, value);
        boolean found = false;
        
        ListIterator> it = bucket.listIterator();
        while (it.hasNext()) {
            MapEntry iPair = it.next();
            //對鍵使用equals()方法線性查詢value
            if (iPair.getKey().equals(key)) {
                oldValue = iPair.getValue();
                //找到了鍵以后更改鍵原來的value
                it.set(pair);
                found = true;
                break;
            }
        }
        //如果沒找到鍵,在bucket中增加一個Entry
        if (!found) {
            buckets[index].add(pair);
        }
        return oldValue;
    }
    
    //get()與put()的工作方式類似
    @Override
    public V get(Object key) {
        //使用hashCode()方法產生hash值,使用hash值與數組容量取余獲得數組的下標
        int index = Math.abs(key.hashCode()) % SIZE;
        if (buckets[index] == null) {
            return null;
        }
        //使用equals()方法線性查找鍵
        for (MapEntry iPair : buckets[index]) {
            if (iPair.getKey().equals(key)) {
                return iPair.getValue();
            }
        }
        return null;
    }

    @Override
    public Set> entrySet() {
        Set> set = new HashSet<>();
        for (LinkedList> bucket : buckets) {
            if (bucket == null) {
                continue;
            }
            for (MapEntry mpair : bucket) {
                set.add(mpair);
            }
        }
        return set;
    }

    public static void main(String[] args) {
        SimpleHashMap m = new SimpleHashMap<>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}

如果hashCode()產生的hash值能夠讓HashMap中的元素均勻分布在數組中,可以提高HashMap的運行效率。
一個良好的hashCode()方法首先是能快速地生成hash值,然后生成的hash值能使HashMap中的元素在數組中盡量均勻的分布,
hash值不一定是唯一的,因為容量是固定的,總會有下標沖突的情況產生。

《Effective Java》中給出了覆蓋hashCode()方法的最佳實踐:

把某個非零的常數值,比如17,保存在一個名為result的int類型中。

對于對象中的每個關鍵域f(指equals()方法中涉及的域),完成以下步驟:

為該域計算int類型的散列碼c,根據域的類型的不同,又可以分為以下幾種情況:

如果該域是boolean類型,則計算(f?1:0)

如果該域是String類型,則使用該域的hashCode()方法

如果該域是byte、char、short或int類型,則計算(int)f

如果該域是long類型,則計算(int)(f^>>>32)

如果該域是float類型,則計算Float.floatToIntBits(f)

如果該域是double類型,則計算Double.doubleToLongBits(f)返回一個long類型的值,再根據long類型的域,生成int類型的散列碼

如果該域是一個對象引用,并且該類的equals()方法通過遞歸調用equals方式來比較這個域,則同樣為這個域遞歸地調用hashCode()

如果該域是一個數組,則要把每一個元素當作多帶帶的域來處理,也就是說遞歸地應用上述原則

按照公式:result = 31 * result + c,返回result。

寫一個簡單的類并用上述的規則來覆蓋hashCode()方法

public class SimpleHashCode {
    private static long counter = 0;
    private final long id = counter++;
    private String name;
    
    @Override
    public int hashCode(){
        int result = 17;
        if (name != null){
            result = 31 * result + name.hashCode(); 
        }
        result = result * 31 + (int) id;
        return result;
    }
    
    @Override
    public boolean equals(Object o){
        return o instanceof SimpleHashCode && id == ((SimpleHashCode)o).id;
    }
}