理解Map

1.映射表的基本思想是它維護的是鍵－值（對）關聯才漆，因此你可以使用鍵來查找值牛曹。
2.下面是一個簡單的關聯數組的創(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;
    }
}

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

一.性能

1.HashMap使用了特殊的值，稱為散列碼鸳玩，來取代對鍵的緩慢搜索阅虫。散列碼是相對唯一的、用以代表對象的int值不跟，他是通過將該對象的某些信息進行轉換而生成的颓帝。
2.hashCode()是類Object中的方法，因此所有Java對象都能產生散列碼窝革。HashMap就是使用對象的hashCode()進行快速查詢的躲履，此方法能夠顯著提高性能。
3.下面是幾種基本的Map的實現：

4.對Map中使用的鍵的要求與對Set中的元素的要求一樣矮瘟。任何鍵都必須具有一個equals()方法瞳脓；如果鍵被用于散列Map，那么它必須還具有恰當的hashCode()方法澈侠；如果鍵被用于TreeMap劫侧，那么它必須實現Comparable。
5.關聯數組中的基本方法是put()和get()埋涧。keySet()方法返回一個由Map的鍵組成的Set板辽。可以直接通過values()方法獲取“值”棘催，該方法會產生一個包含Map中所有“值”的Collection劲弦，需要注意的是對該Collection的任何改動都會反映到與之相關聯的Map。

二.SortedMap

1.使用SortedMap（TreeMap是其現階段的唯一實現）醇坝，可以確币毓颍“鍵”處于排序狀態(tài)。
2.SortedMap接口中的一些特殊方法如下：

三.LinkedHashMap

1.為了提高速度，LinkedHashMap散列化所有的元素谚赎，但是在遍歷鍵值對時淫僻，卻又以元素的插入順序返回鍵值對。
2.可以在構造器中設定LinkedHashMap壶唤，使之采用基于訪問的最近最少使用算法雳灵。于是沒有被訪問過的元素酒會出現在隊列的最前面。對于需要定期清理元素以節(jié)省空間的程序來說闸盔，此功能使得程序很容易就能實現悯辙。

散列與散列碼

1.使用標準類庫中的類來作為HashMap的鍵沒有問題，因為它具備了鍵所需的全部性質迎吵。
2.當自己創(chuàng)建用作HashMap的鍵的類躲撰，有可能會忘記在其中放置必需的方法，而這是通常會犯的一個錯誤钓觉。
3.可能你會認為茴肥，只需編寫恰當的hashCode()方法的覆蓋版本即可。但是它仍然無法正常運行荡灾，除非你同時覆蓋equals()方法，它也是Object的一部分。HashMap使用equals()判斷當前的鍵是否與表中的相同批幌。
4.正確的equals()方法必須滿足的條件：
（1）自反性础锐。對任意x，x.equals(x)一定返回true荧缘。
（2）對稱性皆警。對任意x和y，如果y.equals(x)返回true截粗，則x.equals(y)一定返回true信姓。
（3）傳遞性。對任意x绸罗，y意推，z，如果有x.equals(y)返回true珊蟀，y.equals(z)返回true菊值，則x.equals(z)一定返回true。
（4）一致性育灸。對任意x和y腻窒，如果對象中用于等價比較的信息沒有改變，那么無論調用x.equals(y)多少次磅崭，返回的結果應該保持一致儿子，要么一直是true要么一直是false。
（5）對任何不是null的x砸喻，x.equals(null)一定返回false柔逼。

一.理解hashCode()

1.使用散列的目的是：想要試用一個對象來查找另外一個對象。

二.為速度而散列

1.散列的價值在于速度：散列使得查詢得以快速進行恩够。
2.散列將鍵保存在某處卒落，以便能夠快速找到。存儲一組元素最快的數據結構是數組嗎所以使用它來表示鍵的信息蜂桶。
3.數組并不保存鍵本身儡毕。而是通過鍵對象生成一個數字，將其作為數組的下標扑媚。這個數字就是散列碼腰湾，由hashCode()方法生成。
4.為解決數組容量被固定的問題疆股，不同的鍵會產生相同的下標费坊。也就是說，可能會有沖突旬痹。因此附井，數組多大就不重要了讨越，任何鍵總能在數組中找到它的位置。
5.查詢一個值的過程首先就是計算散列碼永毅，然后使用散列碼查詢數組把跨。如果能夠沒有沖突，那就有了一個完美的散列函數沼死，但這只是特例着逐。通常。沖突由外部鏈接處理：數組并不直接保存值意蛀，而是保存值的list耸别。然后對list中的值使用equals()方法進行線性查詢。這部分的查詢自然會比較慢县钥，但是秀姐，如果散列函數好的話，數組的每個位置就只有較少的值魁蒜。因此囊扳，不會查詢整個list，而是快速地跳到數組的某個位置兜看，只對很少的元素進行比較锥咸。

三.覆蓋hashCode()

1.在使用HashMap的時候，你無法控制數組的下標值的產生细移。這個值依賴于具體的HashMap對象的容量搏予，而容量大改變與容器的充滿程度和負載因子有關。
2.設計hashCode()最重要的一個因素：無論何時弧轧，對同一個對象調用hashCode()都應該產生同樣的值雪侥。
3.不應該使hashCode()依賴于具有唯一性的對象信息，尤其是使用this的值精绎。因為這樣做無法生成一個新的鍵速缨，使之與put()中原始的鍵值對中的鍵相同。
4.hashCode()必須基于對象的內容生成散列碼代乃。散列碼不鄙視獨一無二的旬牲，但是通過hashCode()和equals()，必須能夠完全確定對象的身份搁吓。
5.好的hashCode()應該產生分布均勻的散列碼原茅。如果散列碼都集中在一塊，那么HashMap或者HashSet在某些區(qū)域的負載會很重堕仔，這樣就不如分布均勻的散列函數快擂橘。
6.產生hashCode()的基本指導：
（1）給int變量result賦予某個非零值常量，例如17摩骨。
（2）為對象內每一個有意義的域f（即每個可以做equals()操作的域）計算出一個int散列碼c：

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