image.png

前言

本文快速回顧了Java中容器的知識點，用作面試復習买猖，事半功倍改橘。

其它知識點復習手冊

• Java基礎知識點面試手冊
• 快速梳理23種常用的設計模式
• Redis基礎知識點面試手冊

概覽

容器主要包括 Collection 和 Map 兩種，Collection 又包含了 List玉控、Set 以及 Queue飞主。

Collection

在這里插入圖片描述

在這里插入圖片描述

數組和集合的區(qū)別:

• 長度
  • 數組的長度固定
  • 集合的長度可變
• 內容
  • 數組存儲的是同一種類型的元素
  • 集合可以存儲不同類型的元素(但是一般我們不這樣干..)
• 元素的數據類型
  • 數組可以存儲基本數據類型,也可以存儲引用類型
  • 集合只能存儲引用類型(若存儲的是簡單的int，它會自動裝箱成Integer)

1. Set（元素不可重復）

• HashSet：基于HashMap實現高诺，支持快速查找碌识，但不支持有序性操作。

• TreeSet：基于紅黑樹實現懒叛，支持有序性操作丸冕，但是查找效率不如 HashSet耽梅，HashSet 查找時間復雜度為 O(1)薛窥，TreeSet 則為 O(logN)；

• LinkedHashSet：具有 HashSet 的查找效率眼姐，且內部使用鏈表維護元素的插入順序诅迷。

2. List（有序(存儲順序和取出順序一致)，可重復）

• ArrayList：基于動態(tài)數組實現众旗，支持隨機訪問罢杉；

• Vector：和 ArrayList 類似，但它是線程安全的贡歧；

• LinkedList：基于雙向鏈表實現滩租，只能順序訪問，但是可以快速地在鏈表中間插入和刪除元素利朵。不僅如此律想，LinkedList 還可以用作棧、隊列和雙向隊列绍弟。

3. Queue

• LinkedList：可以用它來支持雙向隊列技即；

• PriorityQueue：基于堆結構實現，可以用它來實現優(yōu)先隊列樟遣。

Map

在這里插入圖片描述

• HashMap：基于哈希實現而叼；

• HashTable：和 HashMap 類似身笤，但它是線程安全的，這意味著同一時刻多個線程可以同時寫入 HashTable 并且不會導致數據不一致葵陵。它是遺留類液荸，不應該去使用它。

• ConcurrentHashMap：支持線程安全脱篙，并且 ConcurrentHashMap 的效率會更高莹弊，因為 ConcurrentHashMap 引入了分段鎖。

• LinkedHashMap：使用鏈表來維護元素的順序涡尘，順序為插入順序或者最近最少使用（LRU）順序忍弛。

• TreeMap：基于紅黑樹實現。

Fail-Fast 機制和 Fail-Safe 機制

https://blog.csdn.net/Kato_op/article/details/80356618

Fail-Fast

Fail-fast 機制是 java 集合(Collection)中的一種錯誤機制考抄。 當多個線程對同一個集合的內容進行操作時细疚，就可能會產生 fail-fast 事件。

• 迭代器在遍歷時直接訪問集合中的內容,并且在遍歷過程中使用一個modCount變量,

• 集合中在被遍歷期間如果內容發(fā)生變化(增刪改),就會改變modCount的值,

• 每當迭代器使用 hashNext()/next()遍歷下一個元素之前,都會執(zhí)行checkForComodification()方法檢測川梅，modCount變量和expectedmodCount值是否相等,

• 如果相等就返回遍歷,否則拋出異常,終止遍歷.

注意疯兼，如果集合發(fā)生變化時修改modCount值, 剛好有設置為了expectedmodCount值, 則異常不會拋出.(比如刪除了數據,再添加一條數據)

所以，一般來說贫途，存在非同步的并發(fā)修改時吧彪，不可能作出任何堅決的保證。

迭代器的快速失敗行為應該僅用于檢測程序錯誤, 而不是用他來同步丢早。

java.util包下的集合類都是Fail-Fast機制的,不能在多線程下發(fā)生并發(fā)修改(迭代過程中被修改).

Fail-Safe

采用安全失斠搪恪（Fail-Safe）機制的集合容器,在遍歷時不是直接在集合內容上訪問的，而是先copy原有集合內容,在拷貝的集合上進行遍歷怨酝。

原理:

由于迭代時是對原集合的拷貝的值進行遍歷,所以在遍歷過程中對原集合所作的修改并不能被迭代器檢測到,所以不會出發(fā)ConcurrentModificationException

缺點:

迭代器并不能訪問到修改后的內容(簡單來說就是, 迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝,在遍歷期間原集合發(fā)生的修改迭代器是不知道的)

使用場景:

java.util.concurrent包下的容器都是Fail-Safe的,可以在多線程下并發(fā)使用,并發(fā)修改

容器中使用的設計模式

迭代器模式

在這里插入圖片描述

• Iterator它是在ArrayList等集合的內部類的方式實現

Collection 實現了 Iterable 接口傀缩，其中的 iterator() 方法能夠產生一個 Iterator 對象氧急，通過這個對象就可以迭代遍歷 Collection 中的元素狼纬。

從 JDK 1.5 之后可以使用 foreach 方法來遍歷實現了 Iterable 接口的聚合對象昌讲。

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
    System.out.println(item);
}

適配器模式

適配器模式解釋：http://www.reibang.com/p/93821721bf08

java.util.Arrays#asList() 可以把數組類型轉換為 List 類型诗舰。

@SafeVarargs
public static <T> List<T> asList(T... a)

如果要將數組類型轉換為 List 類型俘枫，應該注意的是 asList() 的參數為泛型的變長參數冀膝，因此不能使用基本類型數組作為參數绵患，只能使用相應的包裝類型數組句灌。

Integer[] arr = {1, 2, 3};
List list = Arrays.asList(arr);

也可以使用以下方式生成 List揍堕。

List list = Arrays.asList(1,2,3);

源碼分析

ArrayList

關鍵詞

• 默認大小為 10
• 擴容 1.5 倍料身，加載因子為 0.5
• 基于動態(tài)數組實現
• 刪除元素時不會減少容量，若希望減少容量則調用trimToSize()
• 它不是線程安全的
• 它能存放null值鹤啡。
• 擴容操作需要調用 Arrays.copyOf() 把原數組整個復制到新數組
• 刪除需要調用 System.arraycopy() 將 index+1 后面的元素都復制到 index 位置上惯驼，復制的代價很高。
  -序列化：只序列化數組中有元素填充那部分內容

概覽

在這里插入圖片描述

實現了 RandomAccess 接口，因此支持隨機訪問祟牲。這是理所當然的隙畜，因為 ArrayList 是基于數組實現的。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

擴容

如果不夠時说贝，需要使用 grow() 方法進行擴容议惰，新容量的大小為 oldCapacity + (oldCapacity >> 1)，也就是舊容量的 1.5 倍乡恕。

擴容操作需要調用 Arrays.copyOf() 把原數組整個復制到新數組中

因此最好在創(chuàng)建 ArrayList 對象時就指定大概的容量大小言询，減少擴容操作的次數。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

加入元素：add

add(E e)

首先去檢查一下數組的容量是否足夠

• 足夠：直接添加
• 不足夠：擴容

擴容到原來的1.5倍傲宜，第一次擴容后运杭，如果容量還是小于minCapacity，就將容量擴充為minCapacity函卒。

add(int index, E element)

步驟：

• 檢查角標
• 空間檢查辆憔，如果有需要進行擴容
• 插入元素

刪除元素：remove

步驟：

• 檢查角標
• 刪除元素
• 計算出需要移動的個數，并移動
• 設置為null报嵌，讓GC回收（所以說不是立刻回收虱咧，而是等待GC回收）

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

需要調用 System.arraycopy() 將 index+1 后面的元素都復制到 index 位置上，復制的代價很高锚国。

復制數組：System.arraycopy()

看到arraycopy()腕巡，我們可以發(fā)現：該方法是由C/C++來編寫的

在這里插入圖片描述

Fail-Fast

modCount 用來記錄 ArrayList 結構發(fā)生變化的次數。結構發(fā)生變化是指添加或者刪除至少一個元素的所有操作血筑，或者是調整內部數組的大小绘沉，僅僅只是設置元素的值不算結構發(fā)生變化。

在進行序列化或者迭代等操作時云挟，需要比較操作前后 modCount 是否改變梆砸，如果改變了需要拋出 ConcurrentModificationException转质。

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

構造器

ArrayList 提供了三種方式的構造器：

• public ArrayList()可以構造一個默認初始容量為10的空列表园欣；
• public ArrayList(int initialCapacity)構造一個指定初始容量的空列表；
• public ArrayList(Collection<? extends E> c)構造一個包含指定 collection 的元素的列表休蟹，這些元素按照該collection的迭代器返回它們的順序排列的沸枯。

序列化

補充：transient講解

http://www.importnew.com/21517.html

你只需要實現Serilizable接口，將不需要序列化的屬性前添加關鍵字transient赂弓，序列化對象的時候绑榴，這個屬性就不會序列化到指定的目的地中。

ArrayList 基于數組實現盈魁，并且具有動態(tài)擴容特性翔怎，因此保存元素的數組不一定都會被使用，那么就沒必要全部進行序列化。

保存元素的數組 elementData 使用 transient 修飾赤套，該關鍵字聲明數組默認不會被序列化飘痛。

transient Object[] elementData; // non-private to simplify nested class access

ArrayList 實現了 writeObject() 和 readObject() 來控制只序列化數組中有元素填充那部分內容。

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

序列化時需要使用 ObjectOutputStream 的 writeObject() 將對象轉換為字節(jié)流并輸出容握。而 writeObject() 方法在傳入的對象存在 writeObject() 的時候會去反射調用該對象的 writeObject() 來實現序列化宣脉。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理類似剔氏。

ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);

Vector

關鍵詞

• 默認大小為 10（與Arraylist相同）
• 擴容 2 倍塑猖，加載因子是 1（Arraylist是擴容 1.5 倍，加載因子為 0.5）
• 其它幾乎與ArrayList完全相同谈跛，唯一的區(qū)別在于 Vector 是同步的羊苟，因此開銷就比 ArrayList 要大，訪問速度更慢感憾。
• 使用了 synchronized 進行同步
• Vector是jdk1.2的類了践险，比較老舊的一個集合類。應使用JUC的CopyOnWriteArrayList代替

替代方案

可以使用 Collections.synchronizedList(); 得到一個線程安全的 ArrayList吹菱。

List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);

也可以使用 concurrent 并發(fā)包下的 CopyOnWriteArrayList 類巍虫。

List<String> list = new CopyOnWriteArrayList<>();

CopyOnWriteArrayList

關鍵詞

• 寫操作在一個復制的數組上進行，讀操作還是在原始數組中進行鳍刷，讀寫分離占遥，互不影響。
• 寫操作需要加鎖输瓜，防止并發(fā)寫入時導致寫入數據丟失瓦胎。
• 寫操作結束之后需要把原始數組指向新的復制數組。
• 適用于讀操作遠大于寫操作的場景尤揣。

讀寫分離

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

final void setArray(Object[] a) {
    array = a;
}

@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    return (E) a[index];
}

適用場景

CopyOnWriteArrayList 在寫操作的同時允許讀操作搔啊，大大提高了讀操作的性能，因此很適合讀多寫少的應用場景北戏。

缺陷

• 內存占用：在寫操作時需要復制一個新的數組负芋，使得內存占用為原來的兩倍左右；
• 數據不一致：讀操作不能讀取實時性的數據嗜愈，因為部分寫操作的數據還未同步到讀數組中旧蛾。

所以 CopyOnWriteArrayList 不適合內存敏感以及對實時性要求很高的場景。

LinkedList

關鍵詞

• 雙向鏈表
• 默認大小為 10
• 帶 Head 和 Tail 指針
• Node 存儲節(jié)點信息

概覽

在這里插入圖片描述

基于雙向鏈表實現蠕嫁，內部使用 Node 來存儲鏈表節(jié)點信息锨天。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

每個鏈表存儲了 Head 和 Tail 指針：

transient Node<E> first;
transient Node<E> last;

在這里插入圖片描述

ArrayList 與 LinkedList 比較

• ArrayList 基于動態(tài)數組實現，LinkedList 基于雙向鏈表實現剃毒；
• ArrayList 支持隨機訪問病袄，LinkedList 不支持搂赋；
• LinkedList 在任意位置添加刪除元素更快。

刪除元素：remove

在這里插入圖片描述

獲取元素：get

• 下標小于長度的一半益缠，從頭遍歷
• 反之厂镇，從尾部遍歷

替換元素：set

set方法和get方法其實差不多，根據下標來判斷是從頭遍歷還是從尾遍歷

其他方法

LinkedList實現了Deque接口左刽，因此捺信，我們可以操作LinkedList像操作隊列和棧一樣

LinkedList的方法比ArrayList的方法多太多了，這里我就不一一說明了欠痴。具體可參考：

• https://blog.csdn.net/panweiwei1994/article/details/77110354
• https://zhuanlan.zhihu.com/p/24730576
• https://zhuanlan.zhihu.com/p/28373321

HashMap

http://wiki.jikexueyuan.com/project/java-collection/hashmap.html

源碼分析：https://segmentfault.com/a/1190000014293372

關鍵詞

• 初始容量16
• 擴容是2倍迄靠，加載因子0.75
• 頭插法
• 0桶存放null
• 從 JDK 1.8 開始，一個桶存儲的鏈表長度大于 8 時會將鏈表轉換為紅黑樹（前提：鍵值對要超過64個）
• 自動地將傳入的容量轉換為2的冪次方
  • 保證運算速度：確保用位運算代替模運算來計算桶下標喇辽。hash& (length-1)運算等價于對 length 取模掌挚。
  • hash均勻分布：數據在數組上分布就比較均勻，并且能夠利用全部二進制位菩咨，也就是說碰撞的幾率小吠式，
• table數組+Entry<K,V>[]鏈表（散列表），紅黑樹
• 擴容操作需要把鍵值對重新插入新的 table 中抽米，重新計算所有key有特殊機制（JDK1.8后）

存儲結構

hashMap的一個內部類Node：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next; //鏈表結構特占，存儲下一個元素

在這里插入圖片描述

Node內部包含了一個 Entry 類型的數組table，數組中的每個位置被當成一個桶云茸。

transient Entry[] table;

Entry 存儲著鍵值對是目。它包含了四個字段，從 next 字段我們可以看出 Entry 是一個鏈表标捺。即數組中的每個位置被當成一個桶懊纳，一個桶存放一個鏈表。

HashMap 使用拉鏈法來解決沖突亡容，同一個鏈表中存放哈希值相同的 Entry嗤疯。

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;

    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }

    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }

    public final String toString() {
        return getKey() + "=" + getValue();
    }
}

構造器

在這里插入圖片描述

構造時就會調用tableSizeFor()：返回一個大于輸入參數且最近的2的整數次冪。

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

拉鏈法

應該注意到鏈表的插入是以頭插法方式進行的

HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");

• 新建一個 HashMap闺兢，默認大小為 16茂缚；
• 插入 <K1,V1> 鍵值對，先計算 K1 的 hashCode 為 115列敲，使用除留余數法得到所在的桶下標 115%16=3阱佛。
• 插入 <K2,V2> 鍵值對，先計算 K2 的 hashCode 為 118戴而，使用除留余數法得到所在的桶下標 118%16=6。
• 插入 <K3,V3> 鍵值對翩蘸，先計算 K3 的 hashCode 為 118所意，使用除留余數法得到所在的桶下標 118%16=6，插在 <K2,V2> 前面。

查找需要分成兩步進行：

• 計算鍵值對所在的桶扶踊；
• 在鏈表上順序查找泄鹏，時間復雜度顯然和鏈表的長度成正比。

put 操作

• 當我們 put 的時候秧耗，如果 key 存在了备籽，那么新的 value 會代替舊的 value
• 如果 key 存在的情況下，該方法返回的是舊的 value分井，
• 如果 key 不存在车猬，那么返回 null。

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 鍵為 null 單獨處理
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    // 確定桶下標
    int i = indexFor(hash, table.length);
    // 先找出是否已經存在鍵為 key 的鍵值對尺锚，如果存在的話就更新這個鍵值對的值為 value
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    // 插入新鍵值對
    addEntry(hash, key, value, i);
    return null;
}

HashMap 允許插入鍵為 null 的鍵值對珠闰。但是因為無法調用 null 的 hashCode() 方法，也就無法確定該鍵值對的桶下標瘫辩，只能通過強制指定一個桶下標來存放伏嗜。HashMap 使用第 0 個桶存放鍵為 null 的鍵值對。

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

使用鏈表的頭插法伐厌，也就是新的鍵值對插在鏈表的頭部承绸，而不是鏈表的尾部。

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    // 頭插法挣轨，鏈表頭部指向新的鍵值對
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

補充：hashmap里hash方法的高位優(yōu)化：

https://www.cnblogs.com/liujinhong/p/6576543.html

https://note.youdao.com/yws/res/18743/50AADC7BB42845B29CDA293FC409250C?ynotemdtimestamp=1548155508277

設計者將key的哈希值的高位也做了運算(與高16位做異或運算八酒，使得在做&運算時，此時的低位實際上是高位與低位的結合)刃唐，這就增加了隨機性羞迷，減少了碰撞沖突的可能性！

為何要這么做画饥？

table的長度都是2的冪衔瓮，因此index僅與hash值的低n位有關，hash值的高位都被與操作置為0了抖甘。

這樣做很容易產生碰撞热鞍。設計者權衡了speed, utility, and quality，將高16位與低16位異或來減少這種影響衔彻。設計者考慮到現在的hashCode分布的已經很不錯了薇宠，而且當發(fā)生較大碰撞時也用樹形存儲降低了沖突。僅僅異或一下艰额，既減少了系統(tǒng)的開銷澄港，也不會造成的因為高位沒有參與下標的計算(table長度比較小時)，從而引起的碰撞柄沮。

確定桶下標

很多操作都需要先確定一個鍵值對所在的桶下標回梧。

int hash = hash(key);
int i = indexFor(hash, table.length);

4.1 計算 hash 值

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

4.2 取模

令 x = 1<<\4废岂，即 \x 為 2 的 4 次方，它具有以下性質：

x   : 00010000
x-1 : 00001111

令一個數 y 與 x-1 做與運算狱意，可以去除 y 位級表示的第 4 位以上數：

y       : 10110010
x-1     : 00001111
y&(x-1) : 00000010

這個性質和 y 對 x 取模效果是一樣的：

y   : 10110010
x   : 00010000
y%x : 00000010

我們知道湖苞，位運算的代價比求模運算小的多，因此在進行這種計算時用位運算的話能帶來更高的性能详囤。

確定桶下標的最后一步是將 key 的 hash 值對桶個數取模：hash%capacity财骨，如果能保證 capacity 為 2 的 n 次方，那么就可以將這個操作轉換為位運算藏姐。

static int indexFor(int h, int length) {
    return h & (length-1);
}

當 length 總是 2 的 n 次方時隆箩，h& (length-1)運算等價于對 length 取模，也就是 h%length包各，但是 & 比 % 具有更高的效率摘仅。這看上去很簡單，其實比較有玄機的问畅，我們舉個例子來說明：

• 從上面的例子中可以看出：當它們和 15-1（1110）“與”的時候娃属，8 和 9產生了相同的結果，也就是說它們會定位到數組中的同一個位置上去护姆，這就產生了碰撞矾端，8 和 9 會被放到數組中的同一個位置上形成鏈表，那么查詢的時候就需要遍歷這個鏈 表卵皂，得到8或者9秩铆，這樣就降低了查詢的效率。

• 同時灯变，我們也可以發(fā)現殴玛，當數組長度為 15 的時候，hash 值會與 15-1（1110）進行“與”添祸，那么最后一位永遠是 0滚粟，而 0001，0011刃泌，0101凡壤，1001，1011耙替，0111亚侠，1101 這幾個位置永遠都不能存放元素了，空間浪費相當大俗扇，數組可以使用的位置比數組長度小了很多硝烂，這意味著進一步增加了碰撞的幾率。

• 而當數組長度為16時狐援，即為2的n次方時钢坦，2n-1 得到的二進制數的每個位上的值都為 1究孕，這使得在低位上&時啥酱，得到的和原 hash 的低位相同爹凹，加之 hash(int h)方法對 key 的 hashCode 的進一步優(yōu)化，加入了高位計算镶殷，就使得只有相同的 hash 值的兩個值才會被放到數組中的同一個位置上形成鏈表禾酱。

所以說，當數組長度為 2 的 n 次冪的時候绘趋，不同的 key 算得得 index 相同的幾率較小颤陶，那么數據在數組上分布就比較均勻，也就是說碰撞的幾率小

擴容-基本原理

設 HashMap 的 table 長度為 M陷遮，需要存儲的鍵值對數量為 N滓走，如果哈希函數滿足均勻性的要求，那么每條鏈表的長度大約為 N/M帽馋，因此平均查找次數的復雜度為 O(N/M)搅方。

為了讓查找的成本降低，應該盡可能使得 N/M 盡可能小绽族，因此需要保證 M 盡可能大姨涡，也就是說 table 要盡可能大。HashMap 采用動態(tài)擴容來根據當前的 N 值來調整 M 值吧慢，使得空間效率和時間效率都能得到保證涛漂。

和擴容相關的參數主要有：capacity、size检诗、threshold 和 load_factor匈仗。

static final int DEFAULT_INITIAL_CAPACITY = 16;

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

transient Entry[] table;

transient int size;

int threshold;

final float loadFactor;

transient int modCount;

從下面的添加元素代碼中可以看出，當需要擴容時只搁，令 capacity 為原來的兩倍音比。

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

擴容使用 resize() 實現，需要注意的是氢惋，擴容操作同樣需要把 oldTable 的所有鍵值對重新插入 newTable 中洞翩，因此這一步是很費時的稽犁。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

擴容-重新計算桶下標

Rehash優(yōu)化：https://my.oschina.net/u/3568600/blog/1933764

在進行擴容時，需要把鍵值對重新放到對應的桶上骚亿。HashMap 使用了一個特殊的機制已亥，可以降低重新計算桶下標的操作。

假設原數組長度 capacity 為 16来屠，擴容之后 new capacity 為 32：

capacity     : 00010000
new capacity : 00100000

對于一個 Key虑椎，

• 它的哈希值如果在第 5 位上為 0，那么取模得到的結果和之前一樣俱笛；
• 如果為 1捆姜，那么得到的結果為原來的結果 +16。

總結：

經過rehash之后迎膜，元素的位置要么是在原位置泥技，要么是在原位置再移動2次冪的位置

因此，我們在擴充HashMap的時候磕仅，不需要像JDK1.7的實現那樣重新計算hash珊豹，只需要看看原來的hash值新增的那個bit是1還是0就好了滩褥，是0的話索引沒變浙宜，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴充為32的resize示意圖：

在這里插入圖片描述

計算數組容量

HashMap 構造函數允許用戶傳入的容量不是 2 的 n 次方嵌赠，因為它可以自動地將傳入的容量轉換為 2 的 n 次方卸亮。

先考慮如何求一個數的掩碼忽妒，對于 10010000，它的掩碼為 11111111兼贸，可以使用以下方法得到：

mask |= mask >> 1    11011000
mask |= mask >> 2    11111110
mask |= mask >> 4    11111111

mask+1 是大于原始數字的最小的 2 的 n 次方段直。

num     10010000
mask+1 100000000

以下是 HashMap 中計算數組容量的代碼：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

鏈表轉紅黑樹

并不是桶子上有8位元素的時候它就能變成紅黑樹，它得同時滿足我們的鍵值對大于64才行的

這是為了避免在哈希表建立初期溶诞，多個鍵值對恰好被放入了同一個鏈表中而導致不必要的轉化鸯檬。

HashTable

關鍵詞：

• Hashtable的迭代器不是 fail-fast，HashMap 的迭代器是 fail-fast 迭代器螺垢。
• Hashtable 的 key 和 value 都不允許為 null喧务，HashMap 可以插入鍵為 null 的 Entry。
• HashTable 使用 synchronized 來進行同步枉圃。
• 基于 Dictionary 類（遺留類）
• HashMap 不能保證隨著時間的推移 Map 中的元素次序是不變的功茴。

HashMap 與 HashTable

在這里插入圖片描述

• HashTable 基于 Dictionary 類（遺留類），而 HashMap 是基于 AbstractMap孽亲。
  • Dictionary 是任何可將鍵映射到相應值的類的抽象父類坎穿，
  • 而AbstractMap是基于Map接口的實現，它以最大限度地減少實現此接口所需的工作。
• HashMap 的 key 和 value 都允許為 null玲昧，而 Hashtable 的 key 和 value 都不允許為 null
• HashMap 的迭代器是 fail-fast 迭代器栖茉，而 Hashtable 的 enumerator 迭代器不是 fail-fast 的。
• 由于 Hashtable 是線程安全的也是 synchronized孵延，所以在單線程環(huán)境下它比 HashMap 要慢吕漂。
• Hashtable 中的幾乎所有的 public 的方法都是synchronized的，而有些方法也是在內部通過 synchronized 代碼塊來實現隙袁。
  • 但是在 Collections 類中存在一個靜態(tài)方法：synchronizedMap()痰娱，該方法創(chuàng)建了一個線程安全的 Map 對象弃榨，并把它作為一個封裝的對象來返回菩收。
  • 也可以使用 ConcurrentHashMap，它是 HashTable 的替代鲸睛，而且比 HashTable 可擴展性更好

ConcurrentHashMap

談談ConcurrentHashMap1.7和1.8的不同實現：

http://www.importnew.com/23610.html

詳細源碼分析（還未細看）：

https://blog.csdn.net/yan_wenliang/article/details/51029372

https://segmentfault.com/a/1190000014380257

主要針對jdk1.7的實現來介紹

關鍵詞

• key和value都不允許為null
• Hashtable是將所有的方法進行同步娜饵，效率低下。而ConcurrentHashMap通過部分鎖定+CAS算法來進行實現線程安全的
• get方法是非阻塞官辈，無鎖的箱舞。重寫Node類，通過volatile修飾next來實現每次獲取都是最新設置的值
• 在高并發(fā)環(huán)境下拳亿，統(tǒng)計數據(計算size...等等)其實是無意義的晴股，因為在下一時刻size值就變化了。
• 實現形式不同：
  • 1.7：Segment + HashEntry的方式進行實現
  • 1.8：與HashMap相同（散列表（數組+鏈表）+紅黑樹）采用Node數組 + CAS + Synchronized來保證并發(fā)安全進行實現

存儲結構

jdk1.7

jdk1.7中采用Segment + HashEntry的方式進行實現

在這里插入圖片描述

Segment：其繼承于 ReentrantLock 類肺魁，從而使得 Segment 對象可以充當鎖的角色电湘。

Segment 中包含HashBucket的數組，其可以守護其包含的若干個桶鹅经。

static final class HashEntry<K,V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K,V> next;
}

ConcurrentHashMap采用了分段鎖寂呛，每個分段鎖維護著幾個桶，多個線程可以同時訪問不同分段鎖上的桶瘾晃，從而使其并發(fā)度更高（并發(fā)度就是 Segment 的個數）贷痪。

jdk1.8

在這里插入圖片描述

• JDK 1.7 使用分段鎖機制來實現并發(fā)更新操作，核心類為 Segment蹦误，它繼承自重入鎖 ReentrantLock劫拢，并發(fā)程度與 Segment 數量相等。

• JDK 1.8 使用了 CAS 操作來支持更高的并發(fā)度强胰，在 CAS 操作失敗時使用內置鎖 synchronized舱沧。

• 并且 JDK 1.8 的實現也在鏈表過長時會轉換為紅黑樹。

1.8中放棄了Segment臃腫的設計哪廓，取而代之的是采用Node數組 + CAS + Synchronized來保證并發(fā)安全進行實現

添加元素：put

在這里插入圖片描述

只讓一個線程對散列表進行初始化狗唉！

獲取元素：get

從頂部注釋我們可以讀到，get方法是不用加鎖的涡真，是非阻塞的分俯。

Node節(jié)點是重寫的肾筐，設置了volatile關鍵字修飾，致使它每次獲取的都是最新設置的值

獲取大懈准簟：size

每個 Segment 維護了一個 count 變量來統(tǒng)計該 Segment 中的鍵值對個數吗铐。

在執(zhí)行 size 操作時，需要遍歷所有 Segment 然后把 count 累計起來杏节。

ConcurrentHashMap 在執(zhí)行 size操作時先嘗試不加鎖唬渗，如果連續(xù)兩次不加鎖操作得到的結果一致，那么可以認為這個結果是正確的奋渔。

嘗試次數使用 RETRIES_BEFORE_LOCK 定義镊逝，該值為 2，retries 初始值為 -1嫉鲸，因此嘗試次數為 3撑蒜。

如果嘗試的次數超過 3 次，就需要對每個 Segment 加鎖玄渗。

刪除元素：remove

在這里插入圖片描述

為什么用這么方式刪除呢座菠，細心的同學會發(fā)現上面定義的HashEntry的key和next都是final類型的，所以不能改變next的指向藤树，所以又復制了一份指向刪除的結點的next浴滴。

Collections.synchronizedMap()與ConcurrentHashMap的區(qū)別

參考：https://blog.csdn.net/lanxiangru/article/details/53495854

• Collections.synchronizedMap()和Hashtable一樣，實現上在調用map所有方法時岁钓，都對整個map進行同步升略，而ConcurrentHashMap的實現卻更加精細，它對map中的所有桶加了鎖甜紫，同步操作精確控制到桶降宅，所以，即使在遍歷map時囚霸，其他線程試圖對map進行數據修改腰根，也不會拋出ConcurrentModificationException。
• ConcurrentHashMap從類的命名就能看出拓型，它是個HashMap额嘿。而Collections.synchronizedMap()可以接收任意Map實例，實現Map的同步劣挫。比如TreeMap册养。

總結

ConcurrentHashMap 的高并發(fā)性主要來自于三個方面：

• 用分離鎖實現多個線程間的更深層次的共享訪問。
• 用 HashEntery對象的不變性來降低執(zhí)行讀操作的線程在遍歷鏈表期間對加鎖的需求压固。
• 通過對同一個 Volatile 變量的寫 / 讀訪問球拦，協調不同線程間讀 / 寫操作的內存可見性。

LinkedHashMap

http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html

https://segmentfault.com/a/1190000014319445

關鍵詞

• 允許使用 null 值和 null 鍵
• 此實現不是同步的（linkedlist，lilnkedhashset也不是同步的）
• 維護著一個運行于所有條目的雙向鏈表坎炼。定義了迭代順序愧膀，該迭代順序可以是插入順序或者是訪問順序。
• 初始容量對遍歷沒有影響：遍歷的雙向鏈表谣光，而不是散列表
• 在訪問順序的情況下檩淋，使用get方法也是結構性的修改（會導致Fail-Fast）

概論

在這里插入圖片描述

在這里插入圖片描述

成員變量

該 Entry 除了保存當前對象的引用外，還保存了其上一個元素 before 和下一個元素 after的引用萄金，從而在哈希表的基礎上又構成了雙向鏈接列表蟀悦。

/**
* LinkedHashMap的Entry元素。
* 繼承HashMap的Entry元素氧敢，又保存了其上一個元素before和下一個元素after的引用日戈。
 */
static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

構造器

在這里插入圖片描述

• 通過源代碼可以看出，在 LinkedHashMap 的構造方法中福稳，實際調用了父類 HashMap 的相關構造方法來構造一個底層存放的 table 數組涎拉，但額外可以增加 accessOrder 這個參數，如果不設置

  • 默認為 false的圆，代表按照插入順序進行迭代；
  • 當然可以顯式設置為 true半火，代表以訪問順序進行迭代越妈。

• 在構建新節(jié)點時，構建的是LinkedHashMap.Entry 不再是Node.

獲取元素：get

LinkedHashMap 重寫了父類 HashMap 的 get 方法钮糖，實際在調用父類 getEntry() 方法取得查找的元素后梅掠，再判斷當排序模式 accessOrder 為 true 時，記錄訪問順序店归，將最新訪問的元素添加到雙向鏈表的表頭阎抒，并從原來的位置刪除。

由于的鏈表的增加消痛、刪除操作是常量級的且叁，故并不會帶來性能的損失。

遍歷元素

為啥注釋說：初始容量對遍歷沒有影響秩伞？

因為它遍歷的是LinkedHashMap內部維護的一個雙向鏈表逞带，而不是散列表(當然了，鏈表雙向鏈表的元素都來源于散列表)

LinkedHashMap應用

http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap-lrucache.html

LRU最近最少使用（訪問順序）

用這個類有兩大好處：

• 它本身已經實現了按照訪問順序或插入順序的存儲
• LinkedHashMap 本身有removeEldestEntry方法用于判斷是否需要移除最不常讀取的數纱新，但是展氓，原始方法默認不需要移除，我們需要override這樣一個方法脸爱。

Java里面實現LRU緩存通常有兩種選擇：

• 使用LinkedHashMap
• 自己設計數據結構遇汞，使用鏈表+HashMap

以下是使用 LinkedHashMap 實現的一個 LRU 緩存：

• 設定最大緩存空間 MAX_ENTRIES 為 3；
• 使用 LinkedHashMap 的構造函數將 accessOrder 設置為 true，開啟 LRU 順序空入；
• 覆蓋 removeEldestEntry() 方法實現教寂，在節(jié)點多于 MAX_ENTRIES 就會將最近最久未使用的數據移除。

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final int MAX_ENTRIES = 3;

    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

    LRUCache() {
        super(MAX_ENTRIES, 0.75f, true);
    }
}

public static void main(String[] args) {
    LRUCache<Integer, String> cache = new LRUCache<>();
    cache.put(1, "a");
    cache.put(2, "b");
    cache.put(3, "c");
    cache.get(1);
    cache.put(4, "d");
    System.out.println(cache.keySet());
}

[3, 1, 4]

實現詳細代碼請參考文章：補充知識點-緩存

FIFO（插入順序）

還可以在插入順序的LinkedHashMap直接重寫下removeEldestEntry方法即可輕松實現一個FIFO緩存

TreeMap

關鍵詞

• 紅黑樹
• 非同步
• key不能為null
• 實現了NavigableMap接口执庐，而NavigableMap接口繼承著SortedMap接口酪耕，是有序的（HahMap是Key無序的）
• TreeMap的基本操作 containsKey、get轨淌、put 和 remove 的時間復雜度是 log(n) 迂烁。
• 適用于查找性能要求不那么高，反而對有序性要求比較高的應用場景
• 使用Comparator或者Comparable來比較key是否相等與排序的問題

概覽

在這里插入圖片描述

獲取元素：get

詳細看：

https://segmentfault.com/a/1190000014345983#articleHeader4

總結：

• 如果在構造方法中傳遞了Comparator對象递鹉，那么就會以Comparator對象的方法進行比較盟步。否則，則使用Comparable的compareTo(T o)方法來比較躏结。
• 值得說明的是：如果使用的是compareTo(T o)方法來比較却盘，key一定是不能為null，并且得實現了Comparable接口的媳拴。
• 即使是傳入了Comparator對象黄橘，不用compareTo(T o)方法來比較，key也是不能為null的

刪除元素：remove

刪除節(jié)點并且平衡紅黑樹

HashSet

http://wiki.jikexueyuan.com/project/java-collection/hashset.html

https://segmentfault.com/a/1190000014391402

關鍵詞：

• 默認容量16屈溉，擴容兩倍塞关，加載因子0.75

• 允許元素為null

• 實現Set接口

• 不保證迭代順序

• 非同步

• 初始容量非常影響迭代性能

• 底層實際上是一個HashMap實例

  public HashSet() {map = new HashMap<>();}

如果添加的是在 HashSet 中不存在的，則返回 true子巾；如果添加的元素已經存在帆赢，返回 false。

對于 HashSet 中保存的對象线梗，請注意正確重寫其 equals 和 hashCode 方法椰于，以保證放入的對象的唯一性。

HashSet 和 HashMap 的區(qū)別

重要：

1. HashMap中使用鍵對象來計算hashcode值

2. HashSet使用成員對象來計算hashcode值仪搔，對于兩個對象來說hashcode可能相同瘾婿，所以equals()方法用來判斷對象的相等性，如果兩個對象不同的話僻造，那么返回false

在這里插入圖片描述

TreeSet

關鍵詞

• 實現NavigableSet接口
• 可以實現排序功能
• 底層實際上是一個TreeMap實例
• 非同步
• 不允許為null

LinkedHashSet

關鍵詞

• 迭代是有序的
• 允許為null
• 底層實際上是一個HashMap+雙向鏈表實例(其實就是LinkedHashMap)
• 非同步
• 性能比HashSet差一丟丟憋他，因為要維護一個雙向鏈表
• 初始容量與迭代無關（與LinkedHashMap相同），因為LinkedHashSet迭代的是雙向鏈表

總結Set

HashSet：

• 無序髓削，允許為null竹挡，底層是HashMap(散列表+紅黑樹)，非線程同步

TreeSet：

• 有序立膛，不允許為null揪罕，底層是TreeMap(紅黑樹),非線程同步

LinkedHashSet：

• 迭代有序梯码，允許為null，底層是HashMap+雙向鏈表好啰，非線程同步

WeekHashMap

存儲結構

WeakHashMap 的 Entry 繼承自 WeakReference轩娶，被 WeakReference 關聯的對象在下一次垃圾回收時會被回收。

WeakHashMap 主要用來實現緩存框往，通過使用 WeakHashMap 來引用緩存對象鳄抒，由 JVM 對這部分緩存進行回收。

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V>

ConcurrentCache

Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 來實現緩存功能椰弊。

ConcurrentCache 采取的是分代緩存：

• 經常使用的對象放入 eden 中许溅，eden 使用 ConcurrentHashMap 實現，不用擔心會被回收（伊甸園）秉版；
• 不常用的對象放入 longterm贤重，longterm 使用 WeakHashMap 實現，這些老對象會被垃圾收集器回收清焕。
• 當調用 get() 方法時并蝗，會先從 eden 區(qū)獲取，如果沒有找到的話再到 longterm 獲取秸妥，當從 longterm 獲取到就把對象放入 eden 中滚停，從而保證經常被訪問的節(jié)點不容易被回收。
• 當調用 put() 方法時筛峭，如果 eden 的大小超過了 size铐刘，那么就將 eden 中的所有對象都放入 longterm 中，利用虛擬機回收掉一部分不經常使用的對象影晓。

public final class ConcurrentCache<K, V> {

    private final int size;

    private final Map<K, V> eden;

    private final Map<K, V> longterm;

    public ConcurrentCache(int size) {
        this.size = size;
        this.eden = new ConcurrentHashMap<>(size);
        this.longterm = new WeakHashMap<>(size);
    }

    public V get(K k) {
        V v = this.eden.get(k);
        if (v == null) {
            v = this.longterm.get(k);
            if (v != null)
                this.eden.put(k, v);
        }
        return v;
    }

    public void put(K k, V v) {
        if (this.eden.size() >= size) {
            this.longterm.putAll(this.eden);
            this.eden.clear();
        }
        this.eden.put(k, v);
    }
}

常見問題總結

Enumeration和Iterator接口的區(qū)別

Iterator替代了Enumeration，Enumeration是一個舊的迭代器了檩禾。

與Enumeration相比挂签，Iterator更加安全，因為當一個集合正在被遍歷的時候盼产，它會阻止其它線程去修改集合饵婆。

區(qū)別有三點：

• Iterator的方法名比Enumeration更科學
• Iterator有fail-fast機制，比Enumeration更安全
• Iterator能夠刪除元素戏售，Enumeration并不能刪除元素

ListIterator有什么特點

• ListIterator繼承了Iterator接口侨核，它用于遍歷List集合的元素。
• ListIterator可以實現雙向遍歷,添加元素灌灾，設置元素

在這里插入圖片描述

與Java集合框架相關的有哪些最好的實踐

如果是單列的集合搓译，我們考慮用Collection下的子接口ArrayList和Set。

如果是映射锋喜，我們就考慮使用Map

• 是否需要同步：去找線程安全的集合類使用

• 迭代時是否需要有序(插入順序有序)：去找Linked雙向列表結構的

• 是否需要排序(自然順序或者手動排序)：去找Tree紅黑樹類型的(JDK1.8)

• 估算存放集合的數據量有多大些己，無論是List還是Map豌鸡，它們實現動態(tài)增長，都是有性能消耗的段标。在初始集合的時候給出一個合理的容量會減少動態(tài)增長時的消耗

• 使用泛型涯冠，避免在運行時出現ClassCastException

• 盡可能使用Collections工具類，或者獲取只讀逼庞、同步或空的集合蛇更，而非編寫自己的實現。它將會提供代碼重用性赛糟，它有著更好的穩(wěn)定性和可維護性

參考

• https://github.com/CyC2018/CS-Notes/blob/master/docs/notes/Java%20%E5%AE%B9%E5%99%A8.md
• Eckel B. Java 編程思想 [M]. 機械工業(yè)出版社, 2002.
• Java Collection Framework
• Iterator 模式
• Java 8 系列之重新認識 HashMap
• What is difference between HashMap and Hashtable in Java?
• Java 集合之 HashMap
• The principle of ConcurrentHashMap analysis
• 探索 ConcurrentHashMap 高并發(fā)性的實現機制
• HashMap 相關面試題及其解答
• Java 集合細節(jié)（二）：asList 的缺陷
• Java Collection Framework – The LinkedList Class

關注我

本人目前為后臺開發(fā)工程師派任，主要關注Python爬蟲，后臺開發(fā)等相關技術虑灰。

原創(chuàng)博客主要內容：

• 筆試面試復習知識點手冊
• Leetcode算法題解析（前150題）
• 劍指offer算法題解析
• Python爬蟲相關實戰(zhàn)
• 后臺開發(fā)相關實戰(zhàn)

同步更新以下幾大博客：

• Csdn：

  http://blog.csdn.net/qqxx6661

  擁有專欄：Leetcode題解（Java/Python）吨瞎、Python爬蟲開發(fā)

• 知乎：

  https://www.zhihu.com/people/yang-zhen-dong-1/

  擁有專欄：碼農面試助攻手冊

• 掘金：

  https://juejin.im/user/5b48015ce51d45191462ba55

• 簡書：

  http://www.reibang.com/u/b5f225ca2376

• 個人公眾號：Rude3Knife

  在這里插入圖片描述