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

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

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

hashCode()方法返回一個(gè)int值,這個(gè)int值就是用這個(gè)對(duì)象的hashCode()方法產(chǎn)生的hash值。

在散列表中查找一個(gè)值的過(guò)程為,先通過(guò)鍵的hashCode()方法計(jì)算hash值,然后使用hash值產(chǎn)生下標(biāo)并使用下標(biāo)查找數(shù)組,這里為什么要用數(shù)組呢,因?yàn)閿?shù)組是存儲(chǔ)一組元素最快的數(shù)據(jù)結(jié)構(gòu),因此使用數(shù)組來(lái)表示鍵的信息。

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

數(shù)組并不直接保存值,因?yàn)椴煌逆I可能產(chǎn)生相同的數(shù)組下標(biāo),數(shù)組保存的是LinkedList,因此,散列表的存儲(chǔ)結(jié)構(gòu)外層是一個(gè)數(shù)組,容量固定,數(shù)組的每一項(xiàng)都是保存著Entry Object(同時(shí)保存key和value)的LinkedList。

由于下標(biāo)的沖突,不同的鍵可能會(huì)產(chǎn)生相同的bucket location,在使用put(key,value)時(shí),如果兩個(gè)鍵產(chǎn)生了相同的bucket location,由于LinkedList的長(zhǎng)度是可變的,所以會(huì)在該LinkedList中再增加一項(xiàng)Entry Object,其中保存著key和value。

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

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

在知道了散列的原理后我們可以自己實(shí)現(xiàn)一個(gè)簡(jiǎn)單的HashMap(例子來(lái)源于《Java編程思想(第四版)》)

public class SimpleHashMap extends AbstractMap {
    //內(nèi)部數(shù)組的容量
    static final int SIZE = 997;

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

    public V put(K key, V value) {
        V oldValue = null;
        //使用hashCode()方法產(chǎn)生hash值,使用hash值與數(shù)組容量取余獲得數(shù)組的下標(biāo)
        int index = Math.abs(key.hashCode()) % SIZE;
        //如果該桶位為null,則插入一個(gè)鏈表
        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();
            //對(duì)鍵使用equals()方法線性查詢value
            if (iPair.getKey().equals(key)) {
                oldValue = iPair.getValue();
                //找到了鍵以后更改鍵原來(lái)的value
                it.set(pair);
                found = true;
                break;
            }
        }
        //如果沒(méi)找到鍵,在bucket中增加一個(gè)Entry
        if (!found) {
            buckets[index].add(pair);
        }
        return oldValue;
    }
    
    //get()與put()的工作方式類似
    @Override
    public V get(Object key) {
        //使用hashCode()方法產(chǎn)生hash值,使用hash值與數(shù)組容量取余獲得數(shù)組的下標(biāo)
        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()產(chǎn)生的hash值能夠讓HashMap中的元素均勻分布在數(shù)組中,可以提高HashMap的運(yùn)行效率。
一個(gè)良好的hashCode()方法首先是能快速地生成hash值,然后生成的hash值能使HashMap中的元素在數(shù)組中盡量均勻的分布,
hash值不一定是唯一的,因?yàn)槿萘渴枪潭ǖ?總會(huì)有下標(biāo)沖突的情況產(chǎn)生。

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

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

對(duì)于對(duì)象中的每個(gè)關(guān)鍵域f(指equals()方法中涉及的域),完成以下步驟:

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

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

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

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

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

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

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

如果該域是一個(gè)對(duì)象引用,并且該類的equals()方法通過(guò)遞歸調(diào)用equals方式來(lái)比較這個(gè)域,則同樣為這個(gè)域遞歸地調(diào)用hashCode()

如果該域是一個(gè)數(shù)組,則要把每一個(gè)元素當(dāng)作多帶帶的域來(lái)處理,也就是說(shuō)遞歸地應(yīng)用上述原則

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

寫一個(gè)簡(jiǎn)單的類并用上述的規(guī)則來(lái)覆蓋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;
    }
}