理解Map

1.映射表的基本思想是它維護(hù)的是鍵－值（對(duì)）關(guān)聯(lián)，因此你可以使用鍵來(lái)查找值。
2.下面是一個(gè)簡(jiǎn)單的關(guān)聯(lián)數(shù)組的創(chuàng)建：

public class AssociativeArray<K, V> {
    private Object[][] pairs;
    private int index;
    public AssociativeArray(int length) {
        pairs = new Object[length][2];
    }
    public void put(K key, V value) {
        if (index >= pairs.length) 
            throws new ArrayIndexOutOfBoundsException();
        pairs[index++] = new Object[]{key, value};
    }
    @SupressWarning("unchecked")
    public V get(K key) {
        for (int i = 0; i < pairs.length; i++) {
            if (key.equals(pairs[i][0])) {
                return (V) pairs[i][1];
            }
        }
        return null;
    }
}

上面的代碼只是具有一定的說(shuō)明性，但是缺乏效率，并且由于具有固定尺寸而顯得很不靈活。

一.性能

1.HashMap使用了特殊的值，稱為散列碼，來(lái)取代對(duì)鍵的緩慢搜索。散列碼是相對(duì)唯一的、用以代表對(duì)象的int值，他是通過(guò)將該對(duì)象的某些信息進(jìn)行轉(zhuǎn)換而生成的。
2.hashCode()是類Object中的方法，因此所有Java對(duì)象都能產(chǎn)生散列碼。HashMap就是使用對(duì)象的hashCode()進(jìn)行快速查詢的，此方法能夠顯著提高性能。
3.下面是幾種基本的Map的實(shí)現(xiàn)：

4.對(duì)Map中使用的鍵的要求與對(duì)Set中的元素的要求一樣。任何鍵都必須具有一個(gè)equals()方法；如果鍵被用于散列Map，那么它必須還具有恰當(dāng)?shù)?strong>hashCode()方法；如果鍵被用于TreeMap，那么它必須實(shí)現(xiàn)Comparable。
5.關(guān)聯(lián)數(shù)組中的基本方法是put()和get()。keySet()方法返回一個(gè)由Map的鍵組成的Set?？梢灾苯油ㄟ^(guò)values()方法獲取“值”，該方法會(huì)產(chǎn)生一個(gè)包含Map中所有“值”的Collection，需要注意的是對(duì)該Collection的任何改動(dòng)都會(huì)反映到與之相關(guān)聯(lián)的Map。

二.SortedMap

1.使用SortedMap（TreeMap是其現(xiàn)階段的唯一實(shí)現(xiàn)），可以確?！版I”處于排序狀態(tài)。
2.SortedMap接口中的一些特殊方法如下：

三.LinkedHashMap

1.為了提高速度，LinkedHashMap散列化所有的元素，但是在遍歷鍵值對(duì)時(shí)，卻又以元素的插入順序返回鍵值對(duì)。
2.可以在構(gòu)造器中設(shè)定LinkedHashMap，使之采用基于訪問(wèn)的最近最少使用算法。于是沒有被訪問(wèn)過(guò)的元素酒會(huì)出現(xiàn)在隊(duì)列的最前面。對(duì)于需要定期清理元素以節(jié)省空間的程序來(lái)說(shuō)，此功能使得程序很容易就能實(shí)現(xiàn)。

散列與散列碼

1.使用標(biāo)準(zhǔn)類庫(kù)中的類來(lái)作為HashMap的鍵沒有問(wèn)題，因?yàn)樗邆淞随I所需的全部性質(zhì)。
2.當(dāng)自己創(chuàng)建用作HashMap的鍵的類，有可能會(huì)忘記在其中放置必需的方法，而這是通常會(huì)犯的一個(gè)錯(cuò)誤。
3.可能你會(huì)認(rèn)為，只需編寫恰當(dāng)?shù)?strong>hashCode()方法的覆蓋版本即可。但是它仍然無(wú)法正常運(yùn)行，除非你同時(shí)覆蓋equals()方法，它也是Object的一部分。HashMap使用equals()判斷當(dāng)前的鍵是否與表中的相同。
4.正確的equals()方法必須滿足的條件：
（1）自反性。對(duì)任意x，x.equals(x)一定返回true。
（2）對(duì)稱性。對(duì)任意x和y，如果y.equals(x)返回true，則x.equals(y)一定返回true。
（3）傳遞性。對(duì)任意x，y，z，如果有x.equals(y)返回true，y.equals(z)返回true，則x.equals(z)一定返回true。
（4）一致性。對(duì)任意x和y，如果對(duì)象中用于等價(jià)比較的信息沒有改變，那么無(wú)論調(diào)用x.equals(y)多少次，返回的結(jié)果應(yīng)該保持一致，要么一直是true要么一直是false。
（5）對(duì)任何不是null的x，x.equals(null)一定返回false。

一.理解hashCode()

1.使用散列的目的是：想要試用一個(gè)對(duì)象來(lái)查找另外一個(gè)對(duì)象。

二.為速度而散列

1.散列的價(jià)值在于速度：散列使得查詢得以快速進(jìn)行。
2.散列將鍵保存在某處，以便能夠快速找到。存儲(chǔ)一組元素最快的數(shù)據(jù)結(jié)構(gòu)是數(shù)組嗎所以使用它來(lái)表示鍵的信息。
3.數(shù)組并不保存鍵本身。而是通過(guò)鍵對(duì)象生成一個(gè)數(shù)字，將其作為數(shù)組的下標(biāo)。這個(gè)數(shù)字就是散列碼，由hashCode()方法生成。
4.為解決數(shù)組容量被固定的問(wèn)題，不同的鍵會(huì)產(chǎn)生相同的下標(biāo)。也就是說(shuō)，可能會(huì)有沖突。因此，數(shù)組多大就不重要了，任何鍵總能在數(shù)組中找到它的位置。
5.查詢一個(gè)值的過(guò)程首先就是計(jì)算散列碼，然后使用散列碼查詢數(shù)組。如果能夠沒有沖突，那就有了一個(gè)完美的散列函數(shù)，但這只是特例。通常。沖突由外部鏈接處理：數(shù)組并不直接保存值，而是保存值的list。然后對(duì)list中的值使用equals()方法進(jìn)行線性查詢。這部分的查詢自然會(huì)比較慢，但是，如果散列函數(shù)好的話，數(shù)組的每個(gè)位置就只有較少的值。因此，不會(huì)查詢整個(gè)list，而是快速地跳到數(shù)組的某個(gè)位置，只對(duì)很少的元素進(jìn)行比較。

三.覆蓋hashCode()

1.在使用HashMap的時(shí)候，你無(wú)法控制數(shù)組的下標(biāo)值的產(chǎn)生。這個(gè)值依賴于具體的HashMap對(duì)象的容量，而容量大改變與容器的充滿程度和負(fù)載因子有關(guān)。
2.設(shè)計(jì)hashCode()最重要的一個(gè)因素：無(wú)論何時(shí)，對(duì)同一個(gè)對(duì)象調(diào)用hashCode()都應(yīng)該產(chǎn)生同樣的值。
3.不應(yīng)該使hashCode()依賴于具有唯一性的對(duì)象信息，尤其是使用this的值。因?yàn)檫@樣做無(wú)法生成一個(gè)新的鍵，使之與put()中原始的鍵值對(duì)中的鍵相同。
4.hashCode()必須基于對(duì)象的內(nèi)容生成散列碼。散列碼不鄙視獨(dú)一無(wú)二的，但是通過(guò)hashCode()和equals()，必須能夠完全確定對(duì)象的身份。
5.好的hashCode()應(yīng)該產(chǎn)生分布均勻的散列碼。如果散列碼都集中在一塊，那么HashMap或者HashSet在某些區(qū)域的負(fù)載會(huì)很重，這樣就不如分布均勻的散列函數(shù)快。
6.產(chǎn)生hashCode()的基本指導(dǎo)：
（1）給int變量result賦予某個(gè)非零值常量，例如17。
（2）為對(duì)象內(nèi)每一個(gè)有意義的域f（即每個(gè)可以做equals()操作的域）計(jì)算出一個(gè)int散列碼c：

（3）合并計(jì)算得到的散列碼：
result = 37 * result + c;
（4）返回result。
（5）檢查hashCode()最后生成的結(jié)果，確保相同的對(duì)象有相同的散列碼。
7.compareTo()的創(chuàng)建方式：排序的規(guī)則首先按照實(shí)際類型排序，然后如果有名字的話，按照name排序，最后安好創(chuàng)建的順序排序。