集合

Collection

ArrayList

1. 實現(xiàn)了List接口
2. 底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組
3. 允許存儲null值
4. 線程不安全
5. 可以通過Collections.synchronizedList轉(zhuǎn)換為線程安全的list，就是為各個操作上鎖，通過構(gòu)造函數(shù)可以自定義加鎖對象
6. 插入非尾部數(shù)據(jù)時，會移動對象，導(dǎo)致插入效率低
7. 插入前會檢查數(shù)組大小，當數(shù)組大小不足時會進行擴容操作，擴容時創(chuàng)建一個新的數(shù)組，容量為舊數(shù)組的1.5倍左右newCapacity = oldCapacity + (oldCapacity >> 1)，擴容后舊數(shù)組數(shù)據(jù)被復(fù)制到新數(shù)組

LinkedList

1. 實現(xiàn)了List和Deque接口
2. 底層數(shù)據(jù)結(jié)構(gòu)為鏈表
3. LinkedList既可以當做有序列表，也能當做隊列和棧使用

Queue && Strack

1. Queue是一個接口，Strack是一個類
2. Queue和Strack目前都推薦使用ArrayDeque, 次選LinkedList，Strack已經(jīng)不推薦使用了
3. ArrayDeque基于循環(huán)數(shù)組實現(xiàn)
4. ArrayDeque不能添加null元素

ProrityQueue

1. ProrityQueue實現(xiàn)Queue接口
2. 不允許存儲null
3. 每次返回權(quán)重最小的節(jié)點
4. 權(quán)重計算根據(jù)元素自然順序或構(gòu)造器傳入的比較器計算
5. 底層實現(xiàn)為完全二叉樹（任意一個非葉子節(jié)點的權(quán)值都不大于其左右節(jié)點的權(quán)值）
6. 數(shù)據(jù)存儲使用的數(shù)組，leftNode = parent * 2 + 1，rightNode = parent * 2 + 2，parent = (child - 1) / 2

HashMap && HashSet

1. HashSet僅是對HashMap的一層封裝，內(nèi)部實現(xiàn)基本一致
2. HashMap數(shù)據(jù)結(jié)構(gòu)為Entry，每個Entry包含一個key，一個value
3. HashMap有兩個構(gòu)造參數(shù)，初始容量和負載因子，當存儲的數(shù)據(jù)個數(shù)達到兩者的乘積時觸發(fā)擴容，擴容大小為原來的2倍，擴容后會重新計算key的位置
4. HashMap JDK7底層為數(shù)組+鏈表(沖突鏈表方式)，JDK8為數(shù)組+鏈表+紅黑樹(鏈表長度大于等于8時會轉(zhuǎn)為紅黑樹)
5. HashMap put元素時，如果有Hash沖突，采用頭插法添加新元素
6. HashMap的內(nèi)存是在第一次put操作時分配的

LinkedHashSet && LinkedHashMap

1. LinkedHashSet僅是對LinkedHashMap的一層封裝，內(nèi)部實現(xiàn)基本一致
2. LinkedHashMap是HashMap的直接子類，只是采用雙向鏈表將node連接在了一起，遍歷的時候直接從頭開始
3. LinkedHashMap可用于實現(xiàn)LRU緩存

/**
 * 基于LinkedHashMap實現(xiàn)的LRU
 * @author fan
 */
public class LinkedHashMapCache<K, V> extends LinkedHashMap<K, V> {
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private final int initialCapacity;

    /**
     * 初始化大小
     * @param initialCapacity 初始值大小
     */
    public LinkedHashMapCache(int initialCapacity) {
        // 當參數(shù)accessOrder為true時，即會按照訪問順序排序，最近訪問的放在最前，最早訪問的放在后面
        super(initialCapacity, DEFAULT_LOAD_FACTOR, true);
        this.initialCapacity = initialCapacity;
    }

    /**
     * 是否移除最舊的數(shù)據(jù)
     * @param eldest 最舊的節(jié)點
     * @return 是否移除最舊的節(jié)點
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return this.size() > initialCapacity;
    }
}

TreeSet && TreeMap

1. TreeSet只是對TreeMap的一層封裝
2. TreeMap實現(xiàn)了SortedMap接口，可以按照key的大小順序?qū)ζ渲械脑嘏判?/li>
3. 排序默認按照key的自然順序，也可以在構(gòu)造器中傳入自定義的比較器
4. TreeMap底層實現(xiàn)為紅黑樹