本篇文章帶你從Java源碼深入解析關(guān)于Java容器的概念传藏。

參考文獻(xiàn)：

1. Java容器相關(guān)知識(shí)全面總結(jié)

2. Java官方API文檔

1 常用容器繼承關(guān)系圖

先上一張網(wǎng)上的繼承關(guān)系圖

集合繼承關(guān)系圖

個(gè)人覺得有些地方不是很準(zhǔn)確腻暮，比如Iterator不是容器，只是一個(gè)操作遍歷集合的方法接口毯侦，所以不應(yīng)該放在里面哭靖。并且Map不應(yīng)該繼承自Collection。所以自己整理了一個(gè)常用繼承關(guān)系圖如下

New集合繼承關(guān)系圖

如上圖所示侈离，接下去會(huì)自頂向下解釋重要的接口和實(shí)現(xiàn)類款青。

2 Collection和Map

在Java容器中一共定義了2種集合, 頂層接口分別是Collection和Map。但是這2個(gè)接口都不能直接被實(shí)現(xiàn)使用霍狰，分別代表兩種不同類型的容器抡草。

簡單來看，Collection代表的是單個(gè)元素對(duì)象的序列蔗坯，（可以有序/無序康震，可重復(fù)/不可重復(fù) 等，具體依據(jù)具體的子接口Set宾濒，List腿短，Queue等）；Map代表的是“鍵值對(duì)”對(duì)象的集合（同樣可以有序/無序 等依據(jù)具體實(shí)現(xiàn)）

2.1 Collection

根據(jù)Java官方文檔對(duì)Collection的解釋

The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered. The JDK does not provide any direct implementations of this interface: it provides implementations of more specific subinterfaces like Set and List. This interface is typically used to pass collections around and manipulate them where maximum generality is desired.

大概意思就是

是容器繼承關(guān)系中的頂層接口绘梦。是一組對(duì)象元素組橘忱。有些容器允許重復(fù)元素有的不允許，有些有序有些無序卸奉。 JDK不直接提供對(duì)于這個(gè)接口的實(shí)現(xiàn)钝诚，但是提供繼承與該接口的子接口比如 List Set。這個(gè)接口的設(shè)計(jì)目的是希望能最大程度抽象出元素的操作榄棵。

接口定義：

public interface Collection<E> extends Iterable<E> {

    ...
    
}

泛型<E>即該Collection中元素對(duì)象的類型凝颇，繼承的Iterable是定義的一個(gè)遍歷操作接口潘拱，采用hasNext next的方式進(jìn)行遍歷。具體實(shí)現(xiàn)還是放在具體類中去實(shí)現(xiàn)拧略。

我們可以看下定義的幾個(gè)重要的接口方法

add(E e) 
 Ensures that this collection contains the specified element
 
clear()
 Removes all of the elements from this collection (optional operation).
 
contains(Object o)
 Returns true if this collection contains the specified element.
 
isEmpty()
 Returns true if this collection contains no elements.
 
iterator()
 Returns an iterator over the elements in this collection.
 
remove(Object o)
 Removes a single instance of the specified element from this collection, if it is present (optional operation).
 
retainAll(Collection<?> c)
 Retains only the elements in this collection that are contained in the specified collection (optional operation).（**ps:這個(gè)平時(shí)倒是沒注意芦岂，感覺挺好用的接口，保留指定的集合**）
 
size()
 Returns the number of elements in this collection.
 
toArray()
 Returns an array containing all of the elements in this collection.
 
toArray(T[] a)
 Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.（**ps:這個(gè)接口也可以mark下**）
 
 ...

上面定義的接口就代表了Collection這一類容器最基本的操作垫蛆，包括了插入禽最，移除，查詢等袱饭，會(huì)發(fā)現(xiàn)都是對(duì)單個(gè)元素的操作川无，Collection這類集合即元素對(duì)象的存儲(chǔ)。其中有2個(gè)接口平時(shí)沒用過但是覺得很有用

1. retainAll(Collection<?> c) 保留指定的集合
2. toArray(T[] a) 可以轉(zhuǎn)為數(shù)組

2.2 Map

Java官方文檔對(duì)Map的解釋

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

This interface takes the place of the Dictionary class, which was a totally abstract class rather than an interface.

The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map's collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

大概意思就是

一個(gè)保存鍵值映射的對(duì)象宁赤。 映射Map中不能包含重復(fù)的key舀透，每一個(gè)key最多對(duì)應(yīng)一個(gè)value。

這個(gè)接口替代了原來的一個(gè)抽象類Dictionary决左。

Map集合提供3種遍歷訪問方法愕够，1.獲得所有key的集合然后通過key訪問value赂蕴。2.獲得value的集合枚赡。3.獲得key-value鍵值對(duì)的集合（key-value鍵值對(duì)其實(shí)是一個(gè)對(duì)象，里面分別有key和value）淹遵。 Map的訪問順序取決于Map的遍歷訪問方法的遍歷順序继找。 有的Map遂跟，比如TreeMap可以保證訪問順序，但是有的比如HashMap婴渡，無法保證訪問順序幻锁。

接口定義如下：

public interface Map<K,V> {

    ...
    
    interface Entry<K,V> {
        K getKey();
        V getValue();
        ...
    } 
}

泛型<K,V>分別代表key和value的類型。這時(shí)候注意到還定義了一個(gè)內(nèi)部接口Entry边臼，其實(shí)每一個(gè)鍵值對(duì)都是一個(gè)Entry的實(shí)例關(guān)系對(duì)象哄尔，所以Map實(shí)際其實(shí)就是Entry的一個(gè)Collection，然后Entry里面包含key柠并，value岭接。再設(shè)定key不重復(fù)的規(guī)則，自然就演化成了Map臼予。（個(gè)人理解）

下面介紹下定義的3個(gè)遍歷Map的方法鸣戴。

1. Set<K> keySet()

會(huì)返回所有key的Set集合，因?yàn)閗ey不可以重復(fù)粘拾，所以返回的是Set格式窄锅，而不是List格式。（之后會(huì)說明Set半哟，List區(qū)別酬滤。這里先告訴一點(diǎn)Set集合內(nèi)元素是不可以重復(fù)的签餐，而List內(nèi)是可以重復(fù)的） 獲取到所有key的Set集合后寓涨，由于Set是Collection類型的盯串，所以可以通過Iterator去遍歷所有的key，然后再通過get方法獲取value戒良。如下

Map<String,String> map = new HashMap<String,String>();
map.put("01", "zhangsan");
map.put("02", "lisi");
map.put("03", "wangwu");

Set<String> keySet = map.keySet();//先獲取map集合的所有鍵的Set集合
Iterator<String> it = keySet.iterator();//有了Set集合体捏，就可以獲取其迭代器。

while(it.hasNext()) {
       String key = it.next();
       String value = map.get(key);//有了鍵可以通過map集合的get方法獲取其對(duì)應(yīng)的值糯崎。
       System.out.println("key: "+key+"-->value: "+value);//獲得key和value值
}

2. Collection<V> values()

直接獲取values的集合几缭，無法再獲取到key。所以如果只需要value的場景可以用這個(gè)方法沃呢。獲取到后使用Iterator去遍歷所有的value年栓。如下

Map<String,String> map = new HashMap<String,String>();
map.put("01", "zhangsan");
map.put("02", "lisi");
map.put("03", "wangwu");

Collection<String> collection = map.values();//返回值是個(gè)值的Collection集合
System.out.println(collection);

3. Set< Map.Entry< K, V>> entrySet()

是將整個(gè)Entry對(duì)象作為元素返回所有的數(shù)據(jù)。然后遍歷Entry薄霜，分別再通過getKey和getValue獲取key和value某抓。如下

Map<String,String> map = new HashMap<String,String>();
map.put("01", "zhangsan");
map.put("02", "lisi");
map.put("03", "wangwu");

//通過entrySet()方法將map集合中的映射關(guān)系取出（這個(gè)關(guān)系就是Map.Entry類型）
Set<Map.Entry<String, String>> entrySet = map.entrySet();
//將關(guān)系集合entrySet進(jìn)行迭代，存放到迭代器中                
Iterator<Map.Entry<String, String>> it = entrySet.iterator();

while(it.hasNext()) {
       Map.Entry<String, String> me = it.next();//獲取Map.Entry關(guān)系對(duì)象me
       String key = me.getKey();//通過關(guān)系對(duì)象獲取key
       String value = me.getValue();//通過關(guān)系對(duì)象獲取value
}

通過以上3種遍歷方式我們可以知道惰瓜，如果你只想獲取key否副，建議使用keySet。如果只想獲取value崎坊，建議使用values备禀。如果key value希望遍歷，建議使用entrySet奈揍。（雖然通過keySet可以獲得key再間接獲得value曲尸，但是效率沒entrySet高，不建議使用這種方法）

3 List男翰、Set和Queue

在Collection這個(gè)集成鏈中另患，我們介紹List、Set和Queue奏篙。其中會(huì)重點(diǎn)介紹List和Set以及幾個(gè)常用實(shí)現(xiàn)class柴淘。Queue平時(shí)實(shí)在沒用過。

先簡單概述下List和Set秘通。他們2個(gè)是繼承Collection的子接口为严，就是說他們也都是負(fù)責(zé)存儲(chǔ)單個(gè)元素的容器。但是最大的區(qū)別如下

1. List是存儲(chǔ)的元素容器是有個(gè)有序的可以索引到元素的容器肺稀，并且里面的元素可以重復(fù)第股。
2. Set里面和List最大的區(qū)別是Set里面的元素對(duì)象不可重復(fù)。

3.1 List

Java文檔中介紹

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.

...

The List interface provides a special iterator, called a ListIterator, that allows element insertion and replacement, and bidirectional access in addition to the normal operations that the Iterator interface provides. A method is provided to obtain a list iterator that starts at a specified position in the list.

大概意思是

一個(gè)有序的Collection（或者叫做序列）话原。使用這個(gè)接口可以精確掌控元素的插入夕吻，還可以根據(jù)index獲取相應(yīng)位置的元素诲锹。

不像Set，list允許重復(fù)元素的插入涉馅。有人希望自己實(shí)現(xiàn)一個(gè)list归园，禁止重復(fù)元素，并且在重復(fù)元素插入的時(shí)候拋出異常稚矿，但是我們不建議這么做庸诱。

...

List提供了一種特殊的iterator遍歷器，叫做ListIterator晤揣。這種遍歷器允許遍歷時(shí)插入桥爽，替換，刪除昧识，雙向訪問钠四。 并且還有一個(gè)重載方法允許從一個(gè)指定位置開始遍歷。

然后我們?cè)倏聪翷ist接口新增的接口跪楞，會(huì)發(fā)現(xiàn)add缀去，get這些都多了index參數(shù)，說明在原來Collection的基礎(chǔ)上习霹，List是一個(gè)可以指定索引朵耕，有序的容器。在這注意以下添加的2個(gè)新Iteractor方法淋叶。

ListIterator<E> listIterator();

ListIterator<E> listIterator(int index);

我們?cè)倏碙istIterator的代碼

public interface ListIterator<E> extends Iterator<E> {
    // Query Operations
    
    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();

    int previousIndex();

    void remove();

    void set(E e);

    void add(E e);
}

一個(gè)集合在遍歷過程中進(jìn)行插入刪除操作很容易造成錯(cuò)誤阎曹，特別是無序隊(duì)列，是無法在遍歷過程中進(jìn)行這些操作的煞檩。但是List是一個(gè)有序集合处嫌，所以在這實(shí)現(xiàn)了一個(gè)ListIteractor，可以在遍歷過程中進(jìn)行元素操作斟湃，并且可以雙向訪問熏迹。

這個(gè)是之前開發(fā)中一直沒有發(fā)現(xiàn)的，好東西凝赛。mark

以上就是List的基本概念和規(guī)則注暗，下面我們介紹2個(gè)常用List的實(shí)現(xiàn)類，ArrayList和LinkedList墓猎。

3.1.1 ArrayList

就Java文檔的解釋捆昏，整理出以下幾點(diǎn)特點(diǎn)：

1. ArrayList是一個(gè)實(shí)現(xiàn)了List接口的可變數(shù)組
2. 可以插入null
3. 它的size, isEmpty, get, set, iterator,add這些方法的時(shí)間復(fù)雜度是O(1),如果add n個(gè)數(shù)據(jù)則時(shí)間復(fù)雜度是O(n).
4. ArrayList不是synchronized的。

然后我們來簡單看下ArrayList源碼實(shí)現(xiàn)毙沾。這里只寫部分源碼分析骗卜。

所有元素都是保存在一個(gè)Object數(shù)組中，然后通過size控制長度。

transient Object[] elementData;

private int size;

這時(shí)候看下add的代碼分析

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);
}

其實(shí)在每次add的時(shí)候會(huì)判斷數(shù)據(jù)長度寇仓，如果不夠的話會(huì)調(diào)用Arrays.copyOf举户，復(fù)制一份更長的數(shù)組，并把前面的數(shù)據(jù)放進(jìn)去遍烦。

我們?cè)倏聪聄emove的代碼是如何實(shí)現(xiàn)的俭嘁。

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;
}

其實(shí)就是直接使用System.arraycopy把需要?jiǎng)h除index后面的都往前移一位然后再把最后一個(gè)去掉。

PS：終于發(fā)現(xiàn)以前學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)用到用場了乳愉。O兄淫。O

3.1.2 LinkedList

LinkedList是一個(gè)鏈表維護(hù)的序列容器屯远。和ArrayList都是序列容器蔓姚，一個(gè)使用數(shù)組存儲(chǔ)，一個(gè)使用鏈表存儲(chǔ)慨丐。

數(shù)組和鏈表2種數(shù)據(jù)結(jié)構(gòu)的對(duì)比：

1. 查找方面坡脐。數(shù)組的效率更高，可以直接索引出查找房揭，而鏈表必須從頭查找备闲。
2. 插入刪除方面。特別是在中間進(jìn)行插入刪除捅暴，這時(shí)候鏈表體現(xiàn)出了極大的便利性恬砂，只需要在插入或者刪除的地方斷掉鏈然后插入或者移除元素，然后再將前后鏈重新組裝蓬痒，但是數(shù)組必須重新復(fù)制一份將所有數(shù)據(jù)后移或者前移泻骤。
3. 在內(nèi)存申請(qǐng)方面，當(dāng)數(shù)組達(dá)到初始的申請(qǐng)長度后梧奢，需要重新申請(qǐng)一個(gè)更大的數(shù)組然后把數(shù)據(jù)遷移過去才行狱掂。而鏈表只需要?jiǎng)討B(tài)創(chuàng)建即可。

如上LinkedList和ArrayList的區(qū)別也就在此亲轨。根據(jù)使用場景選擇更加適合的List趋惨。

下面簡單展示LinkedList的部分源碼解析。

首先是鏈表的節(jié)點(diǎn)的定義,非常簡單的一個(gè)雙向鏈表惦蚊。

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

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

然后每個(gè)LinkedList中會(huì)持有鏈表的頭指針和尾指針

transient int size = 0;

transient Node<E> first;

transient Node<E> last;

列舉最基本的插入和刪除的鏈表操作

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
    
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

上面6個(gè)方法就是鏈表的核心器虾，頭尾中間插入，頭尾中間刪除蹦锋。其他對(duì)外的調(diào)用都是圍繞這幾個(gè)方法進(jìn)行操作的

同時(shí)LinkedList還實(shí)現(xiàn)了Deque接口兆沙，Deque接口是繼承Queue的。所以LinkedList還支持隊(duì)列的pop晕粪，push挤悉，peek操作。

總結(jié)

3.2 Set

Set的核心概念就是集合內(nèi)所有元素不重復(fù)诀诊。在Set這個(gè)子接口中沒有在Collection特別實(shí)現(xiàn)什么額外的方法洞渤，應(yīng)該只是定義了一個(gè)Set概念。下面我們來看Set的幾個(gè)常用的實(shí)現(xiàn)HashSet属瓣、LinkedHashSet载迄、TreeSet

3.2.1 HashSet

HashSet的核心概念。Java文檔中描述

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

大概意思是

HashSet實(shí)現(xiàn)了Set接口抡蛙，基于HashMap進(jìn)行存儲(chǔ)护昧。遍歷時(shí)不保證順序，并且不保證下次遍歷的順序和之前一樣粗截。HashSet中允許null元素惋耙。

進(jìn)入到HashSet源碼中我們發(fā)現(xiàn)，所有數(shù)據(jù)存儲(chǔ)在

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

意思就是HashSet的集合其實(shí)就是HashMap的key的集合熊昌，然后HashMap的val默認(rèn)都是PRESENT绽榛。HashMap的定義即是key不重復(fù)的集合。使用HashMap實(shí)現(xiàn)婿屹，這樣HashSet就不需要再實(shí)現(xiàn)一遍灭美。

所以所有的add，remove等操作其實(shí)都是HashMap的add昂利、remove操作届腐。遍歷操作其實(shí)就是HashMap的keySet的遍歷,舉例如下

...
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public void clear() {
    map.clear();
}
...

3.2.2 LinkedHashSet

LinkedHashSet的核心概念相對(duì)于HashSet來說就是一個(gè)可以保持順序的Set集合。HashSet是無序的页眯，LinkedHashSet會(huì)根據(jù)add梯捕，remove這些操作的順序在遍歷時(shí)返回固定的集合順序。這個(gè)順序不是元素的大小順序窝撵，而是可以保證2次遍歷的順序是一樣的傀顾。

類似HashSet基于HashMap的源碼實(shí)現(xiàn)，LinkedHashSet的數(shù)據(jù)結(jié)構(gòu)是基于LinkedHashMap碌奉。過多的就不說了短曾。

3.2.3 TreeSet

TreeSet即是一組有次序的集合，如果沒有指定排序規(guī)則Comparator赐劣，則會(huì)按照自然排序嫉拐。（自然排序即e1.compareTo(e2) == 0作為比較）

注意：TreeSet內(nèi)的元素必須實(shí)現(xiàn)Comparable接口。

TreeSet源碼的算法即基于TreeMap魁兼，具體算法在說明TreeMap的時(shí)候進(jìn)行解釋婉徘。

總結(jié)

4 HashMap盖呼、LinkedHashMap儒鹿、TreeMap和WeakHashMap

4.1 HashMap

HashMap就是最基礎(chǔ)最常用的一種Map，它無序几晤，以散列表的方式進(jìn)行存儲(chǔ)约炎。之前提到過，HashSet就是基于HashMap蟹瘾，只使用了HashMap的key作為單個(gè)元素存儲(chǔ)圾浅。

HashMap的訪問方式就是繼承于Map的最基礎(chǔ)的3種方式，詳細(xì)見上憾朴。在這里我具體分析一下HashMap的底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)狸捕。

在看HashMap源碼前，先理解一下他的存儲(chǔ)方式-散列表（哈希表）伊脓。像之前提到過的用數(shù)組存儲(chǔ)府寒，用鏈表存儲(chǔ)。哈希表是使用數(shù)組和鏈表的組合的方式進(jìn)行存儲(chǔ)报腔。(具體哈希表的概念自行搜索)如下圖就是HashMap采用的存儲(chǔ)方法。

哈希散列表

hash得到數(shù)值剖淀，放到數(shù)組中纯蛾，如果遇到?jīng)_突則以鏈表方式掛在下方。

HashMap的存儲(chǔ)定義是

transient Node<K,V>[] table;

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

數(shù)組table存放元素纵隔，如果遇到?jīng)_突下掛到?jīng)_突元素的next鏈表上翻诉。

在這我們可以看下get核心方法和put核心方法的源碼

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

上面代碼中看出先根據(jù)hash值和數(shù)組長度作且運(yùn)算得出下標(biāo)索引。如果存在判斷hash值是否完全一致捌刮，如果不完全一致則next鏈表向下找一致的hash值碰煌。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

上面是put的核心源碼，即查找hash值所在索引是否有元素绅作，沒有的話new一個(gè)Node直接放在table中芦圾。如果已經(jīng)有Node了，就遍歷該Node的next俄认，將新元素放到最后个少。

HashMap的遍歷，是從數(shù)組遍歷第一個(gè)非空的元素眯杏，然后再根據(jù)這個(gè)元素訪問其next下的所有Node夜焦。因?yàn)榈谝粋€(gè)元素不是一定從數(shù)組的0開始，所以HashMap是無序遍歷岂贩。

4.2 LinkedHashMap

LinkedHashMap相對(duì)于HashMap來說區(qū)別是茫经，LinkedHashMap遍歷的時(shí)候具有順序，可以保存插入的順序，（還可以設(shè)置最近訪問的元素也放在前面卸伞，即LRU）

其實(shí)LinkedHashMap的存儲(chǔ)還是跟HashMap一樣褥紫，采用哈希表方法存儲(chǔ)，只不過LinkedHashMap多維護(hù)了一份head瞪慧，tail鏈表髓考。

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;

即在創(chuàng)建新Node的時(shí)候?qū)⑿翹ode放到最后，這樣遍歷的時(shí)候不再像HashMap一樣弃酌，從數(shù)組開始判斷第一個(gè)非空元素氨菇，而是直接從表頭進(jìn)行遍歷。這樣即滿足有序遍歷妓湘。

4.3 TreeMap

TreeMap平時(shí)用的不多查蓉，TreeMap會(huì)實(shí)現(xiàn)SortMap接口，定義一個(gè)排序規(guī)則榜贴，這樣當(dāng)遍歷TreeMap的時(shí)候豌研，會(huì)根據(jù)規(guī)定的排序規(guī)則返回元素。

4.4 WeakHashMap

WeakHashMap唬党，此種Map的特點(diǎn)是鹃共，當(dāng)除了自身有對(duì)key的引用外，此key沒有其他引用那么此map會(huì)自動(dòng)丟棄此值驶拱，

舉例：聲明了兩個(gè)Map對(duì)象霜浴，一個(gè)是HashMap，一個(gè)是WeakHashMap蓝纲，同時(shí)向兩個(gè)map中放入a阴孟、b兩個(gè)對(duì)象，當(dāng)HashMap remove掉a 并且將a税迷、b都指向null時(shí)永丝，WeakHashMap中的a將自動(dòng)被回收掉。出現(xiàn)這個(gè)狀況的原因是箭养，對(duì)于a對(duì)象而言慕嚷，當(dāng)HashMap remove掉并且將a指向null后，除了WeakHashMap中還保存a外已經(jīng)沒有指向a的指針了露懒，所以WeakHashMap會(huì)自動(dòng)舍棄掉a闯冷，而對(duì)于b對(duì)象雖然指向了null，但HashMap中還有指向b的指針懈词，所以
WeakHashMap將會(huì)保留蛇耀。

WeakHashMap用的也不多，在這簡單提及坎弯。

總結(jié)

結(jié)尾

以上就是對(duì)于Java集合的完整分析和源碼解析。其中ArrayList拧咳、HashMap使用較多伯顶，當(dāng)考慮到效率時(shí)記得有Linded系列集合和WeakHashMap。Over~~

更多文章關(guān)注我的公眾號(hào)

我的公眾號(hào)