Ch3nyang's blog web_stories

post

assignment_ind

about

data_object

github

local_offer

tag

rss_feed

rss

Java 集合是包括了 java.util.Collectionjava.util.Map 两个接口的集合类的总称。

下面的图展示了它们的继承关系。

Collection类继承关系图

Map类继承关系图

Collection

Collection 是集合的根接口,表示一组对象的集合。所有 Collection 都拥有以下方法:

  • boolean add(E e):添加元素 e
  • boolean addAll(Collection<? extends E> c):添加集合 c 中的所有元素
  • void clear():清空集合
  • boolean contains(Object o):判断集合中是否包含元素 o
  • boolean containsAll(Collection<?> c):判断集合中是否包含集合 c 中的所有元素
  • boolean isEmpty():判断集合是否为空
  • Iterator<E> iterator():返回集合的迭代器
  • boolean remove(Object o):删除元素 o,如果有多个满足条件的元素,只删除第一个
  • boolean removeAll(Collection<?> c):删除集合 c 中的所有元素
  • boolean retainAll(Collection<?> c):删除集合中不在集合 c 中的所有元素
  • int size():返回集合的元素个数
  • Object[] toArray():将集合转换为数组

集合的遍历方式有三种:

  • 使用 for 循环遍历集合

    for (int i = 0; i < collection.size(); i++) {
        System.out.println(collection.get(i));
    }
    
  • 使用 for-each 循环遍历集合

    for (Object o : collection) {
        System.out.println(o);
    }
    
  • 使用迭代器遍历集合,可以在遍历时删除元素

    Iterator<Object> iterator = collection.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
        iterator.remove();
    }
    
  • 使用 ListIterator 遍历集合,它支持双向遍历,并且可以在遍历时修改集合

    ListIterator<Object> listIterator = collection.listIterator();
    while (listIterator.hasNext()) {
        System.out.println(listIterator.next());
        listIterator.remove();
    }
    
  • 使用 Stream 遍历集合

    collection.stream().forEach(System.out::println)
              .collect(Collectors.toList());
    
  • 使用 forEach 遍历集合

    collection.forEach(System.out::println);
    

List

ListCollection 的子接口,表示一个有序的集合。它允许重复元素,并且可以通过索引访问元素。List 分为三类

ArrayList

ArrayList:基于动态数组实现,支持随机访问,适合频繁读取的场景

除了 Collection 的方法外,它包括了以下方法:

  • E get(int index):返回指定索引位置的元素
  • int indexOf(Object o):返回元素 o 在列表中第一次出现的位置,如果不存在则返回 -1
  • int lastIndexOf(Object o):返回元素 o 在列表中最后一次出现的位置,如果不存在则返回 -1
  • E set(int index, E element):将指定索引位置的元素替换为 element
  • List<E> subList(int fromIndex, int toIndex):返回一个新的 List,包含 \([\text{fromIndex}, \text{toIndex})\) 范围内的元素

ArrayList 的元素本身存储在一个 Object[] 数组中,里面还有一个成员变量 size,表示当前元素的个数。

transient Object[] elementData;
private int size;

transient 关键字表示这些变量不会被序列化。

ArrayList 的默认初始容量为 10。容量不足时,它会创建 1.5 倍大小的新数组,并将旧数组中的元素复制到新数组中。

private static final int DEFAULT_CAPACITY = 10;

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

LinkedList

LinkedList:基于双向链表实现,支持频繁插入和删除的场景

它包括了以下方法:

  • void addFirst(E e):在列表的开头添加元素 e
  • void addLast(E e):在列表的末尾添加元素 e
  • E getFirst():返回列表的第一个元素
  • E getLast():返回列表的最后一个元素
  • E removeFirst():删除列表的第一个元素并返回它
  • E removeLast():删除列表的最后一个元素并返回它

LinkedList 存储了头节点、尾节点、以及元素的个数。

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

每个节点都包含了具体的元素、前后两个指针。

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

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

至于其插入、删除等操作就是平平无奇的双向链表操作了。

Vector

Vector 是一个动态数组,支持随机访问。它基本就是 ArrayList 的古早版本。

Vector 的方法与 ArrayList 基本相同。

Vector 有个子类 Stack,表示一个后进先出的集合。它额外包括了以下方法:

  • E push(E item):添加元素 item
  • E pop():删除并返回栈顶元素
  • E peek():返回栈顶元素
  • boolean empty():判断栈是否为空
  • int search(Object o):返回元素 o 在栈中的位置,如果不存在则返回 -1

Vector 是线程安全的,而如果不需要线程安全,不建议使用 Vector,而是使用 ArrayList

它使用数组来存储元素。当容量不足时,它会创建两倍大小的新数组,并将旧数组中的元素复制到新数组中。

Set

SetCollection 的子接口,表示一个不允许重复元素的集合。我们正常会使用 HashSetTreeSet

HashSet

HashSet:基于哈希表实现,支持快速查找和插入

它的方法与 Collection 相同

他有一个有序的子类 LinkedHashSet,它保持插入顺序。

TreeSet

TreeSet:基于红黑树实现,支持有序的元素

除了 Collection 的方法外,它包括了以下方法:

  • E first():返回集合中的第一个元素
  • E last():返回集合中的最后一个元素
  • E poolFirst():删除集合中的第一个元素并返回它
  • E poolLast():删除集合中的最后一个元素并返回它
  • SortedSet<E> subSet(E fromElement, E toElement):返回一个新的 SortedSet,包含 \([\text{fromElement}, \text{toElement})\) 范围内的元素
  • SortedSet<E> headSet(E toElement):返回一个新的 SortedSet,包含 \([, \text{toElement})\) 范围内的元素
  • SortedSet<E> tailSet(E fromElement):返回一个新的 SortedSet,包含 \([\text{fromElement}, ]\) 范围内的元素

TreeSet 是有序的,它的元素必须实现 Comparable 接口,或者在创建 TreeSet 时传入一个 Comparator 对象。

Queue

QueueCollection 的子接口,表示一个先进先出的集合。它额外包括了以下方法:

  • boolean offer(E e):添加元素 e
  • E poll():删除并返回队列的第一个元素
  • E peek():返回队列的第一个元素
  • E element():返回队列的第一个元素

虽然也能使用 addremove 方法,但不推荐使用,因为它们在队列为空时会抛出异常。相比之下,offerpoll 方法在队列为空时会返回 null

Queue 有两个重要的实现类:

PriorityQueue

PriorityQueue:基于堆实现,支持优先级队列。

它的方法与 Queue 相同。

PriorityQueue 默认情况下是小根堆,如果想要实现大根堆,可以在创建时传入一个 Comparator 对象。以下三种写法都是可以的:

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

PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
});

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);

ArrayDeque

ArrayDeque:双端队列,支持在两端添加和删除元素

它额外包括了以下方法:

  • boolean offerFirst(E e):在队列的开头添加元素 e
  • boolean offerLast(E e):在队列的末尾添加元素 e
  • E peekFirst():返回队列的第一个元素
  • E peekLast():返回队列的最后一个元素
  • E pollFirst():删除队列的第一个元素并返回它
  • E pollLast():删除队列的最后一个元素并返回它
  • E getFirst():返回队列的第一个元素
  • E getLast():返回队列的最后一个元素

Map

Map 是一个键值对集合,表示一组映射关系。它不允许重复的键,但允许重复的值。

Map 的方法包括:

  • void clear():清空所有键值对
  • boolean containsKey(Object key):判断是否包含键 key
  • boolean containsValue(Object value):判断是否包含值 value
  • V get(Object key):返回键 key 对应的值
  • V put(K key, V value):添加键值对 keyvalue
  • void putAll(Map<? extends K, ? extends V> m):添加 Map m 中的所有键值对
  • V remove(Object key):删除键 key 对应的键值对
  • Set entrySet():返回所有键值对的集合,集合中的元素是 Map.Entry 对象

    • K getKey():返回键
    • V getValue():返回值
    • V setValue(V value):设置值并返回旧值
  • Set keySet():返回所有键的集合
  • Collection values():返回所有值的集合
  • boolean isEmpty():判断 Map 是否为空
  • int size():返回键值对的个数
  • V getOrDefault(Object key, V defaultValue):返回键 key 对应的值,如果不存在则返回 defaultValue
  • V putIfAbsent(K key, V value):添加键值对 keyvalue,如果键 key 已经存在则不添加
  • void forEach(BiConsumer<? super K, ? super V> action):对每个键值对执行操作 action

    例如想要将 Map 中的每个值加 1,可以这样写:

    map.forEach((k, v) -> {
        map.put(k, v + 1);
    });
    
  • V replace(K key, V value):将键 key 对应的值替换为 value,如果键 key 不存在则不替换

Map 有多个实现类,最常用的有:

HashMap

HashMap 基于哈希表实现,支持快速查找和插入。

与其类似的还有:

  • TreeMap:基于红黑树实现,支持有序的键
  • LinkedHashMap:与 HashMap 类似,但保持插入顺序

HashMapEntry 对象的形式存储键值对。

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

    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 final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;

        return o instanceof Map.Entry<?, ?> e
                && Objects.equals(key, e.getKey())
                && Objects.equals(value, e.getValue());
    }
}

然后将这些 Entry 对象存储在一个数组中,数组的每个元素称为一个桶(bucket)。

transient Node<K,V>[] table;

HashMap 的默认初始容量为 16,最大容量为 \(2^30\)。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap 在初始化时可以指定初始容量和负载因子。

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

然而,这个指定的初始容量并不是直接用来创建数组的,而是用来计算真实的初始容量

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这个函数的作用是返回大于等于 cap 的最小的 2 的幂次方。例如 cap 为 20 时,返回 32。

HashMap 的负载因子是一个浮点数,表示数组的使用率。默认值为 0.75。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

元素放入 HashMap 时,会先计算出它的哈希值,然后对数组的长度取模,得到它在数组中的位置。不过,它用了位运算来优化:

(tab.length - 1) & hash;

HashMap 处理哈希冲突的方式是链地址法,即每个桶中存储一个链表或则红黑树。

其中,由于 HashMap 在历史原因的影响,并不强制要求键实现 compareTo 方法,因此它使用了一套自己的方法来比较键的大小。

  • 先比较 hash 大小
  • 如果键实现了 Comparable 接口,则使用它的 compareTo 方法
  • 否则调用 tieBreakOrder 方法
static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
          compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
              -1 : 1);
    return d;
}

我们来看它的插入操作:

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

这个函数做了这样几件事情:

  • 如果数组不存在或者长度为 0,则调用扩容方法创建一个新的数组
  • 如果要插入的键已经存在,更具是否允许重复键的标志,替换为新值
  • 如果不存在,则创建一个新的 Node 对象,并将它插入到链表或者红黑树中
  • 如果链表的长度超过了 8,则将链表转换为红黑树

    static final int TREEIFY_THRESHOLD = 8;
    

    如果红黑树的长度小于 6,则将红黑树转换为链表

    static final int UNTREEIFY_THRESHOLD = 6;
    
  • 如果键值对数量大于阈值,则扩容

接下来来看扩容的代码:

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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        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;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                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 { // preserve order
                    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;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

它做了这样几件事情:

  • 计算新的容量和阈值

    • 如果当前数组已经初始化过了

      • 如果旧的容量 \(\geq 2^{30}\),则不再扩容,并将阈值设为最大值
      • 如果新的容量 \(< 2^{30}\),且旧的容量 \(\geq 16\),则将容量翻倍、阈值也翻倍
    • 如果阈值大于 0,且桶未被初始化过

      • 新的容量为阈值
      • 新的阈值为容量乘以负载因子
    • 如果阈值为 0 且桶未初始化过

      • 新容量为默认值 16
      • 新阈值为容量乘以负载因子,即 12
  • 重新分配桶内的元素

    • 如果桶内是链表,计算 hash & oldCap,决定元素放入新桶的哪个位置

      • 如果 hash & oldCap == 0,则放入 loHead
      • 否则放入 hiHead
    • 如果桶内是红黑树,则调用 split 方法将它拆分成两个红黑树

      • 红黑树在插入时,使用一个指针维护了插入的顺序,每个节点都有一个 next 指针指向下一个节点
      • 这使得它可以像链表一样拆分,它会先拆分为两个链表,然后再根据条件决定是否树化

LinkedHashMap

LinkedHashMapHashMap 类似,但保持插入顺序。

具体来讲,就是它额外使用了两个指针来构成了双向链表。

并发

Java 同时提供了一些线程安全的集合类,位于 java.util.concurrent 包中。

CopyOnWriteArrayList

CopyOnWriteArrayListArrayList 提供了写时复制的功能。

它的实现思路就是一把大锁保平安,数组本身也用了 volatile 关键字来保证可见性。

final transient Object lock = new Object();
private transient volatile Object[] array;

它的读操作没有锁,因为它是线程安全的:

  • 首先直接获取整个数组的引用
  • 然后再根据索引获取元素

而写操作则是直接 synchronized 整个方法。

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArray(es);
        return true;
    }
}

在这个方法中,它首先复制出了一份数组,然后在这份数组上进行操作,最后再将它替换回去。

这把大锁保证了同时只有一个线程能操作数组。

它的删除使用了类似的方法。

public E remove(int index) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        E oldValue = elementAt(es, index);
        int numMoved = len - index - 1;
        Object[] newElements;
        if (numMoved == 0)
            newElements = Arrays.copyOf(es, len - 1);
        else {
            newElements = new Object[len - 1];
            System.arraycopy(es, 0, newElements, 0, index);
            System.arraycopy(es, index + 1, newElements, index,
                              numMoved);
        }
        setArray(newElements);
        return oldValue;
    }
}

ConcurrentHashMap

ConcurrentHashMap 是一个线程安全的哈希表,支持高并发的读写操作。

HashMap 不同,ConcurrentHashMap 使用了分段锁的机制来提高并发性能。在 JDK 1.8 之后,它采用了 CAS + synchronized 的方式来保证线程安全。

它的核心数据结构与 HashMap 类似,也是一个数组 + 链表/红黑树的结构:

transient volatile Node<K,V>[] table;

不过,它的 Node 类使用了 volatile 关键字来保证可见性:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    // ...existing code...
}

它的插入操作使用了 CASsynchronized 来保证线程安全:

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else if (onlyIfAbsent
                  && fh == hash
                  && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                  && (fv = f.val) != null)
            return fv;
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                  (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                        value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                    // ...existing code...
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

这个方法的核心思路是:

  • 如果桶为空,使用 CAS 操作直接插入新节点
  • 如果桶正在扩容,帮助扩容
  • 否则对桶的头节点加锁,然后在链表或红黑树中插入元素

读操作则不需要加锁,因为 valnext 都是 volatile 的:

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

ConcurrentHashMap 的扩容也是分段进行的,每次只扩容一部分桶,这样可以减少锁的竞争。

ConcurrentLinkedQueue

ConcurrentLinkedQueue 是一个基于链表实现的线程安全的无界队列。

它使用了 CAS 操作来保证线程安全,而不是使用锁。

private transient volatile Node<E> head;
private transient volatile Node<E> tail;

private static class Node<E> {
    volatile E item;
    volatile Node<E> next;
    // ...existing code...
}

它的插入操作使用了 CAS 来保证线程安全:

public boolean offer(E e) {
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e);

    for (Node<E> t = tail, p = t;;) {
        Node<E> q = p.next;
        if (q == null) {
            if (p.casNext(null, newNode)) {
                if (p != t)
                    casTail(t, newNode);
                return true;
            }
        }
        else if (p == q)
            p = (t != (t = tail)) ? t : head;
        else
            p = (p != t && t != (t = tail)) ? t : q;
    }
}