Ch3nyang's blog | 深入 Java (3) -Java 集合

Java 集合是包括了 java.util.Collection 和 java.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 循环遍历集合

Java

for (int i = 0; i < collection.size(); i++) {
    System.out.println(collection.get(i));
}

使用 for-each 循环遍历集合
Java
```
for (Object o : collection) {
    System.out.println(o);
}
```

使用迭代器遍历集合，可以在遍历时删除元素

Java

Iterator<Object> iterator = collection.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
    iterator.remove();
}

使用 ListIterator 遍历集合，它支持双向遍历，并且可以在遍历时修改集合

Java

ListIterator<Object> listIterator = collection.listIterator();
while (listIterator.hasNext()) {
    System.out.println(listIterator.next());
    listIterator.remove();
}

使用 Stream 遍历集合

Java

collection.stream().forEach(System.out::println)
          .collect(Collectors.toList());

使用 forEach 遍历集合
Java
```
collection.forEach(System.out::println);
```

List

List 是 Collection 的子接口，表示一个有序的集合。它允许重复元素，并且可以通过索引访问元素。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，表示当前元素的个数。

Java

transient Object[] elementData;
private int size;

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

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

Java

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 存储了头节点、尾节点、以及元素的个数。

Java

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

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

Java

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

Set 是 Collection 的子接口，表示一个不允许重复元素的集合。我们正常会使用 HashSet 和 TreeSet。

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

Queue 是 Collection 的子接口，表示一个先进先出的集合。它额外包括了以下方法：

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

虽然也能使用 add 和 remove 方法，但不推荐使用，因为它们在队列为空时会抛出异常。相比之下，offer 和 poll 方法在队列为空时会返回 null。

Queue 有两个重要的实现类：

PriorityQueue

PriorityQueue：基于堆实现，支持优先级队列。

它的方法与 Queue 相同。

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

Java

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)：添加键值对 key 和 value
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)：添加键值对 key 和 value，如果键 key 已经存在则不添加
void forEach(BiConsumer<? super K, ? super V> action)：对每个键值对执行操作 action

例如想要将 Map 中的每个值加 1，可以这样写：
Java
```
map.forEach((k, v) -> {
    map.put(k, v + 1);
});
```
V replace(K key, V value)：将键 key 对应的值替换为 value，如果键 key 不存在则不替换

Map 有多个实现类，最常用的有：

HashMap

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

与其类似的还有：

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

HashMap 以 Entry 对象的形式存储键值对。

Java

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）。

Java

transient Node<K,V>[] table;

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

Java

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

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

Java

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

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

Java

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。

Java

static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

Java

(tab.length - 1) & hash;

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

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

先比较 hash 大小
如果键实现了 Comparable 接口，则使用它的 compareTo 方法
否则调用 tieBreakOrder 方法

Java

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

我们来看它的插入操作：

Java

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，则将链表转换为红黑树
Java
```
static final int TREEIFY_THRESHOLD = 8;
```
如果红黑树的长度小于 6，则将红黑树转换为链表
Java
```
static final int UNTREEIFY_THRESHOLD = 6;
```
如果键值对数量大于阈值，则扩容

接下来来看扩容的代码：

Java

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

LinkedHashMap 与 HashMap 类似，但保持插入顺序。

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

并发

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

CopyOnWriteArrayList

CopyOnWriteArrayList 为 ArrayList 提供了写时复制的功能。

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

Java

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

它的读操作没有锁，因为它是线程安全的：

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

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

Java

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

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

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

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

Java

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 类似，也是一个数组 + 链表/红黑树的结构：

Java

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

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

Java

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

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

Java

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 操作直接插入新节点
如果桶正在扩容，帮助扩容
否则对桶的头节点加锁，然后在链表或红黑树中插入元素

读操作则不需要加锁，因为 val 和 next 都是 volatile 的：

Java

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 操作来保证线程安全，而不是使用锁。

Java

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 来保证线程安全：

Java

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

深入 Java | (3)

Java 集合

Collection

List

ArrayList

LinkedList

Vector

Set

HashSet

TreeSet

Queue

PriorityQueue

ArrayDeque

Map

HashMap

LinkedHashMap

并发

CopyOnWriteArrayList

ConcurrentHashMap

ConcurrentLinkedQueue

Series 深入 Java

Suggested Posts

Comments

深入 Java | (3) Java 集合

Collection

List

ArrayList

LinkedList

Vector

Set

HashSet

TreeSet

Queue

PriorityQueue

ArrayDeque

Map

HashMap

LinkedHashMap

并发

CopyOnWriteArrayList

ConcurrentHashMap

ConcurrentLinkedQueue

Series 深入 Java

Suggested Posts

Comments

Share This Post

深入 Java | (3)

Java 集合