Collections

A collection — sometimes called a container — is simply an object that groups multiple elements into a single unit.

Collections are used to store, retrieve, manipulate, and communicate aggregate data.

https://docs.oracle.com/javase/tutorial/collections/index.html

Arrays vs. Collections

Collections Framework

A collections framework, for example C++ Standard Template Library (STL), is a unified architecture for representing and manipulating collections. All collections frameworks contain the following:

• Interfaces: These are abstract data types that represent collections.
• Implementations: These are the concrete implementations of the collection interfaces.
• Algorithms: These are the methods that perform useful computations, such as searching and sorting.

Interfaces

The core collection interfaces encapsulate different types of collections. These interfaces allow collections to be manipulated independently of the details of their representation. Core collection interfaces form a hierarchy.

Collection

public interface Collection<E> extends Iterable<E>

The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered.

This interface is typically used to pass collections around and manipulate them where maximum generality is desired.

https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html

Traversing Collections

There are three ways to traverse collections:

1. using aggregate operations (talk later)
2. with the for-each construct
3. by using Iterators

for-each Construct

The for-each construct allows you to concisely traverse a collection or array using a for loop — see The for Statement. The following code uses the for-each construct to print out each element of a collection on a separate line.

for (Object o : collection)
    System.out.println(o);

Iterable

public interface Iterable<T>

Implementing this interface allows an object to be the target of the "for-each loop" statement

https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html

Iterators

An Iterator is an object that enables you to traverse through a collection and to remove elements from the collection selectively, if desired. You get an Iterator for a collection by calling its iterator method. The following is the Iterator interface.

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove(); //optional
}

https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

Iterator 使用示例

List<String> list = Arrays.asList("a", "b", "c");
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String element = it.next();
    System.out.println(element);
}
Iterator<String> it2 = list.iterator();
while (it2.hasNext()) {
    if (it2.next().equals("b")) {
        it2.remove();  // 安全删除，不会抛出 ConcurrentModificationException
    }
}

每次 next() 后只能调用一次 remove()。

Collection Interface Bulk Operations

Bulk operations perform an operation on an entire Collection.

• containsAll
• addAll
• removeAll
• retainAll
• clear

Collection Interface Array Operations

The toArray methods are provided as a bridge between collections and older APIs that expect arrays on input. The array operations allow the contents of a Collection to be translated into an array. The simple form with no arguments creates a new array of Object. The more complex form allows the caller to provide an array or to choose the runtime type of the output array.

Object[] a = c.toArray();

The List Interface

A List is an ordered Collection (sometimes called a sequence). Lists may contain duplicate elements. In addition to the operations inherited from Collection, the List interface includes operations of positional access, search, iteration and range-view.

The Java platform contains two general-purpose List implementations. ArrayList, which is usually the better-performing implementation, and LinkedList which offers better performance under certain circumstances.

ArrayList vs. LinkedList

Performance difference?

ArrayList vs LinkedList 性能对比

The Set Interface

A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction. The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited. Two Set instances are equal if they contain the same elements.

The Java platform contains three general-purpose Set implementations: HashSet, TreeSet and LinkedHashSet.

HashSet

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.

This class offers constant time performance for the basic operations (add, remove, contains and size).

https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

TreeSet

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable

A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time.

• 元素自动排序（自然顺序或自定义 Comparator）
• 所有操作时间复杂度 O(log n)

TreeSet<Integer> set = new TreeSet<>();
set.add(3); set.add(1); set.add(2); // 遍历顺序：1, 2, 3（自动排序）

LinkedHashSet

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, Serializable

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation maintains a doubly-linked list running through all entries, preserving insertion order.

• 保持插入顺序，性能接近 HashSet（O(1) 基本操作）
• 适合需要顺序且去重的场景

LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("c"); set.add("a"); set.add("b"); // 遍历顺序：c, a, b（保持插入顺序）

The Map Interface

A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. It models the mathematical function abstraction. The Map interface includes methods for basic operations (such as put, get, remove, containsKey, containsValue, size, and empty), bulk operations (such as putAll and clear), and collection views (such as keySet, entrySet, and values).

The Java platform contains three general-purpose Map implementations: HashMap, TreeMap, and LinkedHashMap.

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

HashMap

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

Hash table based implementation of the Map interface. This implementation permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

HashMap Internal

Two parameters affect its performance: initial capacity and load factor. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed.

JDK 8 的优化：链表转红黑树

• JDK 7：冲突时使用链表，极端情况下退化为 O(n)
• JDK 8：当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树，保证 O(log n)
• 退化：当红黑树节点数 ≤ 6 时，转回链表

容量与负载因子

• 默认初始容量：16 ；默认负载因子：0.75
• 扩容时机：size > capacity * loadFactor
• 扩容操作：容量翻倍，重新计算 hash 并重新分布

Hash 冲突处理

1. 计算 hash：(h = key.hashCode()) ^ (h >>> 16)（高16位异或，减少冲突）
2. 定位桶：(n - 1) & hash（n 为容量，必须是 2 的幂）
3. 处理冲突：链表或红黑树

线程安全

• HashMap：非线程安全，多线程环境下可能导致数据不一致
• ConcurrentHashMap：线程安全替代方案（分段锁或 CAS）

TreeMap

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

A Red-Black tree based NavigableMap implementation.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

TreeMap Internal

红黑树基础

红黑树是一种自平衡二叉搜索树

保证最坏情况下 O(log n) 的查找、插入、删除，相比 AVL 树，旋转操作更少，插入/删除性能更好，适合需要有序且频繁更新的场景

LinkedHashMap

Hash table and linked list implementation of the Map interface, with predictable iteration order.

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.

LinkedHashMap 应用：LRU 缓存

LinkedHashMap 可以通过重写 removeEldestEntry() 实现 LRU（Least Recently Used）缓存：

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(16, 0.75f, true);  // accessOrder=true 表示按访问顺序排序
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;  // 超过容量时删除最久未访问的元素
    }
}

使用示例

LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("1", "one");
cache.put("2", "two");
cache.put("3", "three");
cache.get("1");  // 访问 "1"，使其成为最近使用的
cache.put("4", "four");  // 添加 "4"，"2" 被移除（最久未访问）

Back to The Set Interface

A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction. The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited. Two Set instances are equal if they contain the same elements.

The Java platform contains three general-purpose Set implementations: HashSet, TreeSet and LinkedHashSet.

The Queue Interface

A collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations.

https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

The Deque Interface

A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck". Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.

https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html

Queue 实现类

PriorityQueue

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

基于堆（通常是最小堆）实现的优先级队列。元素按自然顺序或Comparator排序。主要应用场景：任务调度、Top-K、Dijkstra 算法等

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3); pq.offer(1); pq.offer(2);
pq.poll();  // 返回 1（最小元素）
pq.poll();  // 返回 2

Deque 实现类

ArrayDeque

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable

基于循环数组实现的双端队列。比 LinkedList 更高效（无额外节点开销），比 Stack 更推荐（Stack 继承自 Vector，已过时）。（作为栈使用时比 Stack 快，作为队列使用时比 LinkedList 快）

Deque<String> deque = new ArrayDeque<>();
deque.offerFirst("first");   // 头部插入
deque.offerLast("last");      // 尾部插入
deque.pollFirst();            // 头部移除
deque.pollLast();             // 尾部移除

Collections 工具类

java.util.Collections 提供了大量静态方法操作集合：

排序与查找

List<Integer> list = Arrays.asList(3, 1, 4, 1, 5);
Collections.sort(list);                    // [1, 1, 3, 4, 5]
int index = Collections.binarySearch(list, 3);  // 2（必须先排序）
Collections.reverse(list);                 // [5, 4, 3, 1, 1]
Collections.shuffle(list);                 // 随机打乱

同步包装

将非线程安全的集合包装成线程安全版本，通过方法级同步（synchronized）保证多线程访问安全。

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>());
// 返回线程安全的包装器（方法级同步）

注意：多个操作的组合仍需手动同步，否则仍可能不安全。

不可变集合

创建后无法修改的集合，任何修改操作（add、remove、set）都会抛出 UnsupportedOperationException。

List<String> immutable = Collections.unmodifiableList(list);

除了保证数据不被意外修改外，为什么需要不可变集合？

• 线程安全：天然线程安全，多线程环境下无需同步
• 函数式编程：符合不可变性的函数式编程原则，避免副作用
• 性能优化：可以安全地共享，无需防御性拷贝
• 简化代码：减少对数据修改的担心，代码更简洁可靠

注意：unmodifiableList() 返回的是视图，底层集合修改会影响视图；需要真正不可变时，应复制数据后再包装。

其他工具方法

Collections.max(list);           // 最大值
Collections.min(list);           // 最小值
Collections.frequency(list, 1);  // 出现次数
Collections.replaceAll(list, 1, 9);  // 替换所有匹配元素

Summary of Interfaces

• Collection interface
  • The Set interface does not allow duplicate elements
  • The List interface provides for an ordered collection
  • The Queue interface enables additional insertion, extraction, and inspection operations
  • The Deque interface enables operations at both the ends
• Map's subinterface, SortedMap, maintains its key-value pairs in ascending order or in an order specified by a Comparator.

Back to Traversing Collections

There are three ways to traverse collections:

1. using aggregate operations (talk now)
2. with the for-each construct
3. by using Iterators

Aggregate Operations

In JDK 8 and later, the preferred method of iterating over a collection is to obtain a stream and perform aggregate operations on it.

Aggregate operations are often used in conjunction with lambda expressions to make programming more expressive.

myShapesCollection.stream()
.filter(e -> e.getColor() == Color.RED)
.forEach(e -> System.out.println(e.getName()));

https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#stream--

Stream

public interface Stream<T> extends BaseStream<T,Stream<T>>

A sequence of elements supporting sequential and parallel aggregate operations.

https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html

Stream API 常用操作

中间操作（返回 Stream）

List<String> list = Arrays.asList("apple", "banana", "cherry", "date");
// map：转换元素
list.stream().map(String::toUpperCase).forEach(System.out::println);
// flatMap：扁平化
List<List<String>> nested = Arrays.asList(
    Arrays.asList("a", "b"), Arrays.asList("c", "d"));
nested.stream().flatMap(List::stream).forEach(System.out::println);
// filter：过滤
list.stream().filter(s -> s.length() > 5).forEach(System.out::println);
// distinct：去重
Arrays.asList(1, 2, 2, 3).stream().distinct().forEach(System.out::println);
// sorted：排序
list.stream().sorted().forEach(System.out::println);

终端操作（返回结果）

// reduce：归约
int sum = Arrays.asList(1, 2, 3, 4).stream()
    .reduce(0, Integer::sum);  // 10
// collect：收集
List<String> upper = list.stream()
    .map(String::toUpperCase)
    .collect(Collectors.toList());
// groupingBy：分组
Map<Integer, List<String>> byLength = list.stream()
    .collect(Collectors.groupingBy(String::length));
// partitioningBy：分区
Map<Boolean, List<String>> partitioned = list.stream()
    .collect(Collectors.partitioningBy(s -> s.length() > 5));

Parallel Stream

Likewise, you could easily request a parallel stream, which might make sense if the collection is large enough and your computer has enough cores:

myShapesCollection.parallelStream()
.filter(e -> e.getColor() == Color.RED)
.forEach(e -> System.out.println(e.getName()));

并行流适用场景

• 数据量大：通常 > 10,000 元素
• CPU 密集型操作：计算复杂，而非简单过滤
• 多核 CPU：充分利用多核优势

注意事项

1. 性能开销：线程创建、任务分割、结果合并有开销

   • 小数据集可能比串行流更慢
   • 使用 ForkJoinPool 管理线程池

2. 顺序保证：并行流不保证顺序，需要顺序时使用 forEachOrdered()

注意事项

3. 线程安全：确保操作无状态、无副作用

   // 错误：共享可变状态
   List<Integer> result = new ArrayList<>();
   list.parallelStream().forEach(result::add);  // 线程不安全
   
   // 正确：使用 collect
   List<Integer> result = list.parallelStream()
       .collect(Collectors.toList());
   

Java 8 Stream API

https://www.baeldung.com/java-8-streams

https://stackify.com/streams-guide-java-8/

Reactive Programming

In computing, reactive programming is a declarative programming paradigm concerned with data streams and the propagation of change. With this paradigm, it's possible to express static (e.g., arrays) or dynamic (e.g., event emitters) data streams with ease, and also communicate that an inferred dependency within the associated execution model exists, which facilitates the automatic propagation of the changed data flow.

https://en.wikipedia.org/wiki/Reactive_programming

http://www.reactive-streams.org

Java 9 Reactive Streams

public final class Flow extends Object

Interrelated interfaces and static methods for establishing flow-controlled components in which Publishers produce items consumed by one or more Subscribers, each managed by a Subscription.
These interfaces correspond to the reactive-streams specification. Communication relies on a simple form of flow control that can be used to avoid resource management problems that may otherwise occur in "push" based systems.

https://docs.oracle.com/javase/9/docs/api/java/util/concurrent/Flow.html

Java 9 Reactive Streams Tutorial

https://www.baeldung.com/java-9-reactive-streams