摘要：將散列碼作為數組的下標，該數組的一個單元指向一個鏈表，鏈表上的一個節點就是一個對象。散列碼不必獨一無二，應關注生成速度。好的應該產生分布均勻的散列碼。

數組是一種效率最高的存儲和隨機訪問對象引用的一個簡單的線性序列，雖然訪問快速，但為之付出的代價是數組的大小固定，并且在其生命周期中不可改變。數組與其他容器之間的區別在于：效率、類型和保存基本類型的能力。但隨著自動包裝機制的出現，容器已經可以與數組幾乎一樣方便，而數組僅存的優點就是效率。

應該 “優先選擇容器而不是數組”，只有在已經證明性能稱為問題（并且切換到數組對性能提高有所幫助）時，你才應該將程序重構為使用數組

數組標識符就是一個引用，用以保存指向其他對象的引用，數組的一個單元指向在堆中創建的一個真實對象。對像數組與基本類型數組的區別在于，對象保存的是引用，基本類型數組保存的是基本類型的值。

數組的 length屬性，表示數組的大小，而不是實際保存的元素個數。新生成的對象數組，會被默認的初始化為 null，基本類型數組則會初始化為對應基本類型的默認值，對于對象數組，可以檢測其中的引用是否為 null，進而確定某個位置是否存在對象。當數組不被需要時，垃圾回收器會負責清理數組，否則將一直存在。

System.arraycopy()：復制一個數組比用 for 循環復制要快得多，且該方法對所有類型做了重載。當復制對象數組時，只是復制對象的引用（屬淺拷貝）。

Arrays.asList(T... a)：將多個元素轉換成 List 列表，底層表示的還是數組，當嘗試進行 add()、delete()操作時將在運行時報錯。

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

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

comparator用于指定元素的排列順序，在常見的數據類型中已經被默認實現，對于需要按照某種規則進行排序的時候，提供Comparator或者實現 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;
    }
    
}

一個獨立元素的序列，這些元素都服從一條或多條規則，提供了存放一組對象的方式。List必須按照插入的順序保存元素，而Set不能有重復元素。Queue按照隊列排隊規則來確定對象產生的順序。

PriorityQueue：優先級隊列，聲明下一個彈出最需要的元素（具有最高的優先級），通過默認排序或提供 Comparator。當調用 peek()、poll()、remove()方法時，獲取的元素是隊列中優先級最高的。

ListIterator：Iterator的子類，只用于對各種 List 類的訪問，可以實現雙向移動。hasNext() / next()、hasPrevious() / previous()

對于隨機訪問的 get/set操作，背后有數組支持的 List 比 ArrayList 稍快一點，但是對于 LinkedList，將會變得很慢，因為它不是針對隨機訪問操作而設計的。
最佳的做法是將 ArrayList 作為默認首選，當因為經常插入和刪除操作而性能下降時，才去選擇 LinkedList。如果使用的是固定數量的元素，既可以選擇List，也可以選擇數組。

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

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

使用Map時，首選HashMap，TreeMap維護著散列數據結構的同時還要維護鏈表，在迭代的時候速度快，其余方面比HashMap要慢。
插入操作隨著Map尺寸的變大，速度會明顯變慢（除了 IdentityHashMap），但是查找所耗費的代價比插入小很多。對于插入操作，由于維護鏈表所帶來的的開銷，導致LinkedHashSet 比 HashSet的代價高很多。

HashMap的性能因子：

容量：表中的桶位數。
初始容量：表在創建時所擁有的桶位數。
尺寸：表中當前存儲的項數。
負載因子：尺寸/容量。 空表的負載因子為 0，半滿表為 0.5。負載越輕的表產生的沖突性越小，HashMap默認負載因子為 0.75，達到默認值時，將進行散列。

散列碼是一個無符號的十六進制數，散列的目的在于使用一個對象來查找另一個對象；散列的價值在于能夠快速進行查詢。

在Map上的實現：通過鍵對象生成一個數字，這個數字就是散列碼。將散列碼作為數組的下標，該數組的一個單元指向一個鏈表，鏈表上的一個節點就是一個 Entry 對象。數組的容量是固定的，不同的鍵可以產生相同的下標，這將導致 “沖突”。

Example：參考Java編程思想 P493

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

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

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

    // 獲取迭代器進行迭代，判斷是否存在，存在則覆蓋
    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()

自反性。

對稱性。

傳遞性。

一致性。

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

hashcode()

對同一個對象調用hashcode() 都應該生成同樣的值。

基于對象的內容生成散列碼，讓其富有意義。

散列碼不必獨一無二，應關注生成速度。

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

好的 hashCode()應該產生分布均勻的散列碼。賦予一個非零常量值。

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