Java 集合框架中的 Collections 类

此类仅包含操作或返回集合的静态方法。包括

用于操作集合的通用算法，比如，排序、查找最大最小元素、二分查找等
不可变集合，通过方法将集合转换为不可修改的版本，比如，unmodifiableList、unmodifiableSet
“包装器”，返回由指定集合支持的新集合，比如，同步包装器，synchronizedList、synchronizedSet 等，可以将非线程安全的集合包装为线程安全的版本。
集合的批量操作
以及一些其他零散的方法，比如随机打乱集合中元素的顺序，交换集合中的元素位置，旋转集合等。

如果传递给这些方法的集合或类对象为 null，则所有方法都会抛出 NullPointerException。

该类中包含的操作集合的算法的注释通常简要描述了其实现方式。这些描述应被视为实现说明，而非规范的一部分。实现者可以自由替换其他算法，只要遵守规范即可。（例如，sort 方法使用的算法不一定必须是归并排序，但它必须是稳定的排序算法。）

该类中的“破坏性”算法，即那些修改操作对象集合的算法，规定如果集合不支持适当的修改操作（例如 set 方法），将抛出 UnsupportedOperationException。如果调用不会对集合产生任何影响，这些算法可能会抛出此异常，但并非必须抛出。例如，对已经排序的不可修改列表调用 sort 方法，可能会抛出或不抛出 UnsupportedOperationException。

一、算法

二、不可变封装（Unmodifiable Wrappers）

三、同步封装（Synch Wrappers）

对同步数据结构的封装包括：

Collection
Set
SortedSet
NavigableSet
List
RandomAccessList
Map
NavigableMap
SortedMap

这里先以 Map 举个例子。

1、同步 Map

Collections 类中提供了 synchronizedMap(Map<K,V> m) 方法，用来返回一个由指定的 Map 为基础的线程安全的 Map。为了保证串行访问，所有对原始 Map 的访问都必须通过该方法返回的 Map 来完成。

如果方法指定的 Map 是可序列化的，那么方法返回的 Map 也将是可序列化的。

下面是该方法的源码：

1
2
3

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {  
    return new SynchronizedMap<>(m);  
}

如下是 SynchronizedMap 的源码：

private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
    
    @java.io.Serial
    private static final long serialVersionUID = 1978198479659022715L;

    // Conditionally serializable
    @SuppressWarnings("serial")
    private final Map<K,V> m;
    
    // Conditionally serializable
    @SuppressWarnings("serial")
    // Object on which to synchronize
    final Object mutex;

    SynchronizedMap(Map<K,V> m) {
        this.m = Objects.requireNonNull(m);
        mutex = this;
    }

    SynchronizedMap(Map<K,V> m, Object mutex) {
        this.m = m;
        this.mutex = mutex;
    }

    public int size() {
        synchronized (mutex) {return m.size();}
    }
    public boolean isEmpty() {
        synchronized (mutex) {return m.isEmpty();}
    }
    public boolean containsKey(Object key) {
        synchronized (mutex) {return m.containsKey(key);}
    }
    public boolean containsValue(Object value) {
        synchronized (mutex) {return m.containsValue(value);}
    }
    public V get(Object key) {
        synchronized (mutex) {return m.get(key);}
    }

    public V put(K key, V value) {
        synchronized (mutex) {return m.put(key, value);}
    }
    public V remove(Object key) {
        synchronized (mutex) {return m.remove(key);}
    }
    public void putAll(Map<? extends K, ? extends V> map) {
        synchronized (mutex) {m.putAll(map);}
    }
    public void clear() {
        synchronized (mutex) {m.clear();}
    }

    private transient Set<K> keySet;
    private transient Set<Map.Entry<K,V>> entrySet;
    private transient Collection<V> values;

    public Set<K> keySet() {
        synchronized (mutex) {
            if (keySet==null)
                keySet = new SynchronizedSet<>(m.keySet(), mutex);
            return keySet;
        }
    }

    public Set<Map.Entry<K,V>> entrySet() {
        synchronized (mutex) {
            if (entrySet==null)
                entrySet = new SynchronizedSet<>(m.entrySet(), mutex);
            return entrySet;
        }
    }

    public Collection<V> values() {
        synchronized (mutex) {
            if (values==null)
                values = new SynchronizedCollection<>(m.values(), mutex);
            return values;
        }
    }

    public boolean equals(Object o) {
        if (this == o)
            return true;
        synchronized (mutex) {return m.equals(o);}
    }
    public int hashCode() {
        synchronized (mutex) {return m.hashCode();}
    }
    public String toString() {
        synchronized (mutex) {return m.toString();}
    }

    // Override default methods in Map
    @Override
    public V getOrDefault(Object k, V defaultValue) {
        synchronized (mutex) {return m.getOrDefault(k, defaultValue);}
    }
    @Override
    public void forEach(BiConsumer<? super K, ? super V> action) {
        synchronized (mutex) {m.forEach(action);}
    }
    @Override
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        synchronized (mutex) {m.replaceAll(function);}
    }
    @Override
    public V putIfAbsent(K key, V value) {
        synchronized (mutex) {return m.putIfAbsent(key, value);}
    }
    @Override
    public boolean remove(Object key, Object value) {
        synchronized (mutex) {return m.remove(key, value);}
    }
    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        synchronized (mutex) {return m.replace(key, oldValue, newValue);}
    }
    @Override
    public V replace(K key, V value) {
        synchronized (mutex) {return m.replace(key, value);}
    }
    @Override
    public V computeIfAbsent(K key,
            Function<? super K, ? extends V> mappingFunction) {
        synchronized (mutex) {return m.computeIfAbsent(key, mappingFunction);}
    }
    @Override
    public V computeIfPresent(K key,
            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        synchronized (mutex) {return m.computeIfPresent(key, remappingFunction);}
    }
    @Override
    public V compute(K key,
            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        synchronized (mutex) {return m.compute(key, remappingFunction);}
    }
    @Override
    public V merge(K key, V value,
            BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        synchronized (mutex) {return m.merge(key, value, remappingFunction);}
    }

    @java.io.Serial
    private void writeObject(ObjectOutputStream s) throws IOException {
        synchronized (mutex) {s.defaultWriteObject();}
    }
}

SynchronizedMap 类，实现了 Map 接口，实现了所有待实现方法，并且重写了默认方法，将其改为同步方法。

1.1 同步对象的选择

源码中，在同步对象的选择上，有两种方式：

final Object mutex;

SynchronizedMap(Map<K,V> m) {
    this.m = Objects.requireNonNull(m);
    mutex = this;
}

SynchronizedMap(Map<K,V> m, Object mutex) {
    this.m = m;
    this.mutex = mutex;
}

有两个构造方法，第一个构造方法中使用当前对象进行同步；第二个构造方法提供了额外的 mutex 参数，来指定同步对象。

题外话，this 上进行同步的方法和其他对象上进行同步的方法不能同时存在，两个锁的同步是相互独立的，如下示例，f() 方法在 this 上进行同步，而 g() 方法在 syncObject 上进行同步。

class Demo {  
  
    private final Object syncObject = new Object();  
  
    public synchronized void f() {
        // ...
    }  
  
    public void g() {  
        synchronized (syncObject) {  
            // ...
        }  
    }  
}

1.2 需要 coder 手动同步的地方

如果对返回的线程安全的三个集合视图 keySet、entrySet 和 values 进行遍历时，需要手动进行同步，遍历操作包括 Iterator、Spliterator 或 Stream。如果不进行手动同步，将会发生不可预料的后果。手动同步方式如下：

Map map = Collections.synchronizedMap(new HashMap());
// ...
Set set = map.keySet();

// 在 map 上进行同步，而不是 set
synchronized (map) {  
    // 必须在同步块中
    Iterator it = set.iterator(); 
    while (it.hasNext()) {
        foo(it.next());
    }
}

keySet、entrySet 和 values 在 SynchronizedMap 类中都会进行单独的同步处理，使用到的是 SynchronizedCollection，而 SynchronizedCollection 的迭代器是没有进行同步处理的。

private transient Set<K> keySet;  
private transient Set<Map.Entry<K,V>> entrySet;  
private transient Collection<V> values;  
  
public Set<K> keySet() {  
    synchronized (mutex) {  
        if (keySet==null)  
            keySet = new SynchronizedSet<>(m.keySet(), mutex);  
        return keySet;  
    }  
}  
  
public Set<Map.Entry<K,V>> entrySet() {  
    synchronized (mutex) {  
        if (entrySet==null)  
            entrySet = new SynchronizedSet<>(m.entrySet(), mutex);  
        return entrySet;  
    }  
}  
  
public Collection<V> values() {  
    synchronized (mutex) {  
        if (values==null)  
            values = new SynchronizedCollection<>(m.values(), mutex);  
        return values;  
    }  
}

SynchronizedCollection 类

static class SynchronizedCollection<E> implements Collection<E>, Serializable {

    public Iterator<E> iterator() {  
        // Must be manually synched by user!  
        return c.iterator();
    }
}

四、动态类型安全的集合包装器（Dynamically typesafe collection wrappers）

五、空集合（Empty collections）

六、其他方法（Miscellaneous）

1、newSetFromMap

返回一个由指定映射支持的集合。生成的集合显示与支持的映射相同的顺序、并发性和性能特征。实际上，这个工厂方法为任何 Map 实现提供了一个对应的 Set 实现。不需要对已经具有对应 Set 实现的 Map 实现（如 HashMap 或 TreeMap）使用此方法。

通过这种方法返回的集合上的每个方法调用都会在支持的映射或其 keySet 视图上精确地导致一次方法调用，有一个例外：addAll 方法被实现为在支持的映射上一系列的 put 调用。

在调用此方法时，指定的映射必须为空，并且在此方法返回之后不应直接访问该映射。如果映射创建时为空，直接传递给此方法，并且不保留对该映射的引用，则可以确保这些条件，如下代码片段所示：

1	Set<Object> weakHashSet = Collections.newSetFromMap(new WeakHashMap<Object, Boolean>());

newSetFromMap 方法如下所示：

public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {  
    if (!map.isEmpty()) // implicit null check  
        throw new IllegalArgumentException("Map is non-empty");  
    return new SetFromMap<>(map);  
}

SetFromMap 代码如下所示，其中的方法即是对 Map 和 Set 的调用。

private static class SetFromMap<E> extends AbstractSet<E> implements Set<E>, Serializable {  

    @SuppressWarnings("serial") // Conditionally serializable  
    final Map<E, Boolean> m;          // The backing map  
    
    private transient Set<E> s;       // Its keySet  
  
    SetFromMap(Map<E, Boolean> map) {  
        m = map;  
        s = map.keySet();  
    }
    
    public void clear()               {        m.clear(); }  
    public int size()                 { return m.size(); }  
    public boolean isEmpty()          { return m.isEmpty(); }  
    public boolean contains(Object o) { return m.containsKey(o); }  
    public boolean remove(Object o)   { return m.remove(o) != null; }  
    public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }  
    public Iterator<E> iterator()     { return s.iterator(); }  
    public Object[] toArray()         { return s.toArray(); }
    
    // ......
}

使用场景举例：

Java 中没有并发版的 HashSet，但可以通过newSetFromMap 方法基于 ConcurrentHashMap 构建一个并发版本的 HashSet

OB links

OB tags

#Java #未完待续