摘要：將散列碼作為數(shù)組的下標(biāo)，該數(shù)組的一個(gè)單元指向一個(gè)鏈表，鏈表上的一個(gè)節(jié)點(diǎn)就是一個(gè)對(duì)象。散列碼不必獨(dú)一無二，應(yīng)關(guān)注生成速度。好的應(yīng)該產(chǎn)生分布均勻的散列碼。

數(shù)組是一種效率最高的存儲(chǔ)和隨機(jī)訪問對(duì)象引用的一個(gè)簡單的線性序列，雖然訪問快速，但為之付出的代價(jià)是數(shù)組的大小固定，并且在其生命周期中不可改變。數(shù)組與其他容器之間的區(qū)別在于：效率、類型和保存基本類型的能力。但隨著自動(dòng)包裝機(jī)制的出現(xiàn)，容器已經(jīng)可以與數(shù)組幾乎一樣方便，而數(shù)組僅存的優(yōu)點(diǎn)就是效率。

應(yīng)該 “優(yōu)先選擇容器而不是數(shù)組”，只有在已經(jīng)證明性能稱為問題（并且切換到數(shù)組對(duì)性能提高有所幫助）時(shí)，你才應(yīng)該將程序重構(gòu)為使用數(shù)組

數(shù)組標(biāo)識(shí)符就是一個(gè)引用，用以保存指向其他對(duì)象的引用，數(shù)組的一個(gè)單元指向在堆中創(chuàng)建的一個(gè)真實(shí)對(duì)象。對(duì)像數(shù)組與基本類型數(shù)組的區(qū)別在于，對(duì)象保存的是引用，基本類型數(shù)組保存的是基本類型的值。

數(shù)組的 length屬性，表示數(shù)組的大小，而不是實(shí)際保存的元素個(gè)數(shù)。新生成的對(duì)象數(shù)組，會(huì)被默認(rèn)的初始化為 null，基本類型數(shù)組則會(huì)初始化為對(duì)應(yīng)基本類型的默認(rèn)值，對(duì)于對(duì)象數(shù)組，可以檢測其中的引用是否為 null，進(jìn)而確定某個(gè)位置是否存在對(duì)象。當(dāng)數(shù)組不被需要時(shí)，垃圾回收器會(huì)負(fù)責(zé)清理數(shù)組，否則將一直存在。

System.arraycopy()：復(fù)制一個(gè)數(shù)組比用 for 循環(huán)復(fù)制要快得多，且該方法對(duì)所有類型做了重載。當(dāng)復(fù)制對(duì)象數(shù)組時(shí)，只是復(fù)制對(duì)象的引用（屬淺拷貝）。

Arrays.asList(T... a)：將多個(gè)元素轉(zhuǎn)換成 List 列表，底層表示的還是數(shù)組，當(dāng)嘗試進(jìn)行 add()、delete()操作時(shí)將在運(yùn)行時(shí)報(bào)錯(cuò)。

Arrays.sort(T[] a, Comparator c)：按照給定的比較器對(duì)指定的數(shù)組進(jìn)行排序。

Arrays.binarySearch(T[] a,T key, Comparator c)：對(duì)一個(gè)有序的數(shù)組采用二分查找獲取對(duì)象下標(biāo)，如果數(shù)組存在重復(fù)元素，可能返回的不精確。注：如果使用了Comparator排序了一個(gè)對(duì)象數(shù)組，則調(diào)用此方法時(shí)傳入的Comparator必須是同一個(gè)。

comparator用于指定元素的排列順序，在常見的數(shù)據(jù)類型中已經(jīng)被默認(rèn)實(shí)現(xiàn)，對(duì)于需要按照某種規(guī)則進(jìn)行排序的時(shí)候，提供Comparator或者實(shí)現(xiàn) java.lang.Comparable接口。

class DemoComparator implements Comparator {

    @Override
    public int compare(Demo o1, Demo o2) {
        if (o1.value == o2.value) {
            return 0;
        }
        return o1.value < o2.value ? 1 : -1;
    }
    
}

一個(gè)獨(dú)立元素的序列，這些元素都服從一條或多條規(guī)則，提供了存放一組對(duì)象的方式。List必須按照插入的順序保存元素，而Set不能有重復(fù)元素。Queue按照隊(duì)列排隊(duì)規(guī)則來確定對(duì)象產(chǎn)生的順序。

PriorityQueue：優(yōu)先級(jí)隊(duì)列，聲明下一個(gè)彈出最需要的元素（具有最高的優(yōu)先級(jí)），通過默認(rèn)排序或提供 Comparator。當(dāng)調(diào)用 peek()、poll()、remove()方法時(shí)，獲取的元素是隊(duì)列中優(yōu)先級(jí)最高的。

ListIterator：Iterator的子類，只用于對(duì)各種 List 類的訪問，可以實(shí)現(xiàn)雙向移動(dòng)。hasNext() / next()、hasPrevious() / previous()

對(duì)于隨機(jī)訪問的 get/set操作，背后有數(shù)組支持的 List 比 ArrayList 稍快一點(diǎn)，但是對(duì)于 LinkedList，將會(huì)變得很慢，因?yàn)樗皇轻槍?duì)隨機(jī)訪問操作而設(shè)計(jì)的。
最佳的做法是將 ArrayList 作為默認(rèn)首選，當(dāng)因?yàn)榻?jīng)常插入和刪除操作而性能下降時(shí)，才去選擇 LinkedList。如果使用的是固定數(shù)量的元素，既可以選擇List，也可以選擇數(shù)組。

HashSet以某種順序保存元素，LinkedHashSet按照元素插入的順序保存元素，而 TressSet按照排序維護(hù)元素。
HashSet的性能基本上總是比 TreeSet好，特別在添加和查詢?cè)貢r(shí)。 TreeSet存在的唯一原因是它維持元素的排序順序，因此迭代的時(shí)候，TreeSet通常比用HashSet要快。

Map的各個(gè)實(shí)現(xiàn)類的行為特性的不同在于，效率、鍵值對(duì)的保存及呈現(xiàn)次序、對(duì)象的保存周期、映射表如何在多線程程序中工作和判定 ”鍵“等價(jià)的策略等方面。

使用Map時(shí)，首選HashMap，TreeMap維護(hù)著散列數(shù)據(jù)結(jié)構(gòu)的同時(shí)還要維護(hù)鏈表，在迭代的時(shí)候速度快，其余方面比HashMap要慢。
插入操作隨著Map尺寸的變大，速度會(huì)明顯變慢（除了 IdentityHashMap），但是查找所耗費(fèi)的代價(jià)比插入小很多。對(duì)于插入操作，由于維護(hù)鏈表所帶來的的開銷，導(dǎo)致LinkedHashSet 比 HashSet的代價(jià)高很多。

HashMap的性能因子：

容量：表中的桶位數(shù)。
初始容量：表在創(chuàng)建時(shí)所擁有的桶位數(shù)。
尺寸：表中當(dāng)前存儲(chǔ)的項(xiàng)數(shù)。
負(fù)載因子：尺寸/容量。 空表的負(fù)載因子為 0，半滿表為 0.5。負(fù)載越輕的表產(chǎn)生的沖突性越小，HashMap默認(rèn)負(fù)載因子為 0.75，達(dá)到默認(rèn)值時(shí)，將進(jìn)行散列。

散列碼是一個(gè)無符號(hào)的十六進(jìn)制數(shù)，散列的目的在于使用一個(gè)對(duì)象來查找另一個(gè)對(duì)象；散列的價(jià)值在于能夠快速進(jìn)行查詢。

在Map上的實(shí)現(xiàn)：通過鍵對(duì)象生成一個(gè)數(shù)字，這個(gè)數(shù)字就是散列碼。將散列碼作為數(shù)組的下標(biāo)，該數(shù)組的一個(gè)單元指向一個(gè)鏈表，鏈表上的一個(gè)節(jié)點(diǎn)就是一個(gè) Entry 對(duì)象。數(shù)組的容量是固定的，不同的鍵可以產(chǎn)生相同的下標(biāo)，這將導(dǎo)致 “沖突”。

Example：參考Java編程思想 P493

static final int SIZE = 1024;
LinkedList>[] buckets = new LinkedList[SIZE]; 

public V put(K key, V value) {
    V oldValue = null;
    // 對(duì)散列值取余獲取數(shù)組下標(biāo)
    int index = Math.abs(key.hashCode()) % SIZE;
    if (buckets[index] == null) {
        buckets[index] = new LinkedList>();
    }

    // 獲取下標(biāo)所指向的鏈表
    LinkedList> bucket = buckets[index];
    Entry pair = new Entry<>();
    boolean found = false;

    // 獲取迭代器進(jìn)行迭代，判斷是否存在，存在則覆蓋
    ListIterator> it = bucket.listIterator();
    while (it.hasNext()) {
        Entry iPair = it.next();
        if (iPair.getKey().equals(key)) {
            oldValue = iPair.getValue();
            it.set(pair);
            found = true;
            break;
        }
    }
    // 沒有找到就添加
    if (!found) {
        buckets[index].add(pair);
    }
    return oldValue;
}

equals()

自反性。

對(duì)稱性。

傳遞性。

一致性。

對(duì)任何不是 null的 x， x.equals(null) 一定返回 false。

hashcode()

對(duì)同一個(gè)對(duì)象調(diào)用hashcode() 都應(yīng)該生成同樣的值。

基于對(duì)象的內(nèi)容生成散列碼，讓其富有意義。

散列碼不必獨(dú)一無二，應(yīng)關(guān)注生成速度。

通過 hashCode()和equals()，必須能夠完全確定對(duì)象的身份。

好的 hashCode()應(yīng)該產(chǎn)生分布均勻的散列碼。賦予一個(gè)非零常量值。

public int hashCode() {
    int result = 19;
    return result * field.hashCode();
}