package java.util;
// 繼承了 Iterable，意味著所有 Collection 實(shí)現(xiàn)類都可以使用 for-each 循環(huán)
public interface Collection<E> extends Iterable<E> {
    // .......
}

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 默認(rèn)初始容量
    private static final int DEFAULT_CAPACITY = 10;
    // 共享的空數(shù)組實(shí)列
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //默認(rèn)大小的空數(shù)組實(shí)列
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 用于存儲(chǔ)元素的數(shù)組緩沖區(qū)。ArrayList 的容量就是這個(gè)數(shù)組的長度。
    // transient 關(guān)鍵字表示該字段不會(huì)被序列化
    transient Object[] elementData;
    // ArrayList 中包含的元素?cái)?shù)量
    private int size;
    // ..........
}

public ArrayList(){
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//JDK 1.6
public ArrayList() {
        this(10); // 直接調(diào)用帶容量的構(gòu)造函數(shù)，傳入 10
}
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    this.elementData = new Object[initialCapacity]; // 立即創(chuàng)建一個(gè)長度為 10 的數(shù)組
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 如果初始容量大于0，創(chuàng)建對應(yīng)大小的Object數(shù)組
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 如果初始容量為0，使用預(yù)定義的空數(shù)組常量
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 如果初始容量為負(fù)數(shù)，拋出非法參數(shù)異常
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

public ArrayList(Collection<? extends E> c) {
    // 使用Collection的toArray()方法將傳入的集合轉(zhuǎn)換為數(shù)組
    Object[] a = c.toArray();
    // 將數(shù)組長度賦值給 size,同時(shí)判斷數(shù)組長度是否為0
    // 如果數(shù)組長度不等于 0,則向下繼續(xù)執(zhí)行
    // 否則，就使用預(yù)定義的空數(shù)組EMPTY_ELEMENTDATA
    if ((size = a.length) != 0) {
        //判斷集合本身是否是ArrayList
        //如果是，就直接使用其內(nèi)部數(shù)組（elementData）
        //否則，使用Arrays.copyOf()創(chuàng)建一個(gè)新的數(shù)組副本
        //其目的是為了保證新創(chuàng)建的ArrayList的內(nèi)部數(shù)組完全獨(dú)立，不受原集合影響
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        elementData = EMPTY_ELEMENTDATA;
    }
}

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 關(guān)鍵：檢查容量是否足夠
    elementData[size++] = e; // 將元素放入數(shù)組，并增加 size
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // 如果elementData 是否是默認(rèn)的空數(shù)組
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果是，則將最小容量設(shè)置為默認(rèn)容量(10)和請求容量中的較大值
        // 確保了第一次添加元素時(shí)，數(shù)組至少有10個(gè)元素的空間
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

 private void ensureExplicitCapacity(int minCapacity) {
    // 修改計(jì)數(shù)器，用于迭代器的快速失敗機(jī)制
    // 快速失敗機(jī)制（fail-fast）:是一種錯(cuò)誤檢測機(jī)制。當(dāng)在迭代過程中，
    // 如果檢測到集合結(jié)構(gòu)被修改（非迭代器自身的方法導(dǎo)致的修改）                                                               
    // 迭代器會(huì)立即拋出ConcurrentModificationException異常，
    // 而不是繼續(xù)執(zhí) 行可能導(dǎo)致不確定行為。
    modCount++;
    // 檢查是否需要擴(kuò)容 (所需最小容量大于當(dāng)前數(shù)組的長度)
    if (minCapacity - elementData.length > 0) 
        // 執(zhí)行擴(kuò)容操作 grow(int minCapacity)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    // 舊容量      
    int oldCapacity = elementData.length; 
    // 新容量 = 舊容量 + 舊容量/2 (即 1.5 倍)
    int newCapacity = oldCapacity + (oldCapacity >> 1); 
    // 如果 1.5 倍后還不夠，就用所需的最小容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 處理極端情況，防止新容量超過 Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 關(guān)鍵：復(fù)制數(shù)組
    elementData = Arrays.copyOf(elementData, newCapacity);
}

public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}
public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}
public synchronized void removeAllElements() {
    modCount++;
    // Let gc do its work
    for (int i = 0; i < elementCount; i++)
        elementData[i] = null;
    elementCount = 0;
}
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    return elementData(index);
}
public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);
    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
    elementData[--elementCount] = null; // Let gc do its work
    return oldValue;
}
//...........

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    protected Object[] elementData; // 存儲(chǔ)元素的數(shù)組
    protected int elementCount; // 實(shí)際元素?cái)?shù)量（相當(dāng)于 ArrayList 中的 size）
    protected int capacityIncrement; // 容量增長系數(shù)
    private static final long serialVersionUID = -2767605614048989439L;
    // 定義一個(gè)數(shù)組理論上的最大容量上限
    // 注意：這個(gè) 8 不是一個(gè)魔法數(shù)字，它是基于對主流 JVM 實(shí)現(xiàn)對象內(nèi)存布局的經(jīng)驗(yàn)值。
    // 它足夠大，可以覆蓋大多數(shù)虛擬機(jī)中數(shù)組對象的額外開銷。
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 
    //...........
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // 獲取當(dāng)前數(shù)組容量 
    // 計(jì)算新容量 newCapacity：
    // 如果設(shè)置了capacityIncrement（擴(kuò)容增量），則新容量 = 舊容量 + capacityIncrement
    // 如果沒有設(shè)置capacityIncrement（默認(rèn)為0），則新容量 = 舊容量的2倍
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
    // 檢查新容量是否滿足最小需求，如果不滿足則使用minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 檢查新容量是否超過最大數(shù)組限制（MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8）
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 使用Arrays.copyOf創(chuàng)建新數(shù)組并復(fù)制原有元素
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static class Node<E> {
    E item; // 存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)
    Node<E> next; // 指向下一個(gè)節(jié)點(diǎn)的引用
    Node<E> prev; // 指向上一個(gè)節(jié)點(diǎn)的引用
    // 構(gòu)造函數(shù)：建立車廂之間的連接
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element; // 設(shè)置當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
        this.next = next; // 設(shè)置下一個(gè)節(jié)點(diǎn)
        this.prev = prev; // 設(shè)置上一個(gè)節(jié)點(diǎn)
    }
}

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0; // 記錄LinkedList中元素的數(shù)量，初始化為0，表示空鏈表
    transient Node<E> first; // 頭指針，指向鏈表的第一個(gè)節(jié)點(diǎn)，若鏈表為空則為 null
    transient Node<E> last; // 尾指針，指向鏈表的最后一個(gè)節(jié)點(diǎn)，若鏈表為空則為 null
    //........
}

public E get(int index) {
    // 檢查傳入索引是否有效
    checkElementIndex(index); 
    // 如果索引有效，調(diào)用 node(int index) 方法找到對應(yīng)索引得節(jié)點(diǎn)，并返回找到的節(jié)點(diǎn)的 item 字段
    return node(index).item; 
}
private void checkElementIndex(int index) {
    // 檢查傳入索引是否有效（即在指定范圍內(nèi)），無效則拋出IndexOutOfBoundsException的異常
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
    // 判斷索引是否在0到size-1范圍內(nèi)
    return index >= 0 && index < size;
}
Node<E> node(int index) {
    // 根據(jù)索引與鏈表長度的關(guān)系決定是從頭開始遍歷還是從尾開始遍歷，以提高查找效率
    // 如果index小于size的一半(size >> 1 (size/2))
    if (index < (size >> 1)) {
        Node<E> x = first;  // 從頭節(jié)點(diǎn)開始
        for (int i = 0; i < index; i++) // 向后遍歷index次
            x = x.next;
        return x;
    // 否則從last節(jié)點(diǎn)開始向前遍歷
    } else {
        Node<E> x = last; // 從尾節(jié)點(diǎn)開始
        for (int i = size - 1; i > index; i--)  // 向前遍歷(size-1-index)次
            x = x.prev;
        return x;
    }
}

public void addFirst(E e){
    linkFirst(e); // 將實(shí)際元素 e 鏈接到列表開頭
}
public void linkFirst(E e){
    // 保存當(dāng)前頭節(jié)點(diǎn)的引用
    final Node<E> f = first; 
    // 創(chuàng)建新的節(jié)點(diǎn)，它的 prev 是 null，next 是舊的頭節(jié)點(diǎn) f
    final Node<E> newNode = new Node<>(null, e, f); 
    // 讓 first 指針指向新節(jié)點(diǎn)，新節(jié)點(diǎn)成為新的頭
    first = newNode;
    // 處理邊界情況：如果鏈表原來為空
    if (f == null)
        // 鏈表為空時(shí)，新節(jié)點(diǎn)既是頭也是尾
        last = newNode;
    else
        // 如果鏈表不為空，讓舊頭節(jié)點(diǎn)的 prev 指向新節(jié)點(diǎn)
        f.prev = newNode;
    size++; // 增加 size 大小
    modCount++; // 修改計(jì)數(shù)器，用于快速失敗
}
public void addLast(E e){
    linkLast(e); // 將實(shí)際元素 e 鏈接到列表尾部
}
void linkLast(E e){
    // 保存當(dāng)前尾部節(jié)點(diǎn)的引用
    final Node<E> f = last;
    // 創(chuàng)建新的節(jié)點(diǎn)，它的 prev 是 舊的尾部節(jié)點(diǎn) l，next 是 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 讓 last 指針指向新節(jié)點(diǎn)，新節(jié)點(diǎn)成為新的尾部
    last = newNode;
    // 處理邊界情況：如果鏈表原來為空
    if (l == null)
        // 鏈表為空時(shí)，新節(jié)點(diǎn)既是頭也是尾
        first= newNode;
    else
        // 如果鏈表不為空，讓舊尾部節(jié)點(diǎn)的 next 指向新節(jié)點(diǎn)
        l.next= newNode;
    size++; // 增加 size 大小
    modCount++; // 修改計(jì)數(shù)器，用于快速失敗
}

public void add(int index, E element){
    // 檢查索引是否越界
    checkPositionIndex(index);
    // 如果插入位置是末尾
    if(index == size)
        linkLast(element); //調(diào)用linkLast 方法添加至尾部
    else
        linkBefore(element,node(index)); // 否則，在指定節(jié)點(diǎn)前插入
}
private void checkPositionIndex(int index){
    // 檢查傳入索引是否有效（即在指定范圍內(nèi)），無效則拋出IndexOutOfBoundsException異常
    if(!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index){
    // 判斷索引是否在0到size范圍內(nèi)
    return index >= 0 && index <= size;
}
void linkBefore(E e, Node<E> succ){
    // 獲取目標(biāo)節(jié)點(diǎn) succ 的前驅(qū)節(jié)點(diǎn)
    final Node<E> pred = succ.prev;
    // 創(chuàng)建新節(jié)點(diǎn)newNode，設(shè)置其前驅(qū)為pred，后繼為succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 更新succ的前驅(qū)指針指向newNode
    succ.prev = newNode;
    // 目標(biāo)節(jié)點(diǎn) succ 的前驅(qū)節(jié)點(diǎn) pred 是否為null，判斷是否在鏈表頭部插入
    if (pred == null)
        first = newNode; // 如果pred為null，說明succ是第一個(gè)節(jié)點(diǎn)，需要更新first指針
    else
        pred.next = newNode; // 否則，更新pred的后繼指針指向newNode
    size++; // 增加鏈表大小size
    modCount++; // 修改計(jì)數(shù)modCount，用于快速失敗
}

public E removeFirst(){
    // 獲取鏈表頭節(jié)點(diǎn)，并用 final 修飾，確保引用不會(huì)被改變
    final Node<E> f = first; 
    // 檢查鏈表是否為空
    //如果為空（first為null），拋出NoSuchElementException異常
    if (f == null) 
        throw new NoSuchElementException(); 
    //調(diào)用unlinkFirst方法實(shí)際執(zhí)行刪除操作，返回被刪除節(jié)點(diǎn)的值
    return unlinkFirst(f); 
}
private E unlinkFirst(Node<E> f){
    // 保存要?jiǎng)h除節(jié)點(diǎn)的元素值
    final E element = f.item; 
    // 保存下一個(gè)節(jié)點(diǎn)的引用
    final Node<E> next = f.next;
    // 清空當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
    // 顯式地將引用置為null可以幫助垃圾回收器更快回收內(nèi)存
    f.item = null;
    f.next = null; // help GC
    // 將鏈表的first指針指向下一個(gè)節(jié)點(diǎn)
    first = next;
    // 如果下一個(gè)節(jié)點(diǎn)為null，說明鏈表現(xiàn)在為空
    if (next == null)
        last = null;
    // 否則將下一個(gè)節(jié)點(diǎn)的前驅(qū)指針設(shè)為null
    else
        next.prev = null;
    // 更新鏈表大小和修改次數(shù)
    size--;
    modCount++;
    // 返回被刪除節(jié)點(diǎn)的元素值
    return element;
}
public E removeLast(){
    // 獲取鏈表尾節(jié)點(diǎn)，并用 final 修飾，確保引用不會(huì)被改變
    final Node<E> l = last;
    // 檢查鏈表是否為空
    //如果為空（last為null），拋出NoSuchElementException異常
    if (l == null)
        throw new NoSuchElementException();
    //調(diào)用unlinkLast方法實(shí)際執(zhí)行刪除操作，返回被刪除節(jié)點(diǎn)的值
    return unlinkLast(l); 
}
private E unlinkLast(Node<E> l){
    // 保存要?jiǎng)h除節(jié)點(diǎn)的值
    final E element = l.item;
    // 保存前一個(gè)節(jié)點(diǎn)的引用
    final Node<E> prev = l.prev;
    // 清空當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
    // 顯式地將引用置為null可以幫助垃圾回收器更快回收內(nèi)存
    l.item = null;
    l.prev = null; // help GC
    // 將鏈表的last指針指向上一個(gè)節(jié)點(diǎn)
    last = prev;
    // 如果上一個(gè)節(jié)點(diǎn)為null，說明鏈表現(xiàn)在為空
    if (prev == null)
        first = null;
    // 否則將上一個(gè)節(jié)點(diǎn)的后繼指針設(shè)為null
    else
        prev.next = null;
    // 更新鏈表大小和修改次數(shù)
    size--;
    modCount++;
     // 返回被刪除節(jié)點(diǎn)的元素值
    return element;
}

public E remove(int index){
     檢查索引是否有效
     checkElementIndex(index);
     // 調(diào)用 unlink 方法刪除指定位置元素，并返回刪除元素的值
     return unlink(node(index));
}
private void checkElementIndex(int index){
    // 檢查傳入索引是否有效（即在指定范圍內(nèi)），無效則拋出IndexOutOfBoundsException的異常
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
    // 判斷索引是否在0到size-1范圍內(nèi)
    return index >= 0 && index < size;
}
E unlink(Node<E> x){
    // assert x != null;
    // 保存刪除目標(biāo)元素 x及元素本身的前驅(qū)和后繼引用,使用final修飾，確保引用不會(huì)被修改
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    // 如果前驅(qū)節(jié)點(diǎn)為null，說明要移除的是頭節(jié)點(diǎn)，則將first指針指向后繼節(jié)點(diǎn)next
    if (prev == null) {
        first = next;
    // 否則，則將前驅(qū)節(jié)點(diǎn)的next指針指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)next，并斷開當(dāng)前節(jié)點(diǎn)與前驅(qū)節(jié)點(diǎn)的連接
    } else {
        prev.next = next;
        x.prev = null;
    }
    // 如果后繼節(jié)點(diǎn)為null，說明要移除的是尾節(jié)點(diǎn)，則將last指針指向前驅(qū)節(jié)點(diǎn)prev
    if (next == null) {
        last = prev;
    // 否則，則將后繼節(jié)點(diǎn)的prev指針指向前驅(qū)節(jié)點(diǎn)prev，并斷開當(dāng)前節(jié)點(diǎn)與后繼節(jié)點(diǎn)的連接
    } else {
        next.prev = prev;
        x.next = null;
    }
    // 將被移除節(jié)點(diǎn)的item設(shè)為null，幫助垃圾回收
    x.item = null;
    // 減少鏈表的大小size
    size--;
    // 增加修改計(jì)數(shù)modCount（用于迭代時(shí)的快速失敗機(jī)制）
    modCount++;
    // 返回被移除節(jié)點(diǎn)的元素值
    return element;
}

public boolean contains(Object o){
     // 調(diào)用 indexOf 查找目標(biāo)元素 o 的索引，并判斷目標(biāo)元素索引不等于 -1
     // 目標(biāo)元素索引等于 -1，等式不成立，返回 false; 不等于則返回 true
     return indexOf(o) != -1;
}
public int indexOf(Object o){
    // 初始化索引記數(shù)器
    int index = 0; 
    // 分別處理查找 null 值和非 null 值的情況，避免出現(xiàn)NullPointerException
    // 處理查找null值的情況
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    // 處理查找非null值的情況
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    // 未找到元素，返回-1
    return -1;
}

import java.util.LinkedList;
import java.util.ListIterator;
public class ListIteratorDemo {
    public static void main(String[] args){
        LinkedList<String> list = new LinkedList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        System.out.println("原始列表: " + list); // [A, B, C, D]
        // 獲取 ListIterator，從索引 0 開始
        ListIterator<String> iterator = list.listIterator();
        // 1. 獲取第一個(gè)元素 "A"
        System.out.println("next: " + iterator.next()); // 返回 A, 光標(biāo)移到 A 后
        // 光標(biāo)位置: A | B C D
        // 2. 在當(dāng)前光標(biāo)位置（即 A 和 B 之間）插入 "New"
        iterator.add("New"); 
        System.out.println("add后: " + list); // [A, New, B, C, D]
        // 光標(biāo)位置: A New | B C D
        // 3. 獲取下一個(gè)元素 "B"
        System.out.println("next: " + iterator.next()); // 返回 B, 光標(biāo)移到 B 后
        // 光標(biāo)位置: A New B | C D
        // 4. 獲取下一個(gè)元素 "C"
        System.out.println("next: " + iterator.next()); // 返回 C, 光標(biāo)移到 C 后
        // 注意：最后一次返回的是 C，所以接下來的 set 會(huì)替換 C
        // 光標(biāo)位置: A New B C | D
        // 5. 將剛剛獲取的 "C" 替換為 "Replace_C"
        iterator.set("Replace_C");
        System.out.println("set后: " + list); // [A, New, B, Replace_C, D]
        // 6. 向后回退：獲取前一個(gè)元素
        // 此時(shí)光標(biāo)在 C(即Replace_C) 后，前一個(gè)就是 Replace_C
        System.out.println("previous: " + iterator.previous()); //返回 Replace_C, 光標(biāo)回退
        // 光標(biāo)位置: A New B | Replace_C D
        // 7. 刪除剛剛回退獲取的元素 "Replace_C"
        iterator.remove();
        System.out.println("remove后: " + list); // [A, New, B, D]
    }
}

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // 序列化版本號(hào)，用于實(shí)現(xiàn) Serializable 接口
    private static final long serialVersionUID = 8673264195747942595L;
    // ReentrantLock 可重入鎖，用來保護(hù)所有修改操作
    // transient 修飾，表示在序列化時(shí)不會(huì)保存
    final transient ReentrantLock lock = new ReentrantLock();
    // 存儲(chǔ)實(shí)際數(shù)據(jù)的數(shù)組
    // volatile關(guān)鍵字確?？梢娦裕匆粋€(gè)線程修改了數(shù)組，其他線程能立即看到變化
    private transient volatile Object[] array;
    final Object[] getArray() {
        return array;
    }
    final void setArray(Object[] a) {
        array = a;
    }
    //.............
}

public E get(int index) {
    // 先調(diào)用 getArray() 獲取 array 引用，不加任何鎖
    // 然后調(diào)用另一個(gè)重載的get方法，傳入數(shù)組和索引，返回?cái)?shù)組中的元素
    return get(getArray(),index);
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

public boolean add(E e) {
    // 獲取鎖對象
    final ReentrantLock lock = this.lock;
    // 加鎖，確保線程安全
    lock.lock();
    try {
        // 獲取當(dāng)前數(shù)組
        Object[] elements = getArray();
        // 獲取當(dāng)前數(shù)組長度
        int len = elements.length;
        // 創(chuàng)建一個(gè)新數(shù)組，長度為原數(shù)組+1，并拷貝舊數(shù)組
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 在新數(shù)組末尾添加新元素
        newElements[len] = e;
        // 將新數(shù)組設(shè)置為底層數(shù)組
        setArray(newElements);
        return true;
    } finally {
        // 釋放鎖
        lock.unlock();
    }
}

import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
public class CopyOnWriteArrayListDemo {
    public static void main(String[] args) {
        List<String> list = new CopyOnWriteArrayList<>();
        list.add("A");
        list.add("B");
        // 迭代器創(chuàng)建時(shí)，拿到的是 [A, B] 的快照
        Iterator<String> it = list.iterator(); 
        // 主線程修改了列表
        list.add("C"); 
        while(it.hasNext()) {
            // 只會(huì)打印 A 和 B，不會(huì)拋出異常，也看不到 C
            System.out.println(it.next()); 
        }
    }
}

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    // 序列化版本號(hào)
    static final long serialVersionUID = -5024744406713321676L;
    // HashSet 的核心，實(shí)際上使用 HashMap 來存儲(chǔ)數(shù)據(jù)
    // transient 關(guān)鍵字表示 map 不參與序列化
    private transient HashMap<E,Object> map;
    // 一個(gè)固定的 Object 對象，作為 HashMap 中所有 value 的占位值
    private static final Object PRESENT = new Object();
    // 創(chuàng)建 HashSet，底層 HashMap 使用默認(rèn)初始容量（16）和加載因子（0.75）
    public HashSet() {
        map = new HashMap<>();
    }
    // 創(chuàng)建一個(gè)包含指定集合元素的 HashSet，根據(jù)集合大小計(jì)算合適的初始容量，確保不會(huì)頻繁擴(kuò)容
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    // 創(chuàng)建 HashSet,允許自定義初始容量和加載因子
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    // 創(chuàng)建 HashSet, 允許自定義初始容量
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }   
}

public boolean add(E e) {
    // 直接用 map 的 put 方法存儲(chǔ)元素 e
    // e 是 key, PRESENT 是固定的 value
    return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
    // 直接調(diào)用 map 的 remove 方法刪除元素 o
    return map.remove(o)==PRESENT;
}
public boolean contains(Object o) {
    // 直接調(diào)用 map 的 containsKey 方法查找元素 o
    return map.containsKey(o);
}

// Adds the specified element to this set if it is not already present.
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public V put(K key, V value) {
    // 調(diào)用hash(key)方法計(jì)算鍵的哈希值
    // 將哈希值、鍵、值以及其他參數(shù)傳遞給putVal方法
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
    int h;
    // 如果 key 是 null，返回 0；否則將 h 右移 16 位并與自身異或（高位運(yùn)算，減少?zèng)_突）
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// hash: key的哈希值
// key: 要存儲(chǔ)的鍵
// value: 要存儲(chǔ)的值
// onlyIfAbsent: 如果為true，則僅在鍵不存在時(shí)才插入
// evict: 是否在插入后執(zhí)行可能的移除操作（用于LinkedHashMap）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 檢查內(nèi)部數(shù)組table是否為空，如果是則通過resize()初始化
    // resize()會(huì)創(chuàng)建一個(gè)新的數(shù)組并返回
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 使用(n-1) & hash計(jì)算key在數(shù)組中的索引位置
    // 如果該位置為空，直接創(chuàng)建新節(jié)點(diǎn)放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 處理哈希沖突
    else {
        Node<K,V> e; K k;
        // 直接匹配：檢查第一個(gè)節(jié)點(diǎn)是否與要插入的key相同
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 記錄當(dāng)前節(jié)點(diǎn)
        // 紅黑樹節(jié)點(diǎn)
        else if (p instanceof TreeNode)
            // 調(diào)用putTreeVal方法處理
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 鏈表節(jié)點(diǎn)：遍歷鏈表，查找是否已存在相同的key
        else {
            for (int binCount = 0; ; ++binCount) {
                // 如果遍歷到鏈表尾部還沒找到重復(fù)的，說明元素不重復(fù)，掛在尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 當(dāng)鏈表長度達(dá)到TREEIFY_THRESHOLD(默認(rèn)8)時(shí)，轉(zhuǎn)換為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                 // 在鏈表中判斷：Hash值相同 且 (引用相同 或 equals相同)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // 找到重復(fù)了，跳出循環(huán)，e 指向重復(fù)節(jié)點(diǎn)
                p = e;
            }
        }
        // e 不為 null，說明在 Map 中找到了現(xiàn)有的 Key（即元素重復(fù)）
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 根據(jù) onlyIfAbsent 決定是否覆蓋（HashSet 永遠(yuǎn)是覆蓋）
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 返回舊值，這對 HashSet 意味著 add 失敗
            return oldValue;
        }
    }
    // 如果程序能走到這里，說明 e 為 null，是新增節(jié)點(diǎn)
    ++modCount; //增加修改計(jì)數(shù)
    // 檢查是否需要擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null; // 返回 null，這對 HashSet 意味著 add 成功
}

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable 
{
    // 默認(rèn)初始容量（初始容量為2的4次方）
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    // 最大容量（最大容量為2的30次方）
    static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824
    // 默認(rèn)負(fù)載因子（默認(rèn)的負(fù)載因子為0.75，加載因子 = 哈希表中元素?cái)?shù)量 / 容量）
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // .........
}

// java.util.HashMap
final V putVal(int hash, K key, V value, boolean onlyIfAbsent，boolean evict)
{
    // ......（省略前面的計(jì)算索引和處理鏈表邏輯）
    ++modCount;
    // 插入成功后，size 自增
    // 【核心擴(kuò)容判斷】
    // size：當(dāng)前元素?cái)?shù)量
    // threshold：擴(kuò)容閾值（容量*負(fù)載因子）
    if(++size > threshold)
        resize(); // 觸發(fā)擴(kuò)容
    afterNodeInsertion(evict);
    return null;
}

// java.util.HashMap
final Node<K,V>[] resize(){    
    // 獲取舊的 table
    Node<K,V>[] oldTab = table; 
    // 獲取舊表格（oldTab）的容量
    // 使用三元運(yùn)算符判斷：如果oldTab為null，則oldCap為0；否則為oldTab的長度
    int oldCap = (oldTab == null) ? 0 : oldTab.length; 
    // 獲取舊的擴(kuò)容閾值（threshold）
    // HashMap需要擴(kuò)容的臨界值，通常為容量*加載因子
    int oldThr = threshold;
    // 聲明新的容量（newCap）和新的閾值（newThr）
    int newCap, newThr = 0;
    // 如果舊數(shù)組不為空
    if (oldCap > 0) {
        // 如果舊容量已經(jīng)達(dá)到最大值，不再擴(kuò)容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab; // 返回舊表格
        }
        // 【核心邏輯】：新容量 = 舊容量左移1位 (即乘以2)
        // (newCap = oldCap << 1) 例如 16 -> 32
        // 如果計(jì)算的新容量沒達(dá)到最大值且舊容量大于默認(rèn)初始容量，計(jì)算新閾值
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新閾值也乘以2
            newThr = oldThr << 1;
    }
    // 當(dāng)oldThr > 0時(shí)，說明HashMap已經(jīng)被初始化過
    // 這種情況下，新的容量(newCap)直接設(shè)置為舊的閾值(oldThr)
    // 注釋"initial capacity was placed in threshold"表明初始容量被存儲(chǔ)在了閾值中
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 初始化時(shí)，如果用戶沒有指定初始容量（即 threshold 為 0）的情況下
    else {
        // 設(shè)置默認(rèn)容量和擴(kuò)容閾值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新閾值是 0 (比如使用默認(rèn)構(gòu)造函數(shù)時(shí))，重新計(jì)算
    if (newThr == 0) {
        // 新的容量：(newCap)乘以加載因子(loadFactor)
        float ft = (float)newCap * loadFactor;
        // 使用浮點(diǎn)數(shù)ft進(jìn)行中間計(jì)算，避免精度丟失，將計(jì)算結(jié)果轉(zhuǎn)換為整數(shù)賦值給threshold
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);   
    }
    threshold = newThr; // 更新全局閾值
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 創(chuàng)建新的數(shù)組
    table = newTab; // 將新數(shù)組賦值給 table
    // 如果舊數(shù)組有數(shù)據(jù)，開始遍歷遷移
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 如果當(dāng)前位置有元素
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null; // 顯式地將引用置為null幫助垃圾回收器更快回收內(nèi)存
                // 單個(gè)節(jié)點(diǎn)處理
                if (e.next == null)
                    // 直接計(jì)算新位置并放入
                    newTab[e.hash & (newCap - 1)] = e;
                // 紅黑樹處理
                else if (e instanceof TreeNode)
                    // 調(diào)用split方法進(jìn)行拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 鏈表處理
                // 通過維護(hù)兩個(gè)鏈表(lo和hi)，將元素分別加入對應(yīng)的鏈表
                else {
                    // loHead/loTail：保持原索引位置的鏈表
                    // hiHead/hiTail：需要移動(dòng)到"原索引+舊容量"位置的鏈表
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 判斷元素的位置是否需要移動(dòng)
                        // 如果(e.hash & oldCap) == 0，說明元素在新數(shù)組中的位置不變
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 如果(e.hash & oldCap) != 0
                        // 元素需要移動(dòng)到新位置，新位置 = 原位置 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 處理低位鏈表
                    if (loTail != null) {
                        loTail.next = null; // 斷開低位鏈表的最后一個(gè)節(jié)點(diǎn)的next指針
                        newTab[j] = loHead; // 將低位鏈表放在新數(shù)組的原索引位置
                    }
                    // 處理高位鏈表
                    if (hiTail != null) {
                        hiTail.next = null; // 斷開高位鏈表的最后一個(gè)節(jié)點(diǎn)的next指針
                        newTab[j + oldCap] = hiHead; // 將高位鏈表放在新數(shù)組的原索引+oldCap位置
                    }
                }
            }
        }
    }
    return newTab;
}

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable 
{
    // ..........
}

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable 
{
    // 序列化/反序列化的版本控制ID
    private static final long serialVersionUID = -2851667679971038690L;
    // 創(chuàng)建一個(gè)指定初始容量和加載因子的空LinkedHashSet
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
    // 創(chuàng)建一個(gè)指定初始容量，默認(rèn)加載因子(0.75)的空LinkedHashSet
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
    // 創(chuàng)建一個(gè)默認(rèn)初始容量(16)和默認(rèn)加載因子(0.75)的空LinkedHashSet
    public LinkedHashSet() {
        super(16, .75f, true);
    }
    // 創(chuàng)建一個(gè)包含指定集合所有元素的LinkedHashSet，初始容量設(shè)為max(2*c.size(), 11)
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
    // 可分割迭代器
    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }
}

// java.util.HashSet

// 底層存儲(chǔ) Map
private transient HashMap<E,Object> map;


/**
 * 構(gòu)造一個(gè)新的空的鏈接哈希集合實(shí)例。
 * （這個(gè)構(gòu)造函數(shù)只給 LinkedHashSet 訪問，dummy 沒有實(shí)際意義）
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    // 注意這里：new 的不是 HashMap，而是 LinkedHashMap！
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable 
{
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; // 存儲(chǔ)鍵的哈希值，用于快速定位
        final K key; // 存儲(chǔ)鍵，用final修飾表示鍵不可變
        V value; // 存儲(chǔ)值，可以被修改
        Node<K,V> next; // 指向下一個(gè)節(jié)點(diǎn)的引用，用于處理哈希沖突
        //........
    }
}

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
{
    // 靜態(tài)內(nèi)部類
    // 繼承自 HashMap.Node，說明其具備了 HashMap 中節(jié)點(diǎn)的所有基本特性
    static class Entry<K,V> extends HashMap.Node<K,V>{
        // 新增的兩個(gè)指針，用于維護(hù)雙向鏈表
        // before（前驅(qū)指針）：指向前一個(gè)節(jié)點(diǎn)
        // after（后繼指針）：指向后一個(gè)節(jié)點(diǎn)
        Entry<K,V> before, after;
        // 構(gòu)造函數(shù)
        // 接收四個(gè)參數(shù)：hash值、鍵、值和下一個(gè)節(jié)點(diǎn)
        // 通過 super() 調(diào)用父類 HashMap.Node 的構(gòu)造函數(shù)，確保新建節(jié)點(diǎn)具備 HashMap 節(jié)點(diǎn)的所有基本屬性
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
}

// java.util.linkedHashMap
// 雙向鏈表的頭節(jié)點(diǎn)
// transient關(guān)鍵字表示這個(gè)字段不會(huì)被序列化
transient LinkedHashMap.Entry<K,V> head;
// 雙向鏈表的尾節(jié)點(diǎn)
// transient關(guān)鍵字表示這個(gè)字段不會(huì)被序列化
transient LinkedHashMap.Entry<K,V> tail;
// 這是一個(gè) final 字段，決定了 LinkedHashMap 的迭代順序
// 當(dāng)為 true 時(shí)，按照訪問順序迭代（最近訪問的放在最后）
// 當(dāng)為 false 時(shí)，按照插入順序迭代 （默認(rèn)為 false）
final boolean accessOrder;

// java.util.LinkedHashMap
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 創(chuàng)建新節(jié)點(diǎn) p
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 調(diào)用鏈接方法，把新增節(jié)點(diǎn) p 掛在鏈表尾部
    linkNodeLast(p);
    return p;
} 
private void linkNodeLast(LinkedHashMap。Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail; // 保存當(dāng)前尾節(jié)點(diǎn)
    tail = p; // 將新節(jié)點(diǎn)p設(shè)置為新的尾節(jié)點(diǎn)
    if (last == null) // 如果鏈表為空
        head = p; // 將新節(jié)點(diǎn)同時(shí)設(shè)為頭節(jié)點(diǎn)
    else { // 如果鏈表不為空
        p.before = last; // 將新節(jié)點(diǎn)的前驅(qū)指針指向原尾節(jié)點(diǎn)
        last.after = p; // 將原尾節(jié)點(diǎn)的后繼指針指向新節(jié)點(diǎn)
    }
}

// java.util.LinkedHashMap
public V get(Object key) {
    // 聲明一個(gè) Node 類型的變量 e,用于存儲(chǔ)找到的節(jié)點(diǎn)
    Node<K,V> e;
    // 調(diào)用 getNode 方法查找節(jié)點(diǎn)
    // 如果找不到對應(yīng)節(jié)點(diǎn)（e為null），直接返回null
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果accessOrder為true，表示按照訪問順序排序
    if (accessOrder)
        // 調(diào)用 afterNodeAccess(e) 方法將最近訪問的節(jié)點(diǎn)移到鏈表末尾
        afterNodeAccess(e);
    // 返回找到的節(jié)點(diǎn)的value值
    return e.value;
}
void afterNodeAccess(Node<K,V> e) {    
    LinkedHashMap.Entry<K,V> last;
    // 檢查是否需要重新排序（accessOrder為true）且節(jié)點(diǎn)不在尾部
    if (accessOrder && (last = tail) != e) {
        // 保存當(dāng)前節(jié)點(diǎn)的前后節(jié)點(diǎn)引用
        LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 將p的after置為null，因?yàn)樗鼘⒊蔀樾碌奈补?jié)點(diǎn)
        p.after = null;
        // 如果b為null，說明p是頭節(jié)點(diǎn)，更新頭節(jié)點(diǎn)為a；否則，將b的after指向a
        if (b == null)
            head = a;
        else
            b.after = a;
        // 如果a不為null，將a的before指向b；否則，更新last為b
        if (a != null)
            a.before = b;
        else
            last = b;
        // 如果last為null，說明鏈表為空，將頭節(jié)點(diǎn)head設(shè)置為p；否則，將p連接到last之后
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        // 更新尾節(jié)點(diǎn)tail為p
        tail = p;
        // 增加修改計(jì)數(shù)器
        ++modCount;
    }
}

// java.util.LinkedHashMap
abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next; // 指向下一個(gè)要遍歷的節(jié)點(diǎn)
    LinkedHashMap.Entry<K,V> current; // 當(dāng)前正在處理的節(jié)點(diǎn)
    int expectedModCount; // 預(yù)期的修改次數(shù)，用于快速失敗(fail-fast)機(jī)制
    LinkedHashIterator() {
        next = head; // 從雙向鏈表的頭節(jié)點(diǎn)開始
        expectedModCount = modCount; // 記錄創(chuàng)建迭代器時(shí)的修改次數(shù)
        current = null; // 當(dāng)前節(jié)點(diǎn)初始化為null
    }
    // 判斷是否還有下一個(gè)元素
    public final boolean hasNext() {
        return next != null;
    }
    final LinkedHashMap.Entry<K,V> nextNode(){
        LinkedHashMap.Entry<K,V> e = next;
        // 檢查是否有并發(fā)修改
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null) 
            throw new NoSuchElementException();
        // 更新當(dāng)前節(jié)點(diǎn)
        current = e; 
        // 移動(dòng)到下一個(gè)節(jié)點(diǎn)（通過after指針）
        next = e.after; 
        return e;
    }
}

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
// 插入順序 vs 排序順序
public class OrderDemo {
    public static void main(String[] args) {
        String[] letters = {"C", "A", "B", "A"};
        // LinkedHashSet: 維持插入順序
        Set<String> linkedSet = new LinkedHashSet<>(Arrays.asList(letters));
        System.out.println("LinkedHashSet: " + linkedSet);
        // 輸出: [C, A, B] -> 去重了，且 C 在最前面，因?yàn)樗堑谝粋€(gè)插入的
        // TreeSet: 按字典序排序
        Set<String> treeSet = new TreeSet<>(Arrays.asList(letters));
        System.out.println("TreeSet: " + treeSet);
        // 輸出: [A, B, C] -> 去重了，且按 A, B, C 排列，完全忽略了插入順序
    }
}

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    // ..........    
}

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    // TreeSet 內(nèi)部使用一個(gè) NavigableMap (實(shí)際是 TreeMap) 來存儲(chǔ)元素
    private transient NavigableMap<E,Object> m;
    // 這個(gè)是一個(gè)虛擬值，用于在 TreeMap 中關(guān)聯(lián)集合的元素
    // 因?yàn)?TreeMap 存儲(chǔ)的是鍵值對，而 TreeSet 只需要鍵
    private static final Object PRESENT = new Object();
    //.............
}

// java.util.TreeMap
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left; // 左子節(jié)點(diǎn)
    Entry<K,V> right; // 右子節(jié)點(diǎn)
    Entry<K,V> parent; // 父節(jié)點(diǎn)
    boolean color = BLACK; // 節(jié)點(diǎn)顏色，默認(rèn)為黑
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    // .........
}  

// java.util.TreeSet
// 無參構(gòu)造器，使用自然排序
public TreeSet() {
    this(new TreeMap<E,Object>());
}
// 帶比較器的構(gòu)造器，使用自定義排序
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
// 構(gòu)造一個(gè)包含指定集合元素的新 TreeSet，使用自然排序
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
// 構(gòu)造一個(gè)包含指定有序集合元素的新 TreeSet，按照相同順序
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}
// 包訪問權(quán)限的構(gòu)造器，直接傳入一個(gè) NavigableMap
// 主要用于子類或者特定場景，比如 headSet, subSet, tailSet 等返回的子集
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

// java.util.TreeSet
public boolean add(E e) {
    // 直接調(diào)用底層 TreeMap 的 put 方法
    // 如果之前不存在該 key，則 put 返回 null，add 返回 true (添加成功)
    // 如果之前已存在該 key (根據(jù)排序規(guī)則)，則 put 返回舊 value，add 返回 false (添加失敗，元素已存在)
    return m.put(e,PRESENT) == null;
}

// java.util.TreeMap
public V put(K key, V value) {
    Entry<K,V> t = root; // 從根節(jié)點(diǎn)開始
    // 特殊情況：樹是空的
    // 此時(shí) new Entry 的 parent 是 null，默認(rèn) color 是 BLACK
    // (Entry構(gòu)造器中 color 默認(rèn) BLACK，但在 insert 修正里可能會(huì)變)
    if (t == null) {
        compare(key, key); // 類型檢查，確保 key 是可比較的
        root = new Entry<>(key, value, null); // 創(chuàng)建根節(jié)點(diǎn)
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    // 如果有自定義比較器，使用比較器進(jìn)行比較
    if (cpr != null) {
        // 遍歷樹找到合適的插入位置
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0) // 小，往左走
                t = t.left;
            else if (cmp > 0) // 大，往右走
                t = t.right;
            else // 相等，替換值， TreeSet 這里返回 PRESENT
                return t.setValue(value);
        } while (t != null);     
    }
    // 如果沒有自定義比較器，使用鍵的自然排序
    else {
        // 鍵不能為null 且 鍵必須實(shí)現(xiàn)Comparable接口
        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);
    }
    // 創(chuàng)建新節(jié)點(diǎn)并插入到合適位置
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    // 調(diào)用fixAfterInsertion維護(hù)紅黑樹的平衡
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

// java.util.TreeMap
private void fixAfterInsertion(Entry<K,V> x) {
    // 將新插入的節(jié)點(diǎn)設(shè)為紅色
    x.color = RED;
    // 當(dāng) x 不是根節(jié)點(diǎn)，且 x 的父節(jié)點(diǎn)是紅色時(shí)（違反規(guī)則4），需要循環(huán)修復(fù)
    while (x != null && x != root && x.parent.color == RED) {
        // 判斷父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子還是右孩子
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x))); // y 是叔節(jié)點(diǎn)
            // 如果叔節(jié)點(diǎn)是紅色
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK); // 父節(jié)點(diǎn)變黑
                setColor(y, BLACK); // 叔節(jié)點(diǎn)變黑
                setColor(parentOf(parentOf(x)), RED); // 祖父節(jié)點(diǎn)變紅
                x = parentOf(parentOf(x)); // 指針上移，以祖父為當(dāng)前節(jié)點(diǎn)繼續(xù)循環(huán)
            } else {
                // 如果叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)是右孩子
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);  // 左旋（以父節(jié)點(diǎn)為中心）
                    rotateLeft(x);
                }
                // 叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)是左孩子
                setColor(parentOf(x), BLACK); // 父節(jié)點(diǎn)變黑
                setColor(parentOf(parentOf(x)), RED); // 祖父節(jié)點(diǎn)變紅
                rotateRight(parentOf(parentOf(x))); // 右旋（以祖父節(jié)點(diǎn)為中心）
            }
        } else {
            // 父節(jié)點(diǎn)是祖父的右孩子，邏輯同上，只是左右互換（鏡像情況）
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }    
        }
    }
     // 確保根節(jié)點(diǎn)始終是黑色（符合規(guī)則2：根節(jié)點(diǎn)是黑色）
    root.color = BLACK;
}

// java.util.TreeSet
public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

// java.util.TreeMap
final class KeyIterator extends PrivateEntryIterator<K> {
    KeyIterator(Entry<K,V> first) {
        super(first);
    }
    public K next() {
        return nextEntry().key;
    }
}

final Entry<K,V> nextEntry() {
    Entry<K,V> e = next;
    if (e == null)
        throw new NoSuchElementException();
    // 預(yù)先計(jì)算下一個(gè)節(jié)點(diǎn)，保存在 next 變量中
    // 這里的算法是：如果當(dāng)前節(jié)點(diǎn)有右子樹，下一個(gè)節(jié)點(diǎn)是右子樹的最左節(jié)點(diǎn)；
    // 如果沒有右子樹，下一個(gè)節(jié)點(diǎn)是第一個(gè)“祖先”節(jié)點(diǎn)，該節(jié)點(diǎn)的左子樹包含當(dāng)前節(jié)點(diǎn)。
    if ((next = successor(e)) == null)
        next = null;
    lastReturned = e;
    return e;
}
// 尋找后繼節(jié)點(diǎn)的算法
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        //  有右子樹：找右子樹中最左邊的節(jié)點(diǎn)（最小的）
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        //  無右子樹：向上找第一個(gè)左拐的父節(jié)點(diǎn)
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

// java.util.TreeSet
public E floor(E e) {
    return m.floorKey(e);
}
public K floorKey(K key) {
    Entry<K,V> p = getFloorEntry(key);
    return (p == null) ? null : p.key;
}
// 核心：尋找小于等于 key 的最大節(jié)點(diǎn)
final Entry<K,V> getFloorEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) { // key > p.key
            if (p.right != null)
                p = p.right; // 往右找更大的
            else
                return p; // 沒右了，當(dāng)前 p 就是小于 key 的最大值
        } else if (cmp < 0) { // key < p.key
            if (p.left != null)
                p = p.left; // 往左找更小的
            else {
                // 沒左了，說明當(dāng)前 p 太大了，得往回找父節(jié)點(diǎn)
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p; // 相等，直接返回
    }
    return null;
}

public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                             E toElement, boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                  toElement, toInclusive));
}

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    // 用于存儲(chǔ)元素的 
    transient Object[] elements;
    // 對頭指針：指向隊(duì)首元素
    transient int head;
    // 隊(duì)尾指針：指向下一個(gè)待插入元素的位置（隊(duì)尾元素的下一個(gè)位置）
    transient int tail;
    // 最小初始容量
    private static final int MIN_INITIAL_CAPACITY = 8;
}

// java.util.ArrayDeque
// 對頭入隊(duì)
public void addFirst(E e){
    // 安全檢查: ArrayDeque 不允許 null
    if (e == null)
        throw new NullPointerException();
    // 元素入隊(duì)，head 指針向前移動(dòng)一位
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // 在插入元素后，檢查 head 是否追上了 tail
    // 在 ArrayDeque 中，數(shù)組中始終至少留一個(gè)空位
    // 當(dāng) head == tail 時(shí)，說明數(shù)組已經(jīng)滿了，沒有空位了
    if (head == tail)
        doubleCapacity();
}
// 隊(duì)尾入隊(duì)
public void addLast(E e){
    // 安全檢查: ArrayDeque 不允許 null
    if (e == null)
        throw new NullPointerException();
    // 元素入隊(duì)，放在 tail 指向的位置
    elements[tail] = e;
    // tail 指針后移并判斷是否需要擴(kuò)容
    // (tail + 1) & (elements.length - 1) 等同于 (tail + 1) % length
    // 如果移動(dòng)后的 tail 撞上了 head，說明數(shù)組已經(jīng)滿了
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

// java.util.ArrayDeque
// 刪除隊(duì)列頭部元素
public E removeFirst() {
    // 調(diào)用 pollFirst() 方法嘗試獲取并移除隊(duì)列頭部的元素，并將結(jié)果賦值給變量 x
    E x = pollFirst();
    // 如果 pollFirst() 返回 null（意味著隊(duì)列為空），則拋出一個(gè) NoSuchElementException 異常
    if(x == null)
        throw new NoSuchElementException();
    // （隊(duì)列不為空）返回獲取到的元素 x
    return x;
}
public E pollFirst() {
    // 將當(dāng)前隊(duì)列頭部的索引 head 賦值給局部變量 h
    int h = head;
    // @SuppressWarnings("unchecked") 用于抑制編譯器的“未檢查類型轉(zhuǎn)換”警告
    // elements 數(shù)組是 Object[] 類型，將其中的元素強(qiáng)制轉(zhuǎn)換為泛型 E 類型時(shí)，編譯器會(huì)發(fā)出警告
    // 這里開發(fā)人員確認(rèn)這種轉(zhuǎn)換是安全的，因此忽略警告 
    @SuppressWarnings("unchecked")
    // 取出數(shù)組中索引為 h 的元素，并強(qiáng)制轉(zhuǎn)換為泛型 E 類型，賦值給 result
    E result = (E) elements[h];
    // 判斷取出的元素是否為 null
    if (result == null)
        return null;
    // 將原頭部位置的數(shù)組元素顯式設(shè)為 null
    // 手動(dòng)置為 null，防止內(nèi)存泄漏
    // 在 Java 中，只要一個(gè)對象被引用，垃圾回收器（GC）就不會(huì)回收它
    // 雖然我們即將把 head 指針移走，但數(shù)組中該位置仍然引用著舊的對象
    // 如不手動(dòng)置為 null，這個(gè)對象可能一直占用內(nèi)存直到數(shù)組被覆蓋或回收
    elements[h] = null;
    // 計(jì)算新的頭部索引
    head = (h + 1) & (elements.length - 1);
    // 返回之前取出的元素
    return result;
}
// 刪除隊(duì)列尾部元素
public E removeLast() {
    // 調(diào)用 pollLast() 方法嘗試獲取并移除隊(duì)列尾部的元素，并將結(jié)果賦值給變量 x
    E x = pollLast();
    // 如果 pollLast() 返回 null（意味著隊(duì)列為空），則拋出一個(gè) NoSuchElementException 異常
    if(x == null)
        throw new NoSuchElementException();
    // （隊(duì)列不為空）返回獲取到的元素 x
    return x;
}
public E pollLast() {
    // 計(jì)算隊(duì)尾元素索引
    // tail 指向下一個(gè)可用元素的位置（即當(dāng)前隊(duì)尾元素的下一位）
    // 實(shí)際的最后一個(gè)元素索引是 tail - 1
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    // 取出數(shù)組中索引為 t 的元素，并強(qiáng)制轉(zhuǎn)換為泛型 E 類型，賦值給 result
    E result = (E) elements[t];
    // 判斷取出的元素是否為 null
    if (result == null)
        return null;
    // 顯式置空，幫助 GC
    elements[t] = null;
    // 將隊(duì)尾指針 tail 移動(dòng)到剛才取出元素的位置
    tail = t;
    // 返回取出的元素
    return result;
}

// java.util.ArrayDeque
private void doubleCapacity() {
    // 斷言 head 等于 tail
    // 在循環(huán)數(shù)組中，當(dāng)隊(duì)列滿時(shí)，head 和 tail 會(huì)指向同一個(gè)位置
    // （即下一個(gè)要插入的位置會(huì)被覆蓋，或者表示沒有空間）
    // 這個(gè)斷言確保該方法只在隊(duì)列滿時(shí)被調(diào)用
    assert head == tail;
    // 保存當(dāng)前隊(duì)首的索引位置到變量 p
    int p = head;
    // 獲取舊數(shù)組的長度 n
    int n = elements.length;
    // 計(jì)算從 head (即 p) 到數(shù)組末尾的元素個(gè)數(shù)
    int r = n - p; 
    // 計(jì)算新容量，n 左移 1 位相當(dāng)于 n * 2
    int newCapacity = n << 1;
    // 檢查新容量是否溢出
    // 如果 n 已經(jīng)非常大（接近 Integer.MAX_VALUE），n * 2 會(huì)變成負(fù)數(shù)（整數(shù)溢出）
    // 此時(shí)隊(duì)列已經(jīng)無法繼續(xù)擴(kuò)容，拋出異常
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    // 創(chuàng)建一個(gè)容量為 newCapacity 的新數(shù)組 a
    Object[] a = new Object[newCapacity];
    // 復(fù)制 head 到數(shù)組末尾的部分 到 新數(shù)組的開頭
    System.arraycopy(elements, p, a, 0, r);
    // 復(fù)制 數(shù)組開頭 到 tail 的部分 到 新數(shù)組的后面
    System.arraycopy(elements, 0, a, r, p);
    // 將隊(duì)列內(nèi)部的數(shù)組引用指向新數(shù)組 a
    elements = a;
    // 重置隊(duì)首 head 為新數(shù)組的 0 索引
    head = 0;
    // 重置隊(duì)尾 tail 為舊數(shù)組的長度 n
    tail = n;
}

// java.util.ArrayDeque( doubleCapacity() )
int p = head;            // p = 4
int n = elements.length; // n = 8
int r = n - p;           // r = 8 - 4 = 4 (head右邊有4個(gè)元素)
int newCapacity = n << 1; // newCapacity = 16
Object[] a = new Object[newCapacity]; // 創(chuàng)建新數(shù)組，長度 16
// 步驟 1: 復(fù)制右半部分 [A, B, C, D] 到新數(shù)組開頭
System.arraycopy(elements, p, a, 0, r);
// 步驟 2: 復(fù)制左半部分 [E, F, G, H] 到新數(shù)組后面
System.arraycopy(elements, 0, a, r, p);
elements = a; // 引用指向新數(shù)組
head = 0;     // 重置 head
tail = n;     // 重置 tail = 8

import java.util.PriorityQueue;
public class priorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        // 亂序插入
        queue.add(3);
        queue.add(1);
        queue.add(2);
        queue.add(5);
        queue.add(4);
        // 驗(yàn)證“內(nèi)部無序”：直接打印集合
        System.out.println("直接打印內(nèi)部結(jié)構(gòu)(無序): " + queue);
        // 輸出可能是: [1, 2, 3, 5, 4]  <-- 注意這不是完全排序，只是堆結(jié)構(gòu)
        // 驗(yàn)證“出隊(duì)有序”：使用 poll 遍歷
        System.out.print("依次出隊(duì)(有序): ");
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
        // 輸出: 1 2 3 4 5
    }
}

// java.util
public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    // 默認(rèn)初始容量
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    // 底層存儲(chǔ)數(shù)組：通過二叉堆的邏輯來維護(hù)這個(gè)數(shù)組
    transient Object[] queue;
    // 當(dāng)前元素個(gè)數(shù)
    private int size = 0;
    // 比較器：如果為 null，則使用自然排序
    private final Comparator<? super E> comparator;
    // 修改次數(shù)（用于 fail-fast 機(jī)制）
    transient int modCount = 0;
}

// java.util.PriorityQueue
public boolean add(E e) {
    return offer(e);
}
public boolean offer(E e) {
    // 非空檢查
    // PriorityQueue 不允許插入 null 元素，如果插入 null 拋出異常
    if(e == null)
        throw new NullPointerException();
    // 修改計(jì)數(shù)器更新
    modCount++;
    // 獲取當(dāng)前隊(duì)列的大小 i
    int i = size;
    // 如果當(dāng)前元素?cái)?shù)量 i 已經(jīng)大于或等于底層數(shù)組 queue 的長度，說明數(shù)組已滿
    if (i >= queue.length)
        // 調(diào)用 grow(i + 1) 方法進(jìn)行擴(kuò)容，以確保能容納新元素
        grow(i + 1);
    // 更新隊(duì)列大小 i
    size = i + 1;
    // 如果插入前隊(duì)列是空的（i == 0），直接將元素放在數(shù)組的第一個(gè)位置 queue[0]
    if (i == 0)
        queue[0] = e;
    // 如果隊(duì)列不為空，調(diào)用 siftUp(i, e) 方法，執(zhí)行上浮調(diào)整
    else
        siftUp(i, e);
    return true;
}

// java.util.PriorityQueue
private void siftUp(int k,E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}
private void siftUpUsingComparator(int k,E x) {
    // 循環(huán)條件：while (k > 0)
    // 只要當(dāng)前節(jié)點(diǎn)索引 k 不是根節(jié)點(diǎn)（根節(jié)點(diǎn)索引為 0），就繼續(xù)嘗試上浮
    while (k > 0) {
        // 計(jì)算當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)索引
        int parent = (k - 1) >>> 1;
        // 取出父節(jié)點(diǎn)存儲(chǔ)的元素
        Object e = queue[parent];
        // 使用比較器比較當(dāng)前待插入元素 x 和父節(jié)點(diǎn)元素 e
        // 如果 x 大于或等于 e，則 break 跳出循環(huán)。此時(shí)位置 k 就是 x 的最終歸宿
        if (comparator.compare(x, (E) e) >= 0)
            break;
        // 如果 x 小于 e，說明違反了堆序性質(zhì)（子節(jié)點(diǎn)比父節(jié)點(diǎn)?。枰粨Q位置。
        queue[k] = e;
        // 更新當(dāng)前索引 k 為父節(jié)點(diǎn)的索引，準(zhǔn)備繼續(xù)向上層比較
        k = parent;
    }
    // 循環(huán)結(jié)束后（要么找到了合適的位置，要么到了根節(jié)點(diǎn)），將目標(biāo)元素 key 放入最終確定的位置 k
    queue[k] = x;
}
private void siftUpComparable(int k,E x) {
    // 將傳入的元素 x 強(qiáng)制轉(zhuǎn)換為 Comparable 類型
    // PriorityQueue 需要比較元素的大小來確定優(yōu)先級(jí)
    Comparable<? super E> key = (Comparable<? super E>) x;
    // 開始循環(huán)。只要當(dāng)前節(jié)點(diǎn)索引 k 大于 0（即當(dāng)前節(jié)點(diǎn)不是根節(jié)點(diǎn)），就繼續(xù)嘗試上浮
    while (k > 0) {
        // 計(jì)算當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)索引
        int parent = (k - 1) >>> 1;
        // 取出父節(jié)點(diǎn)存儲(chǔ)的元素
        Object e = queue[parent];
        // 比較當(dāng)前插入元素 key 和父節(jié)點(diǎn)元素 e 的大小
        // 如果 key >= e
        // 說明堆的性質(zhì)已經(jīng)滿足（父節(jié)點(diǎn)小于等于子節(jié)點(diǎn)），無需繼續(xù)交換，直接 break 跳出循環(huán)
        if (key.compareTo((E) e) >= 0)
            break;
        // 如果 key < e，說明子節(jié)點(diǎn)比父節(jié)點(diǎn)小，違反了最小堆性質(zhì)
        // 則將父節(jié)點(diǎn) e 向下移動(dòng)到當(dāng)前子節(jié)點(diǎn) k 的位置
        queue[k] = e;
        // 更新當(dāng)前索引 k 為父節(jié)點(diǎn)的索引，準(zhǔn)備繼續(xù)向上層比較
        k = parent;
    } 
    // 循環(huán)結(jié)束后（要么找到了合適的位置，要么到了根節(jié)點(diǎn)），將目標(biāo)元素 key 放入最終確定的位置 k
    queue[k] = key;
}

// java.util.PriorityQueue
public E poll() {
    // 檢查隊(duì)列是否為空
    if (size == 0)
        return null; // 如果為空，返回 null（區(qū)別于 remove() 方法拋出異常）
    // 記錄操作前的元素個(gè)數(shù)，并將 size 減 1
    // s 變成了原數(shù)組最后一個(gè)元素的下標(biāo)
    int s = --size;
    // 更新修改計(jì)數(shù)器
    modCount++;
    // 獲取堆頂元素（即最小值），作為最終要返回的結(jié)果
    E result = (E) queue[0];
    // 獲取隊(duì)列末尾的元素
    E x = (E) queue[s];
    // 將原末尾位置置為 null，幫助 GC 回收，避免內(nèi)存泄漏
    queue[s] = null;
    // 如果隊(duì)列中不止一個(gè)元素，則需要執(zhí)行下沉操作
    // 將剛才取出的末尾元素 x 放到堆頂位置（下標(biāo) 0），并開始下沉
    if (s != 0)
        siftDown(0, x);
    // 返回之前獲取的最小值
    return result;
}

// java.util.PriorityQueue
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}
private void siftDownUsingComparator(int k, E x) {
    // 計(jì)算非葉子節(jié)點(diǎn)邊界
    int half = size >>> 1; // 無符號(hào)右移（等同于 size / 2）
    while (k < half) {
        // 計(jì)算當(dāng)前節(jié)點(diǎn) k 的左孩子的索引
        int child = (k << 1) + 1;
        // 獲取左孩子元素 
        Object c = queue[child];
        // 計(jì)算右孩子的索引
        int right = child + 1;
        // 如果右孩子存在，且右孩子比左孩子小
        if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right]; // 更新 child 指向右孩子
        // 如果當(dāng)前元素 x 已經(jīng)小于等于較小的孩子，說明下沉結(jié)束
        if (comparator.compare(x, (E) c) <= 0)
            break;
        // 否則，交換位置（孩子上浮成為父節(jié)點(diǎn)）
        queue[k] = c;
        k = child;
    }
    // 將末尾元素放到最終的位置
    queue[k] = x;
}
private void siftDownComparable(int k, E x) {
    // 將待下沉的元素 x 強(qiáng)制轉(zhuǎn)換為 Comparable 接口類型
    // 因?yàn)樾枰{(diào)用 compareTo 方法來比較元素大小
    Comparable<? super E> key = (Comparable<? super E>)x;
    // 計(jì)算非葉子節(jié)點(diǎn)邊界
    int half = size >>> 1; // 無符號(hào)右移（等同于 size / 2）
    while (k < half) {
        // 計(jì)算當(dāng)前節(jié)點(diǎn) k 的左孩子的索引
        int child = (k << 1) + 1;
        // 獲取左孩子元素
        Object c = queue[child];
        // 計(jì)算右孩子的索引
        int right = child + 1;
        // 比較左右孩子
        // right<size：檢查右孩子是否存在（是否越界）
        // c.compareTo(queue[right])>0：如果左孩子比右孩子大（compareTo 返回正數(shù)）說明右孩子更小
        if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            // 滿足條件，將 c 指向右孩子，并將 child 更新為右孩子的索引
            c = queue[child = right];
        // 如果 key 小于等于 c（compareTo 返回 0 或負(fù)數(shù)），說明堆的順序已經(jīng)正確（父節(jié)點(diǎn)小于子節(jié)點(diǎn)）
        if (key.compareTo((E) c) <= 0)
            // 跳出循環(huán)，下沉結(jié)束
            break;
        // 如果 key 大于 c，說明堆性質(zhì)被破壞。將較小的子節(jié)點(diǎn) c 移動(dòng)到當(dāng)前父節(jié)點(diǎn) k 的位置
        queue[k] = c;
        // 更新 k 為子節(jié)點(diǎn)的位置，準(zhǔn)備進(jìn)行下一輪比較
        k = child;
    }
    // 循環(huán)結(jié)束后，將原始元素 key 放到最終確定的位置 k 上
    queue[k] = key;
}

// java.util.PriorityQueue
private void grow(int minCapacity) {
    // 獲取當(dāng)前底層數(shù)組 queue 的長度
    int oldCapacity = queue.length;
    // 如果舊容量小于 64，則擴(kuò)容 2 倍 + 2
    // 如果舊容量大于 64，則擴(kuò)容 1.5 倍 (即 oldCapacity + (oldCapacity >> 1))
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
    // 防止溢出，如果計(jì)算出的容量過大
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 調(diào)用 hugeCapacity 方法嘗試分配
        newCapacity = hugeCapacity(minCapacity);
    // 調(diào)用 Arrays.copyOf 方法，將原數(shù)組中的數(shù)據(jù)復(fù)制到一個(gè)長度為 newCapacity 的新數(shù)組中，并將 queue 引用指向這個(gè)新數(shù)組
    queue = Arrays.copyOf(queue, newCapacity);  
}
private static int hugeCapacity(int minCapacity) {
    // 溢出檢查：通過檢查 minCapacity 是否小于 0，來判斷是否發(fā)生了整數(shù)溢出
    // 在 Java 中，int 是有符號(hào)的 32 位整數(shù)，最大值為 Integer.MAX_VALUE（約 21 億）
    // 如果之前的計(jì)算（例如 minCapacity = oldCapacity + (oldCapacity >> 1)）導(dǎo)致數(shù)值超過了 int 的最大值
    // 由于整數(shù)溢出，結(jié)果會(huì)變成負(fù)數(shù)
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    // 如果 minCapacity 大于 MAX_ARRAY_SIZE，則直接返回 Integer.MAX_VALUE（即 2147483647）嘗試分配理論上的最大數(shù)組長度
    // 如果 minCapacity 小于或等于 MAX_ARRAY_SIZE，則返回 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8（即 2147483639））
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}