Java 數(shù)據(jù)結構

詳細請轉到@pdai的博客

1. 基本數(shù)據(jù)結構

1.1 數(shù)組 (Array)

數(shù)組的優(yōu)點:

• 存取速度快
  數(shù)組的缺點:
• 事先必須知道數(shù)組的長度
• 插入刪除元素很慢
• 空間通常是有限制的
• 需要大塊連續(xù)的內(nèi)存塊
• 插入刪除元素的效率很低

源碼分析：
1、底層數(shù)據(jù)結構是Object

 transient Object[] elementData;
 private int size;

2、構造函數(shù)包括無參構造和有參數(shù)構造，有參構造時指定構造大小，或者直接復制已有的

public ArrayList(int initialCapacity)
public ArrayList()
public ArrayList(Collection<? extends E> c)

其中復制方式，public ArrayList(Collection<? extends E> c)，底層實現(xiàn)是通過Arrays.copyof接口來實現(xiàn)的

 elementData = Arrays.copyOf(elementData, size, Object[].class);

3、擴容機制
默認情況下：
ArrayList的容量為10，是由以下參數(shù)決定的

private static final int DEFAULT_CAPACITY = 10;

擴容機制觸發(fā)條件：空間已滿
擴容大小：1.5倍
源碼調(diào)用路徑

其中，在add的時候，會調(diào)用 this.ensureCapacityInternal(this.size + 1);其中size+1是當前添加后的容量值，傳入ensureExplicitCapacity方法，源碼如下：

    private void ensureExplicitCapacity(int minCapacity) {
        ++this.modCount;
        //如果容量不足
        if (minCapacity - this.elementData.length > 0) {
            this.grow(minCapacity);
        }

這里可以看到容量不足時會調(diào)用 this.grow(minCapacity);
grow方式是最關鍵的方法

    private void grow(int minCapacity) {
        int oldCapacity = this.elementData.length;
        //擴容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        //如果超過這個大容量要單獨處理，return minCapacity > 2147483639 ? 2147483647 : 2147483639;
        if (newCapacity - 2147483639 > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
        //先把之前的copy過去
        this.elementData = Arrays.copyOf(this.elementData, newCapacity);
    }

擴完容之后就可以直接放入數(shù)據(jù)了

    public boolean add(E e) {
        this.ensureCapacityInternal(this.size + 1);
        this.elementData[this.size++] = e;
        return true;
    }

4、為什么remove性能不好
因為整體要平移，直接看源碼

public boolean remove(Object o) {
        int index;
        if (o == null) {
            for(index = 0; index < this.size; ++index) {
                if (this.elementData[index] == null) {
                    this.fastRemove(index);
                    return true;
                }
            }
        } else {
            for(index = 0; index < this.size; ++index) {
                if (o.equals(this.elementData[index])) {
                //效率較高的數(shù)組拷貝方式,調(diào)用了System.arraycopy，實際上是一種o(n)的復雜度快速改變索引的方式
                    this.fastRemove(index);
                    return true;
                }
            }
        }

        return false;
    }

整體平移的時候，通過一個for循環(huán)挨個執(zhí)行，時間復雜度是o(n)，加上this.fastRemove(index);是一種o(n)的拷貝方式，效率可想而知

5、其他API
indexOf(), lastIndexOf():獲取元素的第一次出現(xiàn)的index。
get()：獲取值
set()：設置值
addAll()：添加大部分數(shù)據(jù)
6、優(yōu)化：
在使用ArrayList時如果新增數(shù)據(jù)，后面逐漸刪除，會導致當前數(shù)組占用空間過大，無法清理，實際上里面只存儲了幾個數(shù)據(jù)的情況，因此，出現(xiàn)這種情況可以利用jdk提供的方法優(yōu)化：
trimToSize()：底層數(shù)組的容量調(diào)整為當前列表保存的實際元素的大小的功能，源碼如下：

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

1.2 鏈表 (Linked List)

LinkedList同時實現(xiàn)了List接口和Deque接口，也就是說它既可以看作一個順序容器，又可以看作一個隊列(Queue)，同時又可以看作一個棧(Stack)。這樣看來，LinkedList簡直就是個全能冠軍。當你需要使用?；蛘哧犃袝r，可以考慮使用LinkedList，一方面是因為Java官方已經(jīng)聲明不建議使用Stack類，更遺憾的是，Java里根本沒有一個叫做Queue的類(它是個接口名字)。關于?；蜿犃?，現(xiàn)在的首選是ArrayDeque，它有著比LinkedList(當作棧或隊列使用時)有著更好的性能。
整體上，這是一個雙向鏈表結構，在Linkedlist定義了三個數(shù)據(jù)

    transient int size;//當前數(shù)目
    transient LinkedList.Node<E> first;//指向鏈表的第一個
    transient LinkedList.Node<E> last;//指向鏈表的最后一個元素

這個鏈表的每個節(jié)點的數(shù)據(jù)結構

Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
this.item = element;//當前元素值
this.next = next;//后驅
this.prev = prev;//前驅
}

1、刪除為什么這么快
removeFirst(), removeLast(), remove(e), remove(index)
這些方法用的是

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

核心方法為unlink，這個方法實際上是改變x這個節(jié)點的前驅指向x的后驅，同時將x的指向都變成了null，實際上是個o(1)復雜度的代碼

 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; // GC
        size--;
        modCount++;
        return element;
    }

2、add為什么不需要擴容
改變指向就好了，可以無限增長
add(E e)、add(int index, E element)
3、get()效率比較低
查找操作的本質(zhì)是查找元素的下標，如源碼所示，會從first遍歷整個list，時間復雜度是o(n)；

 LinkedList.Node<E> node(int index) {
        LinkedList.Node x;
        int i;
        if (index < this.size >> 1) {
            x = this.first;

            for(i = 0; i < index; ++i) {
                x = x.next;
            }

            return x;
        } else {
            x = this.last;

            for(i = this.size - 1; i > index; --i) {
                x = x.prev;
            }

            return x;
        }
    }

4、其他API
getFirst(), getLast()
獲取第一個元素， 和獲取最后一個元素:
Queue 方法：
peek()：本質(zhì)上獲取第一個元素
poll()：本質(zhì)上將數(shù)據(jù)從第一個元素刪除，并獲取第一個元素
remove()：調(diào)用的是removeFirst()
offer(E e)：調(diào)用的是add(e)
element()：調(diào)用的是getFirst()

Deque 方法:
offerFirst(E e)：調(diào)用addFirst(e)
offerLast(E e)：調(diào)用addLast(e)
peekFirst()： 獲取fist節(jié)點的值
peekLast()：獲取last節(jié)點的值
pollFirst()：刪除第一個節(jié)點
pollLast()：刪除最后一個節(jié)點
push(E e)：添加作為第一個節(jié)點
pop()：彈出第一個節(jié)點

1.3 棧 (Stack)

棧本質(zhì)上是一個加了鎖的數(shù)組（Vector），通過定義規(guī)則的方式，實現(xiàn)了先進后出邏輯，但是這個Vector方法由于性能問題已經(jīng)算是個過時的接口，因此Stack也不再建議使用，這里不再多說，官方更建議將ArrayDeque來作為棧和隊列來使用。

1.4 隊列 (Queue)

雙向隊列

Deque是"double ended queue", 表示雙向的隊列，英文讀作"deck". Deque 繼承自 Queue接口,除了支持Queue的方法之外，還支持insert, remove和examine操作，由于Deque是雙向的，所以可以對隊列的頭和尾都進行操作，它同時也支持兩組格式，一組是拋出異常的實現(xiàn)；另外一組是返回值的實現(xiàn)(沒有則返回null)。
當把Deque當做FIFO的queue來使用時，元素是從deque的尾部添加，從頭部進行刪除的； 所以deque的部分方法是和queue是等同的。具體如下:

    //add調(diào)用的方法添加元素到尾部
    public void addLast(E e) {
        if (e == null) {
            throw new NullPointerException();
        } else {
            this.elements[this.tail] = e;
            if ((this.tail = this.tail + 1 & this.elements.length - 1) == this.head) {
                this.doubleCapacity();
            }

        }
    }
    //poll調(diào)用的方法，從頭部獲取元素
    public E pollFirst() {
        int h = this.head;
        E result = this.elements[h];
        if (result == null) {
            return null;
        } else {
            this.elements[h] = null;
            this.head = h + 1 & this.elements.length - 1;
            return result;
        }
    }

ArrayDeque和LinkedList是Deque的兩個通用實現(xiàn)，由于官方更推薦使用AarryDeque用作棧和隊列，只是底層的數(shù)據(jù)結構不一樣，一個循環(huán)數(shù)組，一個是雙向鏈表。
在這個循環(huán)數(shù)組中，為了滿足可以同時在數(shù)組兩端插入或刪除元素的需求，數(shù)組的任何一點都可能被看作起點或者終點。

優(yōu)先級隊列

這個優(yōu)先級隊列實際上是一個滿足堆特性的數(shù)組結構。默認情況下是個小頂堆。
可以改為大頂堆

 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

在介紹PriorityQueue之前首先需要明確樹結構與數(shù)組結構的關系：

leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2

對于數(shù)組來說需要了解其初始與擴容機制

int newCapacity = oldCapacity + (oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1);

oldCapacity < 64 判斷：如果當前容量小于 64，那么使用 oldCapacity + 2 作為新容量。這是為了在數(shù)組容量較小時，提供一些額外的空間，以避免頻繁擴容。
oldCapacity >= 64 判斷：如果當前容量大于等于 64，那么使用 oldCapacity >> 1（相當于 oldCapacity / 2）作為新容量。這是為了在容量較大時，以較小的步長逐漸擴容，降低擴容的速度。1.5倍

2. 樹形數(shù)據(jù)結構

2.1 二叉樹 (Binary Tree)

TreeMap(紅黑樹的Map結構)

2.2 堆 (Heap)

PriorityQueue，默認小頂堆
可以改為大頂堆

 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

3. 散列數(shù)據(jù)結構

3.1 哈希表 (Hash Map)

HashMap實現(xiàn)了Map接口，即允許放入key為null的元素，也允許插入value為null的元素；除該類未實現(xiàn)同步外，其余跟Hashtable大致相同；跟TreeMap不同，該容器不保證元素順序，根據(jù)需要該容器可能會對元素重新哈希，元素的順序也會被重新打散，因此不同時間迭代同一個HashMap的順序可能會不同。 根據(jù)對沖突的處理方式不同，哈希表有兩種實現(xiàn)方式，一種開放地址方式(Open addressing)，另一種是沖突鏈表方式(Separate chaining with linked lists)。
resize() 方法用于初始化數(shù)組或數(shù)組擴容，每次擴容后，容量為原來的 2 倍，并進行數(shù)據(jù)遷移。
Java8 對 HashMap 進行了一些修改，最大的不同就是利用了紅黑樹，所以其由 數(shù)組+鏈表+紅黑樹 組成。
根據(jù) Java7 HashMap 的介紹，我們知道，查找的時候，根據(jù) hash 值我們能夠快速定位到數(shù)組的具體下標，但是之后的話，需要順著鏈表一個個比較下去才能找到我們需要的，時間復雜度取決于鏈表的長度，為 O(n)。為了降低這部分的開銷，在 Java8 中，當鏈表中的元素達到了 8 個時，會將鏈表轉換為紅黑樹，在這些位置進行查找的時候可以降低時間復雜度為 O(logN)。

插入：
put(K key, V value)方法是將指定的key, value對添加到map里。該方法首先會對map做一次查找，看是否包含該元組，如果已經(jīng)包含則直接返回，查找過程類似于getEntry()方法；如果沒有找到，則會通過addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry，插入方式為頭插法。
resize() 方法用于初始化數(shù)組或數(shù)組擴容，每次擴容后，容量為原來的 2 倍，并進行數(shù)據(jù)遷移。
刪除：
remove(Object key)的作用是刪除key值對應的entry，該方法的具體邏輯是在removeEntryForKey(Object key)里實現(xiàn)的。removeEntryForKey()方法會首先找到key值對應的entry，然后刪除該entry(修改鏈表的相應引用)。查找過程跟getEntry()過程類似。

獲取：
計算 key 的 hash 值，根據(jù) hash 值找到對應數(shù)組下標: hash & (length-1)判斷數(shù)組該位置處的元素是否剛好就是我們要找的，如果不是，走第三步判斷該元素類型是否是 TreeNode，如果是，用紅黑樹的方法取數(shù)據(jù)，如果不是，走第四步遍歷鏈表，直到找到相等(==或equals)的 key

3.2 LinkedHashMap

LinkedHashMap 是 Java 中的一個集合類，它是 HashMap 的子類。與普通的 HashMap 不同，LinkedHashMap 保留了元素插入的順序。它使用一個雙向鏈表來維護元素的順序，該鏈表連接了所有的元素。因此，當你迭代 LinkedHashMap 時，元素的順序與插入順序一致。
1、保留插入順序： LinkedHashMap 會按照元素插入的順序來維護元素的順序，這是通過內(nèi)部的雙向鏈表實現(xiàn)的。
2、性能類似于 HashMap： 在大多數(shù)操作上，LinkedHashMap 的性能與 HashMap 類似。它使用哈希表來實現(xiàn)快速的查找、插入和刪除操作。
3、迭代順序： 迭代 LinkedHashMap 的時候，元素的順序是按照插入的順序。這與 HashMap 不同，后者的迭代順序是不確定的。
4、支持 LRU 緩存策略： LinkedHashMap 提供了一個構造函數(shù)，允許你創(chuàng)建一個有限容量的 LinkedHashMap，當達到容量上限時，會根據(jù)最近最少使用的原則刪除最不經(jīng)常使用的元素。

3.3 TreeMap

轉載TreeMap 源碼解析
TreeMap實現(xiàn)了SortedMap接口，也就是說會按照key的大小順序對Map中的元素進行排序，key大小的評判可以通過其本身的自然順序(natural ordering)，也可以通過構造時傳入的比較器(Comparator)。
TreeMap底層通過紅黑樹(Red-Black tree)實現(xiàn)，也就意味著containsKey(), get(), put(), remove()都有著log(n)的時間復雜度。

補充：
紅黑樹：
紅黑樹是一種近似平衡的二叉查找樹，它能夠確保任何一個節(jié)點的左右子樹的高度差不會超過二者中較低那個的一倍。具體來說，紅黑樹是滿足如下條件的二叉查找樹(binary search tree):
1、每個節(jié)點要么是紅色，要么是黑色。
3、根節(jié)點必須是黑色
4、紅色節(jié)點不能連續(xù)(也即是，紅色節(jié)點的孩子和父親都不能是紅色)。
5、對于每個節(jié)點，從該點至null(樹尾端)的任何路徑，都含有相同個數(shù)的黑色節(jié)點。

左旋(Rotate Left)：
左旋的過程是將x的右子樹繞x逆時針旋轉，使得x的右子樹成為x的父親，同時修改相關節(jié)點的引用。旋轉之后，二叉查找樹的屬性仍然滿足。

左旋代碼：

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

右旋：右旋的過程是將x的左子樹繞x順時針旋轉，使得x的左子樹成為x的父親，同時修改相關節(jié)點的引用。旋轉之后，二叉查找樹的屬性仍然滿足。

TreeMap中右旋代碼如下:

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

get方法：
get(Object key)方法根據(jù)指定的key值返回對應的value，該方法調(diào)用了getEntry(Object key)得到相應的entry，然后返回entry.value。因此getEntry()是算法的核心。算法思想是根據(jù)key的自然順序(或者比較器順序)對二叉查找樹進行查找，直到找到滿足k.compareTo(p.key) == 0的entry。

final Entry<K,V> getEntry(Object key) {
    ......
    if (key == null)//不允許key值為null
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然順序
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)//向左找
            p = p.left;
        else if (cmp > 0)//向右找
            p = p.right;
        else
            return p;
    }
    return null;
}

put()方法：
put(K key, V value)方法是將指定的key, value對添加到map里。該方法首先會對map做一次查找，看是否包含該元組，如果已經(jīng)包含則直接返回，查找過程類似于getEntry()方法；如果沒有找到則會在紅黑樹中插入新的entry，如果插入之后破壞了紅黑樹的約束條件，還需要進行調(diào)整(旋轉，改變某些節(jié)點的顏色)。

public V put(K key, V value) {
	......
    int cmp;
    Entry<K,V> parent;
    if (key == null)
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然順序
    do {
        parent = t;
        cmp = k.compareTo(t.key);
        if (cmp < 0) t = t.left;//向左找
        else if (cmp > 0) t = t.right;//向右找
        else return t.setValue(value);
    } while (t != null);
    Entry<K,V> e = new Entry<>(key, value, parent);//創(chuàng)建并插入新的entry
    if (cmp < 0) parent.left = e;
    else parent.right = e;
    fixAfterInsertion(e);//調(diào)整
    size++;
    return null;
}

上述代碼的插入部分并不難理解: 首先在紅黑樹上找到合適的位置，然后創(chuàng)建新的entry并插入(當然，新插入的節(jié)點一定是樹的葉子)。難點是調(diào)整函數(shù)fixAfterInsertion()，前面已經(jīng)說過，調(diào)整往往需要1.改變某些節(jié)點的顏色，2.對某些節(jié)點進行旋轉。

ConcurrentHashMap詳解

JDK1.7之前的ConcurrentHashMap使用分段鎖機制實現(xiàn)，JDK1.8則使用數(shù)組+鏈表+紅黑樹數(shù)據(jù)結構和CAS原子操作實現(xiàn)ConcurrentHashMap；本文將分別介紹這兩種方式的實現(xiàn)方案及其區(qū)別。

ConcurrentHashMap - JDK 1.7

ConcurrentHashMap在對象中保存了一個Segment數(shù)組，即將整個Hash表劃分為多個分段；而每個Segment元素，即每個分段則類似于一個Hashtable；這樣，在執(zhí)行put操作時首先根據(jù)hash算法定位到元素屬于哪個Segment，然后對該Segment加鎖即可。因此，ConcurrentHashMap在多線程并發(fā)編程中可是實現(xiàn)多線程put操作。
Segment 通過繼承 ReentrantLock 來進行加鎖，所以每次需要加鎖的操作鎖住的是一個 segment，這樣只要保證每個 Segment 是線程安全的，也就實現(xiàn)了全局的線程安全。
ConcurrentHashMap 有 16 個 Segments，所以理論上，這個時候，最多可以同時支持 16 個線程并發(fā)寫。

初始化：
loadFactor: 負載因子，是 0.75，得出初始閾值為 1.5，也就是以后插入第一個元素不會觸發(fā)擴容，插入第二個會進行第一次擴容
initialCapacity: 初始容量

并發(fā)問題安全性：
put 操作的線程安全性。
使用了 CAS 來初始化 Segment 中的數(shù)組。添加節(jié)點到鏈表的操作是插入到表頭的，所以，如果這個時候 get 操作在鏈表遍歷的過程已經(jīng)到了中間，是不會影響的。
當然，另一個并發(fā)問題就是 get 操作在 put 之后，需要保證剛剛插入表頭的節(jié)點被讀取，這個依賴于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject。
擴容。擴容是新創(chuàng)建了數(shù)組，然后進行遷移數(shù)據(jù)，最后面將 newTable 設置給屬性 table。所以，如果 get 操作此時也在進行，那么也沒關系，如果 get 先行，那么就是在舊的 table 上做查詢操作；而 put 先行，那么 put 操作的可見性保證就是 table 使用了 volatile 關鍵字。
remove 操作的線程安全性。
get 操作需要遍歷鏈表，但是 remove 操作會"破壞"鏈表。如果 remove 破壞的節(jié)點 get 操作已經(jīng)過去了，那么這里不存在任何問題。如果 remove 先破壞了一個節(jié)點，分兩種情況考慮。
1、如果此節(jié)點是頭節(jié)點，那么需要將頭節(jié)點的 next 設置為數(shù)組該位置的元素，table 雖然使用了 volatile 修飾，但是 volatile 并不能提供數(shù)組內(nèi)部操作的可見性保證，所以源碼中使用了 UNSAFE 來操作數(shù)組，請看方法 setEntryAt。
2、如果要刪除的節(jié)點不是頭節(jié)點，它會將要刪除節(jié)點的后繼節(jié)點接到前驅節(jié)點中，這里的并發(fā)保證就是 next 屬性是 volatile 的。

ConcurrentHashMap - JDK 1.8

在JDK1.8中，ConcurrentHashMap選擇了與HashMap類似的數(shù)組+鏈表+紅黑樹的方式實現(xiàn)，而加鎖則采用CAS和synchronized實現(xiàn)。

4. 并發(fā)數(shù)據(jù)結構（JUC集合）

4.1 ConcurrentHashMap

4.2 CopyOnWriteArrayList

CopyOnWriteArrayList實現(xiàn)了List接口，List接口定義了對列表的基本操作；同時實現(xiàn)了RandomAccess接口，表示可以隨機訪問(數(shù)組具有隨機訪問的特性)；同時實現(xiàn)了Cloneable接口，表示可克??；同時也實現(xiàn)了Serializable接口，表示可被序列化。

CopyOnWriteArrayList 是 Java 中并發(fā)編程提供的線程安全的集合類之一，它的特點是在進行寫操作時會創(chuàng)建一個新的復制（copy）來保證線程安全。以下是 CopyOnWriteArrayList 的主要原理和特點：
1、寫時復制： 當有寫操作（如添加、刪除元素）發(fā)生時，CopyOnWriteArrayList 會創(chuàng)建一個新的數(shù)組（復制原數(shù)組），在新數(shù)組上執(zhí)行寫操作，然后將新數(shù)組替換原來的數(shù)組。這樣可以確保寫操作不會影響正在進行的讀操作，因為讀操作仍然在原數(shù)組上進行。
2、讀操作不需要加鎖： 由于讀操作不涉及修改集合內(nèi)容，而是在不變的原數(shù)組上進行，因此讀操作不需要加鎖。這使得在讀多寫少的場景中，CopyOnWriteArrayList 的性能相對較好。
3、適用于讀多寫少的場景： CopyOnWriteArrayList 的設計適用于那些讀操作頻繁，而寫操作相對較少的場景。這是因為在寫時需要進行數(shù)組復制，可能會引起一些性能開銷。
4、弱一致性： CopyOnWriteArrayList 提供的是弱一致性，即在寫操作完成后，對于讀操作來說，并不一定能立即看到最新的修改。這是因為讀操作仍然可能在舊數(shù)組上進行，直到寫操作完成并新數(shù)組替換了舊數(shù)組。
5、不支持并發(fā)修改的迭代器： 由于寫操作會創(chuàng)建新的數(shù)組，舊數(shù)組上的迭代器可能會拋出 ConcurrentModificationException 異常。因此，CopyOnWriteArrayList 的迭代器是不支持并發(fā)修改的。

CopyOnWriteArrayList的缺陷和使用場景CopyOnWriteArrayList 有幾個缺點：由于寫操作的時候，需要拷貝數(shù)組，會消耗內(nèi)存，如果原數(shù)組的內(nèi)容比較多的情況下，可能導致young gc或者full gc不能用于實時讀的場景，像拷貝數(shù)組、新增元素都需要時間，所以調(diào)用一個set操作后，讀取到數(shù)據(jù)可能還是舊的,雖然CopyOnWriteArrayList 能做到最終一致性,但是還是沒法滿足實時性要求；
CopyOnWriteArrayList 合適讀多寫少的場景，不過這類慎用因為誰也沒法保證CopyOnWriteArrayList 到底要放置多少數(shù)據(jù)，萬一數(shù)據(jù)稍微有點多，每次add/set都要重新復制數(shù)組，這個代價實在太高昂了。在高性能的互聯(lián)網(wǎng)應用中，這種操作分分鐘引起故障。

4.3 ConcurrentLinkedQueue

ConcurerntLinkedQueue一個基于鏈接節(jié)點的無界線程安全隊列。此隊列按照 FIFO(先進先出)原則對元素進行排序。隊列的頭部是隊列中時間最長的元素。隊列的尾部 是隊列中時間最短的元素。新的元素插入到隊列的尾部，隊列獲取操作從隊列頭部獲得元素。當多個線程共享訪問一個公共 collection 時，ConcurrentLinkedQueue是一個恰當?shù)倪x擇。此隊列不允許使用null元素。

ConcurrentLinkedQueue 是 Java 中并發(fā)編程提供的線程安全的隊列實現(xiàn)。它基于非阻塞算法，使用 CAS（Compare and Swap）等原子操作來確保線程安全。以下是 ConcurrentLinkedQueue 的主要特點和原理：
非阻塞算法： ConcurrentLinkedQueue 使用非阻塞算法，避免了使用鎖的情況，因此具有較好的并發(fā)性能。它通過 CAS 操作等方式來保證多個線程可以同時進行讀和寫操作。

1、無界隊列： ConcurrentLinkedQueue 是無界隊列，它沒有固定的容量限制。可以不受限制地添加元素。
2、基于鏈表： 內(nèi)部使用單向鏈表來組織隊列元素。新的元素總是被添加到隊列的尾部，而移除元素則發(fā)生在隊列的頭部。
3、線程安全的入隊和出隊操作： ConcurrentLinkedQueue 提供了線程安全的入隊（offer和add）和出隊（poll和remove）操作。這意味著多個線程可以同時進行這些操作而不需要額外的同步。
4、迭代器支持弱一致性： ConcurrentLinkedQueue 的迭代器是弱一致性的，它不會拋出 ConcurrentModificationException 異常。因此，迭代器可能看到隊列的部分修改，而不一定是最新狀態(tài)。
5、適用于生產(chǎn)者-消費者模型： ConcurrentLinkedQueue 在生產(chǎn)者-消費者模型中是一個常用的選擇，特別是當多個線程并發(fā)地生產(chǎn)和消費元素時。

4.4 BlockingQueue

BlockingQueue大家族有哪些? ArrayBlockingQueue, DelayQueue, LinkedBlockingQueue, SynchronousQueue…
BlockingQueue 通常用于一個線程生產(chǎn)對象，而另外一個線程消費這些對象的場景。
一個線程將會持續(xù)生產(chǎn)新對象并將其插入到隊列之中，直到隊列達到它所能容納的臨界點。也就是說，它是有限的。如果該阻塞隊列到達了其臨界點，負責生產(chǎn)的線程將會在往里邊插入新對象時發(fā)生阻塞。它會一直處于阻塞之中，直到負責消費的線程從隊列中拿走一個對象。
負責消費的線程將會一直從該阻塞隊列中拿出對象。如果消費線程嘗試去從一個空的隊列中提取對象的話，這個消費線程將會處于阻塞之中，直到一個生產(chǎn)線程把一個對象丟進隊列。

ArrayBlockingQueue:

基于數(shù)組的阻塞隊列實現(xiàn)。
有界隊列，必須指定容量。
使用獨占鎖實現(xiàn)線程安全。

BlockingQueue<Integer> arrayBlockingQueue = new ArrayBlockingQueue<>(10);

LinkedBlockingQueue:

基于鏈表的阻塞隊列實現(xiàn)。
可以選擇有界或無界。
如果不指定容量，默認是無界隊列。
使用兩個鎖（讀鎖和寫鎖）實現(xiàn)線程安全。

BlockingQueue<String> linkedBlockingQueue = new LinkedBlockingQueue<>();

PriorityBlockingQueue:

一個支持優(yōu)先級的無界阻塞隊列。
元素按照它們的自然順序或者根據(jù)構造函數(shù)中提供的比較器來進行排序。
不保證同優(yōu)先級元素的順序。

BlockingQueue<Task> priorityBlockingQueue = new PriorityBlockingQueue<>();

DelayQueue:

用于存放實現(xiàn)了 Delayed 接口的元素，這些元素只能在其指定的延遲時間過后才能被消費。
通常用于定時任務調(diào)度。

BlockingQueue<DelayedTask> delayQueue = new DelayQueue<>();

SynchronousQueue:

一個不存儲元素的阻塞隊列。
生產(chǎn)者線程必須等待消費者線程取走元素，反之亦然。
用于直接傳遞任務或數(shù)據(jù)，通常在生產(chǎn)者和消費者線程之間進行交互。文章來源地址http://www.zghlxwxcb.cn/news/detail-821635.html

BlockingQueue<String> synchronousQueue = new SynchronousQueue<>();

到了這里，關于Java 數(shù)據(jù)結構集合的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！