1.Queue

队列常见实现类包含：ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、PriorityQueue、ConcurrentLinkedQueue、PriorityBlockingQueue、DelayQueue、LinkedList。

队列使用场景：全局变量。

传统队列的单一模式： “要么存储、要么交换” 。

直接交换：生产者线程阻塞，直到有消费者线程接收数据，数据直接从生产者传递到消费者，不进入队列。例如SynchronousQueue。

队列存储：生产者直接将数据放入队列，无需等待消费者，消费者从队列中取数据。

LinkedTransferQueue 结合 SynchronousQueue（直接交换）和 LinkedBlockingQueue（无界存储）的优势。

---

1.1.ArrayBlockingQueue

特点：

• 数据结构：连续数组。
• 有界：初始化时必须指定容量，意味着容量不能自动扩容，即初始化时强制分配存储元素的数组空间。
• 线程安全性： ArrayBlockingQueue读写共用可重入锁，虽然线程安全但是严重影响并发性能。

ArrayList数组结构虽然也是连续数组，但是其容量可以根据元素量自动扩容。

public class ArrayBlockingQueue<E> {
    final Object[] items;
    final ReentrantLock lock;
    private final Condition notEmpty;
    private final Condition notFull;
    public ArrayBlockingQueue(int capacity, boolean fair) {
        this.items = new Object[capacity];
        /*
            所有读写操作通过锁lock控制并发安全性，即读写操作开始前必须持有锁
        */
        lock = new ReentrantLock(fair);
        /*
            部分操作涉及阻塞操作：阻塞借助锁实现。
                1.queue满时写操作阻塞。
                2.queue空时读操作阻塞。
                3.阻塞操作等待锁被唤醒。
        */
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
    }
}

数组初始化必须指定容量：

1. 非自动扩容导致初始化时必须分配对应大小的空间。 
2. 容量达到阈值：put阻塞、offer抛出异常。
3. 容量取值为：Integer.MAX_VALUE。以int类型【4个字节】为例，Integer.MAX_VALUE * 4 约等于8G，意味着初始化时JVM需要分配8G的内存。

适用场景：线程池。 

---

1.2.LinkedBlockingQueue

特性：

• 数据结构：链表。
• 无界：初始化时无需指定容量，默认最大值为Integer.MAX_VALUE。但是实际容量根据队列元素的多少自动扩容。容易导致出现OOM。
• 线程安全性： LinkedBlockingQueue读写锁是分开的，线程安全的同时保证了并发性能。高并发性能远高于ArrayBlockingQueue。
• 所有读写操作都持有锁，部分操作根据queue满or空阻塞等待。

public class LinkedBlockingQueue<E> {
    private final ReentrantLock takeLock = new ReentrantLock();//读锁
    /*
        put、take操作提供阻塞功能：notEmpty、notFull
    */
    private final Condition notEmpty = takeLock.newCondition();
    private final ReentrantLock putLock = new ReentrantLock();//写锁
    private final Condition notFull = putLock.newCondition();
    public LinkedBlockingQueue() {
        this(Integer.MAX_VALUE);
    }
}

适用场景：消息中间件。

---

1.3.SynchronousQueue

SynchronousQueue 是一个不存储元素的阻塞队列，每个插入操作必须等待另一个线程的移除操作，反之亦然。

• poll操作非阻塞的、take操作是阻塞的。
• offer、add操作是非阻塞的、put操作是阻塞的。
• add、put必须成功添加，否则抛出异常。

如果读写都是非阻塞操作，那么写的时候如果没有线程读则直接返回null【数据直接丢失】，同理读的时候没有线程写则直接返回null。

如果读or写都是阻塞操作，那么写的时候会一直阻塞直到存在读线程消费，同理读的时候一直阻塞直到存在写线程写入数据。

public class SynchronousQueue{
	private transient volatile Transferer<E> transferer;
	public SynchronousQueue(boolean fair) {
		/*
			如果是公平则选择TransferQueue，否则选择TransferStack。默认情况下选择TransferStack
		*/ 
		transferer = fair ? new TransferQueue<E>() : new TransferStack<E>();
	}

	public E poll() {
		/*
			存在限时阻塞，但是超时时间为0，即不管队列是否存在数据都立即返回数据 or null
		*/
        return transferer.transfer(null, true, 0);
    }

    public E take() throws InterruptedException {
    	/*
    		不存在限时阻塞，即一直阻塞直到队列存在数据
    	*/
        E e = transferer.transfer(null, false, 0);
        if (e != null){
            return e;
        }//此处执行可能性小，除非存在操作可以指定超时时间，超时后没有数据返回则直接抛出异常
        Thread.interrupted();
        throw new InterruptedException();
    }

    public boolean add(E e) {
        if (offer(e)){
            return true;
        }else{//添加失败抛出异常
            throw new IllegalStateException("Queue full");
        }
    }

    public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        /*
        	存在限时阻塞，但是超时时间为0，意味着不管添加结果成功与否都立即返回
        */
        return transferer.transfer(e, true, 0) != null;
    }

    public void put(E e) throws InterruptedException {
        if (e == null) throw new NullPointerException();
        if (transferer.transfer(e, false, 0) == null) {//添加失败抛出异常
            Thread.interrupted();
            throw new InterruptedException();
        }
    }

    abstract static class Transferer<E> {
    	/*
    		timed：是否存在限时阻塞
    		nanos：超时时间
    	*/
        abstract E transfer(E e, boolean timed, long nanos);
    }
}

也就是说：所以，它更像是一个交换数据的通道，而不是传统意义上的“队列”。

特性：不存储任何元素（容量为0）；put 和 take 都会阻塞直到匹配的操作出现；线程安全。

适用场景：

1.线程池任务调度（如 CachedThreadPool = Executors.newCachedThreadPool()），工作机制：

• 每当有一个新任务提交进来，如果当前有空闲线程，就会被该线程通过 SynchronousQueue 接收。
• 如果没有可用线程，则创建一个新的线程来处理任务。
• 线程空闲超过一定时间后会被回收。

2.线程间直接通信 / 数据交换：你希望两个线程之间进行一对一的数据传递。

---

2.Deque 双端队列 

特点：可以在两端进行插入和删除操作，既可当队列用，也可当栈用。

public interface Deque<E> extends Queue<E> {}

---

2.1.LinkedList

linkFirst 在链表头部插入，适合实现栈或双端队列的前插。

linkLast 在链表尾部插入，是 add、offer等 默认行为，适合队列操作。

"first'相关操作：头部为起始位置。

"last'相关操作：尾部为起始位置。

---

3.Stack

Vector 是线程安全的，因为其所有public方法都存在synchronized修饰，而且其内部接口为数组类型。

public class Stack<E> extends Vector<E> { ... }

先进后出：从头部位置添加元素、尾部位置获取元素。

public class Stack<E> extends Vector<E> {
    public synchronized E pop() {
        E obj;
        int en = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
    }

    public synchronized E peek() {
        int len = size();
        if (len == 0)
           throw new EmptyStackException();
       // 从尾部获取元素    
       return elementAt(len - 1);
    }
}

---

4.数组 vs 链表 vs 哈希表

数组是 Java 基本数据结构，长度固定，元素为基本数据类型、对象。

数组 vs 链表：前者是有界的、后者是无界的。

---

4.1.数组

数组基于index获取数据的时间复杂度O(1)的原因：

• 数组内存区域是连续的。
• 数组元素地址计算公式：基地址 + 下标 × 单个元素大小。
• 例如：arr[3] 的地址 = 1000 + 3 × 4(int类型占用的字节数) = 1012。

---

4.1.1.列表ArrayList

列表ArrayList：元素类型是对象（包括基础数据类型的包装类型），长度可变。

ArrayList底层的数据结构为数组：内存连续 & 以时间复杂度O(1)获取数据。

列表ArrayList添加元素并不存在覆盖情况，添加行为存在两种方式：

• 尾部添加：add(index)。
• 任何位置插入：add(i,v)。将 i 到末尾的元素后移一位。

列表ArrayList插入 or 删除的平均时间复杂度为O(n)：在 ArrayList 中，除了在末尾插入/删除（平均情况接近 O(1)，但可能触发扩容为 O(n)），在其他位置插入或删除都需要移动元素以保持顺序。平均需要移动约 n/2 个元素，因此时间复杂度为 O(n)。

public abstract class AbstractList{
	// 在列表ArrayList生命周期内该变量是一直自增的。  自增发生场景：元素增加、删除之时
	protected transient int modCount = 0;
	/*
		增强 for 循环、forEach 方法底层都是 Iterator，本质是迭代遍历，直接修改集合会触发异常。

	*/
	private class Itr implements Iterator<E> {
		int cursor = 0;
		int lastRet = -1;
		/*
			迭代器中任何操作只针对变量modCount校验，并不会涉及变更。
			迭代器Iterator一旦实例化之后，变量 modCount 不能发生任何改变，意味着遍历期间绝对不能出现add、remove等操作。
			基于此通过 变量modCount 控制数组状态，一旦发生变化及早以 异常ConcurrentModificationException 终端流程。
			原因：
				1.遍历结果错误：比如迭代器以为集合还有 5 个元素，但实际已被删到 3 个，可能遍历到不存在的索引；
				2.数组越界 / 空指针：比如 ArrayList 迭代时，数组已被缩容，但迭代器仍按旧长度遍历，触发 ArrayIndexOutOfBoundsException；
				3.数据脏读 / 不一致：多线程下可能遍历到 “半修改” 的集合状态（比如元素刚被添加但未完成赋值）。
		*/ 
		int expectedModCount = modCount;

		public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
        	//抛出ConcurrentModificationException异常
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
        	// 此处证明：执行该方法之前必须执行方法next，否则lastRet必小于0
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            ...
        }
	}
}

综上所述：ArrayList不能用于并发场景【多线程操作该集合导致modCount不可控】，此种情况下优先选择CopyOnWriteArrayList。

---

4.1.2.CopyOnWriteArrayList

CopyOnWriteArrayList 是为 读多写少 场景设计的线程安全集合。

add操作：添加，而且是尾部添加。

Caffeine 是一个高性能的 Java 缓存库，旨在提供快速、灵活和高效的缓存解决方案。它是 Guava Cache 的一个替代品，提供了更高的性能和更多的功能。

public class CopyOnWriteArrayList{
    /*
        final修饰禁用原因：add|set|remove等更改操作会将新的数组引用指向array，所以非final修饰。
        private final transient volatile Object[] array; 此时只是引用array不可变，但是其内部元素是可变的。
        volatile：
            1.volatile 保证 “数组引用可见”，但不保证 “数组元素修改可见”。
            2.volatile Object[] array → 仅保证 array 这个引用的赋值操作对所有线程可见，不保证数组内部元素（如 array[0] = 1）的修改可见。
    */
    private transient volatile Object[] array;

    public E get(int index) {
        /*
            getArray()得到的引用指向旧数组在堆空间分配的内存，即使此时其他线程触发更改操作，并且将新数组引用赋值给实例变量array，
            对于此时的线程来说，其读取的数据仍为旧数组
        */
        return elementAt(getArray(), index);//直接从原数组array中读取数据
    }

    public boolean add(E e) {
        /*
            读操作：不加锁。加锁只解决 “写操作的互斥”，但解决不了 “读写冲突”。
            加锁是为了保证写操作的互斥和原子性，复制是为了 实现读写分离，让读操作无锁且安全。
            “复制” 是为了保证在写操作过程中，读操作不会看到 “被修改到一半的数组”，也不会触发异常 —— 这是单纯靠 volatile 或加锁无法实现的。
            假设缺失复制动作：
                1.其他线程b通过add(index,v)方式添加元素，导致index之后的元素整体往后移动，再赋值。如果当前线程a在线程b赋值之前读取index索引的值，可能就是空值，导致空指针。
                2.多个线程操作同一个数组，很容易导致ConcurrentModificationException。
        */
        synchronized (lock) {
            Object[] es = getArray();
            int len = es.length;
            // 数组复制时capacity加1
            es = Arrays.copyOf(es, len + 1);
            // 尾部添加：不需要注意下标跨界问题
            es[len] = e;
            setArray(es);//es指向array数组
            return true;
        }
    }    
}

set操作：更新场景，需要注意下标跨界问题。

---

4.2.链表

链表内存区域是不连续的、添加 or 删除元素并不涉及元素（内存）复制。

链表以遍历方式获取元素，其时间复杂度为O(n)。添加 or 删除：

• index已知的前提下：时间复杂度为O(1)。
• index未知的前提下：时间复杂度为O(n)。

示例：双向链表的数据结构LinkedList。

---

4.3.哈希表Hash Table

结构：数组 + hash函数。也叫散列表，是一种基于键-值（key-value）映射实现的高效数据结构，它通过一个哈希函数将键（key）转换为数组的索引，从而实现快速的插入、删除和查找操作。

解决hash冲突：

• 链表法：冲突的value添加到链表中。
• 开放寻址法：所有元素都直接存在数组中，当发生冲突时，按某种规则寻找下一个“空位”。对应的规则例如：线性探测法、平方探测、双重hash。

查找、添加、删除的最好时间复杂度O(1)，最坏时间复杂度为O(n)。

---

4.4.Set集合

Set集合：无序、不重复。实现类包括：

• HashSet：底层结构是HashMap。
• TreeSet：底层结构是TreeMap。
• LinkedHashSet：底层结构是LinkedHashMap。
• 上述所有实现类的元素都存储在对应Map中的key中，value没有任何作用。
• Set集合可以add元素，但是没有get方式获取元素，只能通过迭代器遍历方式获取。
• Set 是为了快速查找元素是否存在而设计的，它不关心元素的顺序，也不提供通过位置访问的功能。

---

4.5.Map结构

HashMap结构：数组 + 链表 / 红黑树。数组元素Node同时也是链表结构。

版本	核心数据结构	解决的问题
JDK 1.7	数组 + 单向链表	基础哈希存储，但链表过长查询慢
JDK 1.8+	数组 + 单向链表 + 红黑树	链表长度超过阈值（默认 8）时转红黑树，提升查询性能

public class HashMap<K,V> extends AbstractMap<K,V> mplements Map<K,V>{

    public class HashMap<K,V> extends AbstractMap<K,V> mplements Map<K,V>{
        //通过hash函数~hash(key)，确定kv对应的Node在数组中的位置
        transient Node<K,V>[] table;
        static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;// 除了作为数组元素，自身也是链表结构，解决hash冲突问题
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }

            public final K getKey() { return key; }
            public final V getValue() { return value; }  
        }
    }

    public V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0){
            n = (tab = resize()).length;
        }
        if ((p = tab[i = (n - 1) & hash]) == null){
            tab[i] = newNode(hash, key, value, null);
        }else {
            Node<K,V> e; K k;
            // key相等的条件：hash 是节点p一个字段，取值即为key的哈希值，key完全相等  or key字面量值相等
            if (p.hash == hash && (
                (k = p.key) == key || (key != null && key.equals(k)))
            ){
                e = p;//如果key冲突
            }else if (p instanceof TreeNode){
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            }else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1){
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
                        break;
                    }
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null){
                    e.value = value;
                }
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold){
            resize();
        }
        afterNodeInsertion(evict);
        return null;
    }
}

---

LinkedHashMap 是 HashMap 的子类，核心特性是在 HashMap 哈希表结构的基础上，增加了双向链表来维护键值对的访问 / 插入顺序。

public class LinkedHashMap<K,V> extends HashMap<K,V> mplements Map<K,V>{

    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;
    
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        // 单独维护一个列表：保证有序性。注意此时有序性是指Entry有序性，而非key or value有序
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null){
            head = p;
        }else {
            p.before = last;
            last.after = p;
        }
    }

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
}

LinkedHashMap 完全复用了 HashMap 的底层哈希表结构（数组 + 链表 + 红黑树），同时新增了双向链表来记录键值对的顺序。

复用 HashMap 的哈希表结构：

• 底层仍有 Node[] table 桶数组，解决哈希冲突的方式（链表 / 红黑树）与 HashMap 完全一致；
• 哈希寻址、扩容、冲突处理的逻辑均继承自 HashMap，保证了哈希表的高效查询特性。

新增的双向链表（核心差异化），LinkedHashMap 重写了哈希表的节点类型（Entry），在 HashMap.Node 的基础上增加了 before 和 after 指针，形成双向链表：

• 双向链表的作用：串联所有键值对，维护其「插入顺序」或「访问顺序」。
• 链表头 / 尾指针：LinkedHashMap 还维护了两个全局指针：指向双向链表的头节点和尾节点，快速定位链表首尾。

双向链表的核心价值是支持两种顺序，通过构造函数的 accessOrder 参数控制：

顺序模式	accessOrder 值	含义
插入顺序（默认）	false	双向链表按键值对的插入顺序排列，先插入的在前，后插入的在后；即使后续访问已存在的键，顺序也不变；
访问顺序	true	双向链表按键值对的最近访问顺序排列：每次 get()/put() 访问已有键时，该节点会被移到链表尾部；

---

TreeMap：红黑树。有序【key】（自然顺序或指定比较器顺序），查询、插入、删除效率为 O (log n)，线程不安全。

特点：

• 没有哈希表，红黑树中每个节点均为Entry。
• key存在与否：通过比较器（Comparator）或 Comparable 接口来判断两个 key 是否 “相等”。

public class TreeMap<K,V> extends AbstractMap<K,V> mplements Map<K,V>{
    private transient Entry<K,V> root;

    public V put(K key, V value) {//构建红黑树的过程
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        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
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null){
                throw new NullPointerException();
            }
            @SuppressWarnings("unchecked")
            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);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
    }
}