Java集合框架是什么

這篇文章主要介紹了Java集合框架是什么，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

一、簡(jiǎn)介

1、集合框架介紹

Java集合框架提供了一套性能優(yōu)良，使用方便的接口和類，他們位于java.util包中。容器主要包括 Collection 和 Map 兩種，Collection 存儲(chǔ)著對(duì)象的集合，而 Map 存儲(chǔ)著鍵值對(duì)(兩個(gè)對(duì)象)的映射表

2、相關(guān)容器介紹

2.1 Set相關(guān)

• TreeSet
  基于紅黑樹實(shí)現(xiàn)，支持有序性操作，例如根據(jù)一個(gè)范圍查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的時(shí)間復(fù)雜度為 O(1)，TreeSet 則為 O(logN)

• HashSet
  基于哈希表實(shí)現(xiàn)，支持快速查找，但不支持有序性操作。并且失去了元素的插入順序信息，也就是說使用 Iterator 遍歷 HashSet 得到的結(jié)果是不確定的。

• LinkedHashSet
  具有 HashSet 的查找效率，且內(nèi)部使用雙向鏈表維護(hù)元素的插入順序。

2.2 List相關(guān)

• ArrayList
  基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，支持隨機(jī)訪問。

• Vector
  和 ArrayList 類似，但它是線程安全的。

• LinkedList
  基于雙向鏈表實(shí)現(xiàn)，只能順序訪問，但是可以快速地在鏈表中間插入和刪除元素。不僅如此，LinkedList 還可以用作棧、隊(duì)列和雙向隊(duì)列。

2.3 Queue相關(guān)

• LinkedList
  可以實(shí)現(xiàn)雙向隊(duì)列。

• PriorityQueue
  基于堆結(jié)構(gòu)實(shí)現(xiàn)，可以用它來實(shí)現(xiàn)優(yōu)先隊(duì)列。

2.4 Map相關(guān)

• TreeMap
  基于紅黑樹實(shí)現(xiàn)。

• HashMap
  基于哈希表實(shí)現(xiàn)。

• HashTable
  和 HashMap 類似，但它是線程安全的，這意味著同一時(shí)刻多個(gè)線程可以同時(shí)寫入 HashTable 并且不會(huì)導(dǎo)致數(shù)據(jù)不一致。它是遺留類，不應(yīng)該去使用它?，F(xiàn)在可以使用 ConcurrentHashMap 來支持線程安全，并且 ConcurrentHashMap 的效率會(huì)更高，因?yàn)?ConcurrentHashMap 引入了分段鎖。

• LinkedHashMap
  使用雙向鏈表來維護(hù)元素的順序，順序?yàn)椴迦腠樞蚧蛘咦罱钌偈褂?LRU)順序

3、集合重點(diǎn)

• Collection 接口存儲(chǔ)一組不唯一，無序的對(duì)象

• List 接口存儲(chǔ)一組不唯一，有序的對(duì)象。

• Set 接口存儲(chǔ)一組唯一，無序的對(duì)象

• Map 接口存儲(chǔ)一組鍵值對(duì)象，提供key到value的映射

• ArrayList實(shí)現(xiàn)了長(zhǎng)度可變的數(shù)組，在內(nèi)存中分配連續(xù)的空間。遍歷元素和隨機(jī)訪問元素的效率比較高

• LinkedList采用鏈表存儲(chǔ)方式。插入、刪除元素時(shí)效率比較高

• HashSet采用哈希算法實(shí)現(xiàn)的Set

• HashSet的底層是用HashMap實(shí)現(xiàn)的，因此查詢效率較高，由于采用hashCode算法直接確定 元素的內(nèi)存地址，增刪效率高

二、ArrayList分析

1、ArrayList使用

2、ArrayList介紹

• ArrayList是可以動(dòng)態(tài)增長(zhǎng)和縮減的索引序列，它是基于數(shù)組實(shí)現(xiàn)的List類

• 該類封裝了一個(gè)動(dòng)態(tài)再分配的Object[]數(shù)組，每一個(gè)類對(duì)象都有一個(gè)capacity[容量]屬性，表示它們所封裝的Object[]數(shù)組的長(zhǎng)度，當(dāng)向ArrayList中添加元素時(shí)，該屬性值會(huì)自動(dòng)增加。如果想ArrayList中添加大量元素，可使用ensureCapacity方法一次性增加capacity，可以減少增加重分配的次數(shù)提高性能

• ArrayList的用法和Vector向類似，但是Vector是一個(gè)較老的集合，具有很多缺點(diǎn)，不建議使用

另外，ArrayList和Vector的區(qū)別是：ArrayList是線程不安全的，當(dāng)多條線程訪問同一個(gè)ArrayList集合時(shí)，程序需要手動(dòng)保證該集合的同步性，而Vector則是線程安全的。

3、源碼分析

3.1 繼承結(jié)構(gòu)與層次關(guān)系

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

這里簡(jiǎn)單解釋一下幾個(gè)接口

• RandomAccess接口
  這個(gè)是一個(gè)標(biāo)記性接口，通過查看api文檔，它的作用就是用來快速隨機(jī)存取，有關(guān)效率的問題，在實(shí)現(xiàn)了該接口的話，那么使用普通的for循環(huán)來遍歷，性能更高，例如ArrayList。而沒有實(shí)現(xiàn)該接口的話，使用Iterator來迭代，這樣性能更高，例如linkedList。所以這個(gè)標(biāo)記性只是為了 讓我們知道我們用什么樣的方式去獲取數(shù)據(jù)性能更好。

• Cloneable接口
  實(shí)現(xiàn)了該接口，就可以使用Object.Clone()方法了。

• Serializable接口
  實(shí)現(xiàn)該序列化接口，表明該類可以被序列化。什么是序列化？簡(jiǎn)單的說，就是能夠從類變成字節(jié)流傳輸，然后還能從字節(jié)流變成原來的類。

這里的繼承結(jié)構(gòu)可通過IDEA中Navigate>Type Hierarchy查看

3.2 屬性

//版本號(hào)
private static final long serialVersionUID = 8683452581122892189L;
//缺省容量
private static final int DEFAULT_CAPACITY = 10;
//空對(duì)象數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//缺省空對(duì)象數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存儲(chǔ)的數(shù)組元素
transient Object[] elementData; // non-private to simplify nested class access
//實(shí)際元素大小，默認(rèn)為0
private int size;
//最大數(shù)組容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3.3 構(gòu)造方法

/**
 * 構(gòu)造具有指定初始容量的空列表
 * 如果指定的初始容量為負(fù)，則為IllegalArgumentException
 */public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }}/**
 * 默認(rèn)空數(shù)組的大小為10
 * ArrayList中儲(chǔ)存數(shù)據(jù)的其實(shí)就是一個(gè)數(shù)組，這個(gè)數(shù)組就是elementData
 */public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/**
 * 按照集合迭代器返回元素的順序構(gòu)造包含指定集合的元素的列表
 */public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 轉(zhuǎn)換為數(shù)組
        //每個(gè)集合的toarray()的實(shí)現(xiàn)方法不一樣，所以需要判斷一下，如果不是Object[].class類型，那么久需要使用ArrayList中的方法去改造一下。
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 否則就用空數(shù)組代替
        this.elementData = EMPTY_ELEMENTDATA;
    }}

3.4 自動(dòng)擴(kuò)容

每當(dāng)向數(shù)組中添加元素時(shí)，都要去檢查添加后元素的個(gè)數(shù)是否會(huì)超出當(dāng)前數(shù)組的長(zhǎng)度，如果超出，數(shù)組將會(huì)進(jìn)行擴(kuò)容，以滿足添加數(shù)據(jù)的需求。數(shù)組擴(kuò)容通過一個(gè)公開的方法ensureCapacity(int minCapacity)來實(shí)現(xiàn)。在實(shí)際添加大量元素前，我也可以使用ensureCapacity來手動(dòng)增加ArrayList實(shí)例的容量，以減少遞增式再分配的數(shù)量。

數(shù)組進(jìn)行擴(kuò)容時(shí)，會(huì)將**老數(shù)組中的元素重新拷貝一份到新的數(shù)組中，每次數(shù)組容量的增長(zhǎng)大約是其原容量的1.5倍。**這種操作的代價(jià)是很高的，因此在實(shí)際使用時(shí)，我們應(yīng)該盡量避免數(shù)組容量的擴(kuò)張。當(dāng)我們可預(yù)知要保存的元素的多少時(shí)，要在構(gòu)造ArrayList實(shí)例時(shí)，就指定其容量，以避免數(shù)組擴(kuò)容的發(fā)生?；蛘吒鶕?jù)實(shí)際需求，通過調(diào)用ensureCapacity方法來手動(dòng)增加ArrayList實(shí)例的容量。

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //判斷初始化的elementData是不是空的數(shù)組，也就是沒有長(zhǎng)度
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //因?yàn)槿绻强盏脑?，minCapacity=size+1；其實(shí)就是等于1，空的數(shù)組沒有長(zhǎng)度就存放不了
        //所以就將minCapacity變成10，也就是默認(rèn)大小，但是在這里，還沒有真正的初始化這個(gè)elementData的大小
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //確認(rèn)實(shí)際的容量，上面只是將minCapacity=10，這個(gè)方法就是真正的判斷elementData是否夠用
    return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //minCapacity如果大于了實(shí)際elementData的長(zhǎng)度，那么就說明elementData數(shù)組的長(zhǎng)度不夠用
    /*第一種情況：由于elementData初始化時(shí)是空的數(shù)組，那么第一次add的時(shí)候，
    minCapacity=size+1；也就minCapacity=1，在上一個(gè)方法(確定內(nèi)部容量ensureCapacityInternal)
    就會(huì)判斷出是空的數(shù)組，就會(huì)給將minCapacity=10，到這一步為止，還沒有改變elementData的大小。
    第二種情況：elementData不是空的數(shù)組了，那么在add的時(shí)候，minCapacity=size+1；也就是
    minCapacity代表著elementData中增加之后的實(shí)際數(shù)據(jù)個(gè)數(shù)，拿著它判斷elementData的length
    是否夠用，如果length不夠用，那么肯定要擴(kuò)大容量，不然增加的這個(gè)元素就會(huì)溢出。*/ 
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);}//ArrayList核心的方法，能擴(kuò)展數(shù)組大小的真正秘密。private void grow(int minCapacity) {
    //將擴(kuò)充前的elementData大小給oldCapacity
    int oldCapacity = elementData.length;
    //newCapacity就是1.5倍的oldCapacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    /*這句話就是適應(yīng)于elementData就空數(shù)組的時(shí)候，length=0，那么oldCapacity=0，newCapacity=0，
    所以這個(gè)判斷成立，在這里就是真正的初始化elementData的大小了，就是為10.前面的工作都是準(zhǔn)備工作。
    */
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果newCapacity超過了最大的容量限制，就調(diào)用hugeCapacity，也就是將能給的最大值給newCapacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //新的容量大小已經(jīng)確定好就copy數(shù)組，改變?nèi)萘看笮　?
    elementData = Arrays.copyOf(elementData, newCapacity);}//用來賦最大值private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //如果minCapacity都大于MAX_ARRAY_SIZE，那么就Integer.MAX_VALUE返回，反之將MAX_ARRAY_SIZE返回。
    //相當(dāng)于給ArrayList上了兩層防護(hù)
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;}

3.5 add()方法

/**
 * 添加一個(gè)特定的元素到list的末尾。
 * 先size+1判斷數(shù)組容量是否夠用，最后加入元素
 */public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;}/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */public void add(int index, E element) {
    //檢查index也就是插入的位置是否合理。
    rangeCheckForAdd(index);
    //檢查容量是否夠用，不夠就自動(dòng)擴(kuò)容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //這個(gè)方法就是用來在插入元素之后，要將index之后的元素都往后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;}

當(dāng)調(diào)用add()方法時(shí)，實(shí)際函數(shù)調(diào)用：

add→ensureCapacityInternal→ensureExplicitCapacity(→grow→hugeCapacity)

例如剛開始初始化一個(gè)空數(shù)組后add一個(gè)值，會(huì)首先進(jìn)行自動(dòng)擴(kuò)容

3.6 trimToSize()

將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實(shí)際元素的大小的功能

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA          : Arrays.copyOf(elementData, size);
    }}

3.7 remove()方法

remove()方法也有兩個(gè)版本，一個(gè)是remove(int index)刪除指定位置的元素，另一個(gè)是remove(Object o)刪除第一個(gè)滿足o.equals(elementData[index])的元素。刪除操作是add()操作的逆過程，需要將刪除點(diǎn)之后的元素向前移動(dòng)一個(gè)位置。需要注意的是為了讓GC起作用，必須顯式的為最后一個(gè)位置賦null值。

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; //清除該位置的引用，讓GC起作用

        return oldValue;
    }

3.8 其他方法

這里簡(jiǎn)單介紹了核心方法，其他方法查看源碼可以很快了解

3.9 Fail-Fast機(jī)制

ArrayList采用了快速失敗的機(jī)制，通過記錄modCount參數(shù)來實(shí)現(xiàn)。在面對(duì)并發(fā)的修改時(shí)，迭代器很快就會(huì)完全失敗，并拋出ConcurrentModificationException異常，而不是冒著在將來某個(gè)不確定時(shí)間發(fā)生任意不確定行為的風(fēng)險(xiǎn)

4、總結(jié)

• ArrayList可以存放null

• ArrayList本質(zhì)上就是一個(gè)elementData數(shù)組

• ArrayList區(qū)別于數(shù)組的地方在于能夠自動(dòng)擴(kuò)展大小，其中關(guān)鍵的方法就是gorw()方法

• ArrayList中removeAll(collection c)和clear()的區(qū)別就是removeAll可以刪除批量指定的元素，而clear是全是刪除集合中的元素

• ArrayList由于本質(zhì)是數(shù)組，所以它在數(shù)據(jù)的查詢方面會(huì)很快，而在插入刪除這些方面，性能下降很多，有移動(dòng)很多數(shù)據(jù)才能達(dá)到應(yīng)有的效果

• ArrayList實(shí)現(xiàn)了RandomAccess，所以在遍歷它的時(shí)候推薦使用for循環(huán)

三、LinkedList分析

1、LinkedList使用

2、LinkedList介紹

LinkedList同時(shí)實(shí)現(xiàn)了List接口和Deque接口，也就是說它既可以看作一個(gè)順序容器，又可以看作一個(gè)隊(duì)列(Queue)，同時(shí)又可以看作一個(gè)棧(Stack)。這樣看來，LinkedList簡(jiǎn)直就是個(gè)全能冠軍。當(dāng)你需要使用?；蛘哧?duì)列時(shí)，可以考慮使用LinkedList，一方面是因?yàn)镴ava官方已經(jīng)聲明不建議使用Stack類，更遺憾的是，Java里根本沒有一個(gè)叫做Queue_的類(它是個(gè)接口名字)。關(guān)于?；蜿?duì)列，現(xiàn)在的首選是ArrayDeque，它有著比LinkedList(當(dāng)作?；蜿?duì)列使用時(shí))有著更好的性能。

LinkedList的實(shí)現(xiàn)方式?jīng)Q定了所有跟下標(biāo)相關(guān)的操作都是線性時(shí)間，而在首段或者末尾刪除元素只需要常數(shù)時(shí)間。為追求效率LinkedList沒有實(shí)現(xiàn)同步(synchronized)，如果需要多個(gè)線程并發(fā)訪問，可以先采用Collections.synchronizedList()方法對(duì)其進(jìn)行包裝

3、源碼分析

3.1 繼承結(jié)構(gòu)與層次

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

這里可以發(fā)現(xiàn)LinkedList多了一層AbstractSequentialList的抽象類，這是為了減少實(shí)現(xiàn)順序存?。ɡ鏛inkedList）這種類的工作。如果自己想實(shí)現(xiàn)順序存取這種特性的類(就是鏈表形式)，那么就繼承 這個(gè)AbstractSequentialList抽象類，如果想像數(shù)組那樣的隨機(jī)存取的類，那么就去實(shí)現(xiàn)AbstracList抽象類。

• List接口
  列表add、set等一些對(duì)列表進(jìn)行操作的方法

• Deque接口
  有隊(duì)列的各種特性

• Cloneable接口
  能夠復(fù)制，使用那個(gè)copy方法

• Serializable接口
  能夠序列化。

• 沒有RandomAccess
  推薦使用iterator，在其中就有一個(gè)foreach，增強(qiáng)的for循環(huán)，其中原理也就是iterator，我們?cè)谑褂玫臅r(shí)候，使用foreach或者iterator

3.2 屬性與構(gòu)造方法

transient關(guān)鍵字修飾，這也意味著在序列化時(shí)該域是不會(huì)序列化的

//實(shí)際元素個(gè)數(shù)transient int size = 0;
//頭結(jié)點(diǎn)transient Node<E> first;
//尾結(jié)點(diǎn)transient Node<E> last;

public LinkedList() {}public LinkedList(Collection<? extends E> c) {
    this();
    //將集合c中的各個(gè)元素構(gòu)建成LinkedList鏈表
    addAll(c);}

3.3 內(nèi)部類Node

//根據(jù)前面介紹雙向鏈表就知道這個(gè)代表什么了，linkedList的奧秘就在這里private static class Node<E> {
    // 數(shù)據(jù)域（當(dāng)前節(jié)點(diǎn)的值）
    E item;
    //后繼
    Node<E> next;
    //前驅(qū)
    Node<E> prev;
    // 構(gòu)造函數(shù)，賦值前驅(qū)后繼
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }}

3.4 核心方法add()和addAll()

public boolean add(E e) {
    linkLast(e);
    return true;}void linkLast(E e) {
    //臨時(shí)節(jié)點(diǎn)l(L的小寫)保存last，也就是l指向了最后一個(gè)節(jié)點(diǎn)
    final Node<E> l = last;
    //將e封裝為節(jié)點(diǎn)，并且e.prev指向了最后一個(gè)節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(l, e, null);
    //newNode成為了最后一個(gè)節(jié)點(diǎn)，所以last指向了它
    last = newNode;
    if (l == null)
        //判斷是不是一開始鏈表中就什么都沒有，如果沒有，則new Node就成為了第一個(gè)結(jié)點(diǎn)，first和last都指向它
        first = newNode;
    else
        //正常的在最后一個(gè)節(jié)點(diǎn)后追加，那么原先的最后一個(gè)節(jié)點(diǎn)的next就要指向現(xiàn)在真正的 最后一個(gè)節(jié)點(diǎn)，原先的最后一個(gè)節(jié)點(diǎn)就變成了倒數(shù)第二個(gè)節(jié)點(diǎn)
        l.next = newNode;
    //添加一個(gè)節(jié)點(diǎn)，size自增
    size++;
    modCount++;}

addAll()有兩個(gè)重載函數(shù)，addAll(Collection<? extends E>)型和addAll(int,Collection<? extends E>)型，我們平時(shí)習(xí)慣調(diào)用的addAll(Collection<?extends E>)型會(huì)轉(zhuǎn)化為addAll(int,Collection<? extends<E>)型

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);}public boolean addAll(int index, Collection<? extends E> c) {
    //檢查index這個(gè)是否為合理
    checkPositionIndex(index);
    //將集合c轉(zhuǎn)換為Object數(shù)組
    Object[] a = c.toArray();
    //數(shù)組a的長(zhǎng)度numNew，也就是由多少個(gè)元素
    int numNew = a.length;
    if (numNew == 0)
        //如果空的就什么也不做
        return false;

    Node<E> pred, succ;
    //構(gòu)造方法中傳過來的就是index==size
    //情況一：構(gòu)造方法創(chuàng)建的一個(gè)空的鏈表，那么size=0，last、和first都為null。linkedList中是空的。
    //什么節(jié)點(diǎn)都沒有。succ=null、pred=last=null
    //情況二：鏈表中有節(jié)點(diǎn)，size就不是為0，first和last都分別指向第一個(gè)節(jié)點(diǎn)，和最后一個(gè)節(jié)點(diǎn)，
    //在最后一個(gè)節(jié)點(diǎn)之后追加元素，就得記錄一下最后一個(gè)節(jié)點(diǎn)是什么，所以把last保存到pred臨時(shí)節(jié)點(diǎn)中。
    //情況三index！=size，說明不是前面兩種情況，而是在鏈表中間插入元素，那么就得知道index上的節(jié)點(diǎn)是誰，
    //保存到succ臨時(shí)節(jié)點(diǎn)中，然后將succ的前一個(gè)節(jié)點(diǎn)保存到pred中，這樣保存了這兩個(gè)節(jié)點(diǎn)，就能夠準(zhǔn)確的插入節(jié)點(diǎn)了
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        /*如果succ==null，說明是情況一或者情況二，
        情況一、構(gòu)造方法，也就是剛創(chuàng)建的一個(gè)空鏈表，pred已經(jīng)是newNode了，
        last=newNode，所以linkedList的first、last都指向第一個(gè)節(jié)點(diǎn)。
        情況二、在最后節(jié)后之后追加節(jié)點(diǎn)，那么原先的last就應(yīng)該指向現(xiàn)在的最后一個(gè)節(jié)點(diǎn)了，
        就是newNode。*/
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;}//根據(jù)引下標(biāo)找到該結(jié)點(diǎn)并返回Node<E> node(int index) {
    //判斷插入的位置在鏈表前半段或者是后半段
    if (index < (size >> 1)) {
        Node<E> x = first;
        //從頭結(jié)點(diǎn)開始正向遍歷
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        //從尾結(jié)點(diǎn)開始反向遍歷
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }}

3.5 remove()

/*如果我們要移除的值在鏈表中存在多個(gè)一樣的值，那么我們
會(huì)移除index最小的那個(gè)，也就是最先找到的那個(gè)值，如果不存在這個(gè)值，那么什么也不做
*/public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;}不能傳一個(gè)null值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的前后指向都為null了，也把item為null，讓gc回收它
    x.item = null;
    size--;
    modCount++;
    return element;}

3.6 其他方法

**get(index)、indexOf(Object o)**等查看源碼即可

3.7 LinkedList的迭代器

在LinkedList中除了有一個(gè)Node的內(nèi)部類外，應(yīng)該還能看到另外兩個(gè)內(nèi)部類，那就是ListItr，還有一個(gè)是DescendingIterator內(nèi)部類

/*這個(gè)類，還是調(diào)用的ListItr，作用是封裝一下Itr中幾個(gè)方法，讓使用者以正常的思維去寫代碼，
例如，在從后往前遍歷的時(shí)候，也是跟從前往后遍歷一樣，使用next等操作，而不用使用特殊的previous。
*/private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }}

4、總結(jié)

• linkedList本質(zhì)上是一個(gè)雙向鏈表，通過一個(gè)Node內(nèi)部類實(shí)現(xiàn)的這種鏈表結(jié)構(gòu)。linkedList能存儲(chǔ)null值

• 跟ArrayList相比較，就真正的知道了，LinkedList在刪除和增加等操作上性能好，而ArrayList在查詢的性能上好，從源碼中看，它不存在容量不足的情況

• linkedList不光能夠向前迭代，還能像后迭代，并且在迭代的過程中，可以修改值、添加值、還能移除值

• linkedList不光能當(dāng)鏈表，還能當(dāng)隊(duì)列使用，這個(gè)就是因?yàn)閷?shí)現(xiàn)了Deque接口

四、List總結(jié)

1、ArrayList和LinkedList區(qū)別

• ArrayList底層是用數(shù)組實(shí)現(xiàn)的順序表，是隨機(jī)存取類型，可自動(dòng)擴(kuò)增，并且在初始化時(shí)，數(shù)組的長(zhǎng)度是0，只有在增加元素時(shí)，長(zhǎng)度才會(huì)增加。默認(rèn)是10，不能無限擴(kuò)增，有上限，在查詢操作的時(shí)候性能更好

• LinkedList底層是用鏈表來實(shí)現(xiàn)的，是一個(gè)雙向鏈表，注意這里不是雙向循環(huán)鏈表,順序存取類型。在源碼中，似乎沒有元素個(gè)數(shù)的限制。應(yīng)該能無限增加下去，直到內(nèi)存滿了在進(jìn)行刪除，增加操作時(shí)性能更好。

兩個(gè)都是線程不安全的，在iterator時(shí)，會(huì)發(fā)生fail-fast：快速失效。

2、ArrayList和Vector區(qū)別

• ArrayList線程不安全，在用iterator，會(huì)發(fā)生fail-fast

• Vector線程安全，因?yàn)樵诜椒ㄇ凹恿薙ynchronized關(guān)鍵字，也會(huì)發(fā)生fail-fast

3、fail-fast和fail-safe區(qū)別與情況說明

在java.util下的集合都是發(fā)生fail-fast，而在java.util.concurrent下的發(fā)生的都是fail-safe

• fail-fast
  快速失敗，例如在arrayList中使用迭代器遍歷時(shí)，有另外的線程對(duì)arrayList的存儲(chǔ)數(shù)組進(jìn)行了改變，比 如add、delete等使之發(fā)生了結(jié)構(gòu)上的改變，所以Iterator就會(huì)快速報(bào)一個(gè)java.util.ConcurrentModi?cationException異常（并發(fā)修改異常），這就是快速失敗

• fail-safe
  安全失敗，在java.util.concurrent下的類，都是線程安全的類，他們?cè)诘倪^程中，如果有線程進(jìn)行結(jié)構(gòu)的改變，不會(huì)報(bào)異常，而是正常遍歷，這就是安全失敗

• 為什么在java.util.concurrent包下對(duì)集合有結(jié)構(gòu)的改變卻不會(huì)報(bào)異常？
  在concurrent下的集合類增加元素的時(shí)候使用Arrays.copyOf()來拷貝副本，在副本上增加元素，如果有其他線程在此改變了集合的結(jié)構(gòu)，那也是在副本上的改變，而不是影響到原集合，迭代器還是照常遍歷，遍歷完之后，改變?cè)弥赶蚋北?，所以總的一句話就是如果在此包下的類進(jìn)行增加刪除，就會(huì)出現(xiàn)一個(gè)副本。所以能防止fail-fast，這種機(jī)制并不會(huì)出錯(cuò)，所以我們叫這種現(xiàn)象為fail-safe

• vector也是線程安全的，為什么是fail-fast呢？
  出現(xiàn)fail-safe是因?yàn)樗麄冊(cè)趯?shí)現(xiàn)增刪的底層機(jī)制不一樣，就像上面說的，會(huì)有一個(gè)副本，而像arrayList、linekdList、verctor等他們底層就是對(duì)著真正的引用進(jìn)行操作，所以才會(huì)發(fā)生異常

4、為什么現(xiàn)在都不提倡使用Vector

• vector實(shí)現(xiàn)線程安全的方法是在每個(gè)操作方法上加鎖，這些鎖并不是必須要的，在實(shí)際開發(fā)中，一般都是通過鎖一系列的操作來實(shí)現(xiàn)線程安全，也就是說將需要同步的資源放一起加鎖來保證線程安全

• 如果多個(gè)Thread并發(fā)執(zhí)行一個(gè)已經(jīng)加鎖的方法，但是在該方法中，又有Vector的存在，Vector
  本身實(shí)現(xiàn)中已經(jīng)加鎖了，那么相當(dāng)于鎖上又加鎖，會(huì)造成額外的開銷

• Vector還有fail-fast的問題，也就是說它也無法保證遍歷安全，在 遍歷時(shí)又得額外加鎖，又是額外的開銷，還不如直接用arrayList，然后再加鎖

總結(jié)：Vector在你不需要進(jìn)行線程安全的時(shí)候，也會(huì)給你加鎖，也就導(dǎo)致了額外開銷，所以在jdk1.5之后就被棄用了，現(xiàn)在如果要用到線程安全的集合，都是從java.util.concurrent包下去拿相應(yīng)的類。

五、HashMap分析

1、HashMap介紹

1.1 Java8以前的HashMap

通過key、value封裝成一個(gè)entry對(duì)象，然后通過key的值來計(jì)算該entry的hash值，通過entry的hash 值和數(shù)組的長(zhǎng)度length來計(jì)算出entry放在數(shù)組中的哪個(gè)位置上面，每次存放都是將entry放在第一個(gè)位置。

HashMap實(shí)現(xiàn)了Map接口，即允許放入key為null的元素，也允許插入value為null的元素；除該類未實(shí)現(xiàn)同步外，其余跟Hashtable大致相同；跟TreeMap不同，該容器不保證元素順序，根據(jù)需要該容器可能會(huì)對(duì)元素重新哈希，元素的順序也會(huì)被重新打散，因此不同時(shí)間迭代同一個(gè)HashMap的順序可能會(huì)不同。 根據(jù)對(duì)沖突的處理方式不同，哈希表有兩種實(shí)現(xiàn)方式，一種開放地址方式(Open addressing)，另一種是沖突鏈表方式(Separate chaining with linked lists)。Java7 HashMap采用的是沖突鏈表方式。

1.2 Java8后的HashMap

Java8 對(duì) HashMap 進(jìn)行了一些修改，最大的不同就是利用了紅黑樹，所以其由 數(shù)組+鏈表+紅黑樹 組成。根據(jù) Java7 HashMap 的介紹，我們知道，查找的時(shí)候，根據(jù) hash 值我們能夠快速定位到數(shù)組的具體下標(biāo)，但是之后的話，需要順著鏈表一個(gè)個(gè)比較下去才能找到我們需要的，時(shí)間復(fù)雜度取決于鏈表的長(zhǎng)度為 O(n)。為了降低這部分的開銷，在 Java8 中，當(dāng)鏈表中的元素達(dá)到了 8 個(gè)時(shí)，會(huì)將鏈表轉(zhuǎn)換為紅黑樹，在這些位置進(jìn)行查找的時(shí)候可以降低時(shí)間復(fù)雜度為 O(logN)。

Java7 中使用 Entry 來代表每個(gè) HashMap 中的數(shù)據(jù)節(jié)點(diǎn)，Java8 中使用 Node，基本沒有區(qū)別，都是 key，value，hash 和 next 這四個(gè)屬性，不過，Node 只能用于鏈表的情況，紅黑樹的情況需要使用 TreeNode

2、Java8 HashMap源碼分析

2.1 繼承結(jié)構(gòu)與層次

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

2.2 屬性

//序列號(hào)private static final long serialVersionUID = 362498820763181265L;
//默認(rèn)的初始容量static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
// aka 16
//最大容量static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)加載因子static final float DEFAULT_LOAD_FACTOR = 0.75f;
//當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹static final int TREEIFY_THRESHOLD = 8;
//當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)樹轉(zhuǎn)鏈表static final int UNTREEIFY_THRESHOLD = 6;
//桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對(duì)應(yīng)的table的最小大小static final int MIN_TREEIFY_CAPACITY = 64;
//存儲(chǔ)元素的數(shù)組，總是2的冪次倍transient Node<K,V>[] table;
//存放具體元素的集transient Set<Map.Entry<K,V>> entrySet;
//存放元素的個(gè)數(shù)，注意這個(gè)不等于數(shù)組的長(zhǎng)度transient int size;
//每次擴(kuò)容和更改map結(jié)構(gòu)的計(jì)數(shù)器transient int modCount;
//臨界值，當(dāng)實(shí)際大小(容量*填充因子)超過臨界值時(shí)，會(huì)進(jìn)行擴(kuò)容int threshold;
//填充因子,計(jì)算HashMap的實(shí)時(shí)裝載因子的方法為：size/capacityfinal float loadFactor;

2.3 構(gòu)造方法

public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0，否則報(bào)錯(cuò)
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 初始容量不能大于最大值，否則為最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //填充因子不能小于或等于0，不能為非數(shù)字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
         loadFactor);
    //初始化填充因子                                       
    this.loadFactor = loadFactor;
    //初始化threshold大小
    this.threshold = tableSizeFor(initialCapacity);}//這個(gè)方法將傳進(jìn)來的參數(shù)轉(zhuǎn)變?yōu)?的n次方的數(shù)值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;}/**
 * 自定義初始容量，加載因子為默認(rèn)
 */public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);}/**
 * 使用默認(rèn)的加載因子等字段
 */public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public HashMap(Map<? extends K, ? extends V> m) {
    //初始化填充因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    //將m中的所有元素添加至HashMap中
    putMapEntries(m, false);}//將m的所有元素存入該實(shí)例final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        //判斷table是否已經(jīng)初始化
        if (table == null) { // pre-size
            //未初始化，s為m的實(shí)際元素個(gè)數(shù)
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            //計(jì)算得到的t大于閾值，則初始化閾值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        //將m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }}

2.4 核心方法

put()方法

先計(jì)算key的hash值，然后根據(jù)hash值搜索在table數(shù)組中的索引位置，如果table數(shù)組在該位置處有元素，則查找是否存在相同的key，若存在則覆蓋原來key的value，否則將該元素保存在鏈表尾部，注意JDK1.7中采用的是頭插法，即每次都將沖突的鍵值對(duì)放置在鏈表頭，這樣最初的那個(gè)鍵值對(duì)最終就會(huì)成為鏈尾，而JDK1.8中使用的是尾插法。此外，若table在該處沒有元素，則直接保存。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //第一次put元素時(shí)，table數(shù)組為空，先調(diào)用resize生成一個(gè)指定容量的數(shù)組
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //hash值和n-1的與運(yùn)算結(jié)果為桶的位置，如果該位置空就直接放置一個(gè)Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //如果計(jì)算出的bucket不空，即發(fā)生哈希沖突，就要進(jìn)一步判斷
    else {
        Node<K,V> e; K k;
        //判斷當(dāng)前Node的key與要put的key是否相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //判斷當(dāng)前Node是否是紅黑樹的節(jié)點(diǎn)
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //以上都不是，說明要new一個(gè)Node，加入到鏈表中
        else {
            for (int binCount = 0; ; ++binCount) {
              //在鏈表尾部插入新節(jié)點(diǎn)，注意jdk1.8是在鏈表尾部插入新節(jié)點(diǎn)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果當(dāng)前鏈表中的元素大于樹化的閾值，進(jìn)行鏈表轉(zhuǎn)樹的操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //在鏈表中繼續(xù)判斷是否已經(jīng)存在完全相同的key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //走到這里，說明本次put是更新一個(gè)已存在的鍵值對(duì)的value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //在hashMap中，afterNodeAccess方法體為空，交給子類去實(shí)現(xiàn)
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //如果當(dāng)前size超過臨界值，就擴(kuò)容。注意是先插入節(jié)點(diǎn)再擴(kuò)容
    if (++size > threshold)
        resize();
    //在hashMap中，afterNodeInsertion方法體為空，交給子類去實(shí)現(xiàn)
    afterNodeInsertion(evict);
    return null;}

resize() 數(shù)組擴(kuò)容

用于初始化數(shù)組或數(shù)組擴(kuò)容，每次擴(kuò)容后，容量為原來的 2 倍，并進(jìn)行數(shù)據(jù)遷移

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) { // 對(duì)應(yīng)數(shù)組擴(kuò)容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 將數(shù)組大小擴(kuò)大一倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 將閾值擴(kuò)大一倍
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // 對(duì)應(yīng)使用 new HashMap(int initialCapacity) 初始化后，第一次 put 的時(shí)候
        newCap = oldThr;
    else {// 對(duì)應(yīng)使用 new HashMap() 初始化后，第一次 put 的時(shí)候
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    // 用新的數(shù)組大小初始化新的數(shù)組
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab; // 如果是初始化數(shù)組，到這里就結(jié)束了，返回 newTab 即可

    if (oldTab != null) {
        // 開始遍歷原數(shù)組，進(jìn)行數(shù)據(jù)遷移。
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果該數(shù)組位置上只有單個(gè)元素，那就簡(jiǎn)單了，簡(jiǎn)單遷移這個(gè)元素就可以了
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是紅黑樹，具體我們就不展開了
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    // 這塊是處理鏈表的情況，
                    // 需要將此鏈表拆成兩個(gè)鏈表，放到新的數(shù)組中，并且保留原來的先后順序
                    // loHead、loTail 對(duì)應(yīng)一條鏈表，hiHead、hiTail 對(duì)應(yīng)另一條鏈表，代碼還是比較簡(jiǎn)單的
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        // 第一條鏈表
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 第二條鏈表的新的位置是 j + oldCap，這個(gè)很好理解
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;}

get()過程

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;}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) {
        // 判斷第一個(gè)節(jié)點(diǎn)是不是就是需要的
        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;}

2.5 其他方法

HashSet是對(duì)HashMap的簡(jiǎn)單包裝，其他還有迭代器等

3、總結(jié)

關(guān)于數(shù)組擴(kuò)容，從putVal源代碼中我們可以知道，當(dāng)插入一個(gè)元素的時(shí)候size就加1，若size大于threshold的時(shí)候，就會(huì)進(jìn)行擴(kuò)容。假設(shè)我們的capacity大小為32，loadFator為0.75，則threshold為24 = 32 * 0.75，此時(shí)，插入了25個(gè)元素，并且插入的這25個(gè)元素都在同一個(gè)桶中，桶中的數(shù)據(jù)結(jié)構(gòu)為紅黑樹，則還有31個(gè)桶是空的，也會(huì)進(jìn)行擴(kuò)容處理，其實(shí)此時(shí)，還有31個(gè)桶是空的，好像似乎不需要進(jìn)行擴(kuò)容處理，但是是需要擴(kuò)容處理的，因?yàn)榇藭r(shí)我們的capacity大小可能不適當(dāng)。我們前面知道，擴(kuò)容處理會(huì)遍歷所有的元素，時(shí)間復(fù)雜度很高；前面我們還知道，經(jīng)過一次擴(kuò)容處理后，元素會(huì)更加均勻的分布在各個(gè)桶中，會(huì)提升訪問效率。所以說盡量避免進(jìn)行擴(kuò)容處理，也就意味著，遍歷元素所帶來的壞處大于元素在桶中均勻分布所帶來的好處。

• HashMap在JDK1.8以前是一個(gè)鏈表散列這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)，而在JDK1.8以后是一個(gè)數(shù)組加鏈表加紅黑樹的數(shù)據(jù)結(jié)構(gòu)

• 通過源碼的學(xué)習(xí)，HashMap是一個(gè)能快速通過key獲取到value值得一個(gè)集合，原因是內(nèi)部使用的是hash查找值得方法

另外LinkedHashMap是HashMap的直接子類，二者唯一的區(qū)別是LinkedHashMap在HashMap的基礎(chǔ)上，采用雙向鏈表(doubly-linked list)的形式將所有**entry**連接起來，這樣是為保證元素的迭代順序跟插入順序相同

六、Collections工具類

1、概述

此類完全由在 collection 上進(jìn)行操作或返回 collection 的靜態(tài)方法組成。它包含在 collection 上操作的多態(tài)算法，即“包裝器”，包裝器返回由指定 collection 支持的新 collection，以及少數(shù)其他內(nèi)容。如果為此類的方法所提供的 collection 或類對(duì)象為 null，則這些方法都將拋出NullPointerException

2、排序常用方法

//反轉(zhuǎn)列表中元素的順序
static void reverse(List<?> list)
//對(duì)List集合元素進(jìn)行隨機(jī)排序
static void shuffle(List<?> list)
//根據(jù)元素的自然順序 對(duì)指定列表按升序進(jìn)行排序
static void sort(List<T> list)
//根據(jù)指定比較器產(chǎn)生的順序?qū)χ付斜磉M(jìn)行排序
static <T> void sort(List<T> list, Comparator<? super T> c)
//在指定List的指定位置i,j處交換元素
static void swap(List<?> list, int i, int j)
//當(dāng)distance為正數(shù)時(shí)，將List集合的后distance個(gè)元素“整體”移到前面；當(dāng)distance為負(fù)數(shù)時(shí)，將list集合的前distance個(gè)元素“整體”移到后邊。該方法不會(huì)改變集合的長(zhǎng)度
static void rotate(List<?> list, int distance)

3、查找、替換操作

//使用二分搜索法搜索指定列表，以獲得指定對(duì)象在List集合中的索引
//注意：此前必須保證List集合中的元素已經(jīng)處于有序狀態(tài)
static <T> int binarySearch(List<? extends Comparable<? super T>>list, T key)
//根據(jù)元素的自然順序，返回給定collection 的最大元素
static Object max(Collection coll)
//根據(jù)指定比較器產(chǎn)生的順序，返回給定 collection 的最大元素
static Object max(Collection coll,Comparator comp):
//根據(jù)元素的自然順序，返回給定collection 的最小元素
static Object min(Collection coll):
//根據(jù)指定比較器產(chǎn)生的順序，返回給定 collection 的最小元素
static Object min(Collection coll,Comparator comp):
//使用指定元素替換指定列表中的所有元素
static <T> void fill(List<? super T> list,T obj)
//返回指定co1lection中等于指定對(duì)象的出現(xiàn)次數(shù)
static int frequency(collection<?>c,object o)
//返回指定源列表中第一次出現(xiàn)指定目標(biāo)列表的起始位置；如果沒有出現(xiàn)這樣的列表，則返回-1
static int indexofsubList(List<?>source, List<?>target)
//返回指定源列表中最后一次出現(xiàn)指定目標(biāo)列表的起始位置；如果沒有出現(xiàn)這樣的列表，則返回-1
static int lastIndexofsubList(List<?>source,List<?>target)
//使用一個(gè)新值替換List對(duì)象的所有舊值o1dval
static <T> boolean replaceA1l(list<T> list,T oldval,T newval)

4、同步控制

Collectons提供了多個(gè)synchronizedXxx()方法，該方法可以將指定集合包裝成線程同步的集合，從而解決多線程并發(fā)訪問集合時(shí)的線程安全問題。正如前面介紹的HashSet，TreeSet，arrayList，LinkedList，HashMap，TreeMap都是線程不安全的。Collections提供了多個(gè)靜態(tài)方法可以把他們包裝成線程同步的集合。

//返回指定 Collection 支持的同步（線程安全的）collection
static <T> Collection<T> synchronizedCollection(Collection<T> c)
//返回指定列表支持的同步（線程安全的）列表
static <T> List<T> synchronizedList(List<T> list)
//返回由指定映射支持的同步（線程安全的）映射
static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)
//返回指定 set 支持的同步（線程安全的）set
static <T> Set<T> synchronizedSet(Set<T> s)

5、Collection設(shè)置不可變集合

//返回一個(gè)空的、不可變的集合對(duì)象，此處的集合既可以是List，也可以是Set，還可以是Map。
emptyXxx()
//返回一個(gè)只包含指定對(duì)象（只有一個(gè)或一個(gè)元素）的不可變的集合對(duì)象，此處的集合可以是：List，Set，Map。
singletonXxx():
//返回指定集合對(duì)象的不可變視圖，此處的集合可以是：List，Set，Map
unmodifiableXxx()

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Java集合框架是什么”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!