Java 集合（5）-- Collections 源码解析
发布于: 2020 年 11 月 16 日
一、Collections 接口是做什么的？
用官网文档的介绍：
The polymorphic algorithms described here are pieces of reusable functionality provided by the Java platform. All of them come from the Collections class, and all take the form of static methods whose first argument is the collection on which the operation is to be performed. The great majority of the algorithms provided by the Java platform operate on List instances, but a few of them operate on arbitrary Collection instances.（这里描述的多态算法是 Java 平台提供的可重用功能的一部分。它们都来自 Collections 类，都采用静态方法的形式，其第一个参数是要执行操作的集合。Java 平台提供的绝大多数算法都对列表实例进行操作，但也有少数算法对任意集合实例进行操作。）
从介绍来看，这其实是一个工具类，实现了一些常用的算法，方便我们操作集合，如果没有这个类，也是可以的，就是自己写比较麻烦😂。但是呢，有了这个类，平时写代码我们可以直接调用（前提是了解里面怎么实现的，实现了什么功能），毕竟不是所有的轮子都要重复造。但是，不是有轮子了，我们就可以不去深究里面到底是啥，重要的不是造轮子，而是，我们必须有能够造轮子的能力。
二、Collections 源码之大类方法
1.提供不可变集合
一般是通过一个方法直接获取不可变的集合，里面包含了不可变的Collection，Set，SortedSet，NavigableSet，List，SortedMap，NavigableMap。
// 获取不可变的Collection public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) { return new UnmodifiableCollection<>(c); } // 获取不可变的Set public static <T> Set<T> unmodifiableSet(Set<? extends T> s) { return new UnmodifiableSet<>(s); } // 获取不可变的SortedSet public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) { return new UnmodifiableSortedSet<>(s); } // 获取不可变的NavigableSet public static <T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> s) { return new UnmodifiableNavigableSet<>(s); } // 获取不可变的List public static <T> List<T> unmodifiableList(List<? extends T> list) { return (list instanceof RandomAccess ? new UnmodifiableRandomAccessList<>(list) : new UnmodifiableList<>(list)); } // 获取不可变的SortedMap public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) { return new UnmodifiableSortedMap<>(m); } // 获取不可变的NavigableMap public static <K,V> NavigableMap<K,V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> m) { return new UnmodifiableNavigableMap<>(m); }复制代码
但是这些不可变的集合到底是什么呢？怎么使用呢？
我们来看一个最普遍的UnmodifiableCollection类的源码：
// 实现了Collection和序列化接口 static class UnmodifiableCollection<E> implements Collection<E>, Serializable { // 定义序列化的uid private static final long serialVersionUID = 1820017752578914078L; // 定义数据 final Collection<? extends E> c;
UnmodifiableCollection(Collection<? extends E> c) { if (c==null) throw new NullPointerException(); this.c = c; } // 获取大小 public int size() {return c.size();} // 是否为空 public boolean isEmpty() {return c.isEmpty();} // 是否包含 public boolean contains(Object o) {return c.contains(o);} // 转成数组 public Object[] toArray() {return c.toArray();} // 转成特定类型数组 public <T> T[] toArray(T[] a) {return c.toArray(a);} // toString方法 public String toString() {return c.toString();} // 获取迭代器 public Iterator<E> iterator() { // 用内部类方式实现 return new Iterator<E>() { // 迭代器其实是c的迭代器 private final Iterator<? extends E> i = c.iterator(); // 是否有下一个元素 public boolean hasNext() {return i.hasNext();} // 获取下一个 public E next() {return i.next();} // 移除元素 public void remove() { throw new UnsupportedOperationException(); } // 遍历剩下的元素 @Override public void forEachRemaining(Consumer<? super E> action) { // Use backing collection version i.forEachRemaining(action); } }; } // 增加操作抛异常 public boolean add(E e) { throw new UnsupportedOperationException(); } //删除操作抛异常 public boolean remove(Object o) { throw new UnsupportedOperationException(); } // 是否包含所有 public boolean containsAll(Collection<?> coll) { return c.containsAll(coll); } // 批量添加操作抛异常 public boolean addAll(Collection<? extends E> coll) { throw new UnsupportedOperationException(); } // 批量删除抛异常 public boolean removeAll(Collection<?> coll) { throw new UnsupportedOperationException(); } // 取交集抛异常 public boolean retainAll(Collection<?> coll) { throw new UnsupportedOperationException(); } // 清空数据抛异常 public void clear() { throw new UnsupportedOperationException(); }
// Override default methods in Collection @Override //遍历元素 public void forEach(Consumer<? super E> action) { c.forEach(action); } // 按照条件移除元素抛异常 @Override public boolean removeIf(Predicate<? super E> filter) { throw new UnsupportedOperationException(); } // 获取可分割迭代器 @SuppressWarnings("unchecked") @Override public Spliterator<E> spliterator() { return (Spliterator<E>)c.spliterator(); } // 获取数据流 @SuppressWarnings("unchecked") @Override public Stream<E> stream() { return (Stream<E>)c.stream(); } // 获取并行流 @SuppressWarnings("unchecked") @Override public Stream<E> parallelStream() { return (Stream<E>)c.parallelStream(); } }复制代码
从上面的代码可以看出其实所谓不可变的集合，就是用一个包装类，持有对实际的集合的引用，只能执行查询操作，其他操作都会抛出异常UnsupportedOperationException。我们来看其他的，随便挑一个UnmodifiableMap:
// 实现map接口和序列化接口 private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable { // 序列号 private static final long serialVersionUID = -1034234728574286014L; // 持有的引用 private final Map<? extends K, ? extends V> m; // 初始化函数 UnmodifiableMap(Map<? extends K, ? extends V> m) { if (m==null) throw new NullPointerException(); this.m = m; } // 查询大小 public int size() {return m.size();} // 是否为空 public boolean isEmpty() {return m.isEmpty();} // 是否包含键 public boolean containsKey(Object key) {return m.containsKey(key);} // 是否包含值 public boolean containsValue(Object val) {return m.containsValue(val);} // 通过值获取 public V get(Object key) {return m.get(key);} // 添加（抛异常） public V put(K key, V value) { throw new UnsupportedOperationException(); } // 删除元素（抛异常） public V remove(Object key) { throw new UnsupportedOperationException(); } // 批量增加（抛异常） public void putAll(Map<? extends K, ? extends V> m) { throw new UnsupportedOperationException(); } // 清空元素（抛异常） public void clear() { throw new UnsupportedOperationException(); } // set的集合 private transient Set<K> keySet; // ebtry的集合 private transient Set<Map.Entry<K,V>> entrySet; // value的集合 private transient Collection<V> values; // 获取key的集合 public Set<K> keySet() { if (keySet==null) // 如果不为空，把keyset也变成一个不可变的集合之后再返回 keySet = unmodifiableSet(m.keySet()); return keySet; }
public Set<Map.Entry<K,V>> entrySet() { if (entrySet==null) // 如果不为空，把entryset也变成一个不可变的集合之后再返回 entrySet = new UnmodifiableEntrySet<>(m.entrySet()); return entrySet; }
public Collection<V> values() { if (values==null) // // 如果不为空，把value也变成一个不可变的集合之后再返回 values = unmodifiableCollection(m.values()); return values; } // 对象的方法判断是否相等，引用相等也是判断为相等 public boolean equals(Object o) {return o == this || m.equals(o);} // 计算hash public int hashCode() {return m.hashCode();} // toString法法 public String toString() {return m.toString();}
// 重写方法，通过key获取vaule，没有则返回默认值 @Override @SuppressWarnings("unchecked") public V getOrDefault(Object k, V defaultValue) { // Safe cast as we don't change the value return ((Map<K, V>)m).getOrDefault(k, defaultValue); }
// 遍历执行action（动作参数化） @Override public void forEach(BiConsumer<? super K, ? super V> action) { m.forEach(action); }
// 替换所有，抛异常 @Override public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { throw new UnsupportedOperationException(); } // 如果不存在则放进去，抛异常 @Override public V putIfAbsent(K key, V value) { throw new UnsupportedOperationException(); }
//删除操作，抛异常 @Override public boolean remove(Object key, Object value) { throw new UnsupportedOperationException(); } //替换操作，抛异常 @Override public boolean replace(K key, V oldValue, V newValue) { throw new UnsupportedOperationException(); } // 替换操作抛异常 @Override public V replace(K key, V value) { throw new UnsupportedOperationException(); } // 抛异常 @Override public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { throw new UnsupportedOperationException(); } // 抛异常 @Override public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { throw new UnsupportedOperationException(); } // 抛异常 @Override public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { throw new UnsupportedOperationException(); } // 抛异常 @Override public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) { throw new UnsupportedOperationException(); }
/** * We need this class in addition to UnmodifiableSet as * Map.Entries themselves permit modification of the backing Map * via their setValue operation. This class is subtle: there are * many possible attacks that must be thwarted. * * @serial include */ // 将map内部的Entry也用一个不可变的类存起来（实际上也是引用） static class UnmodifiableEntrySet<K,V> extends UnmodifiableSet<Map.Entry<K,V>> { private static final long serialVersionUID = 7854390611657943733L;
@SuppressWarnings({"unchecked", "rawtypes"}) UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) { // Need to cast to raw in order to work around a limitation in the type system super((Set)s); } // 处理entry的元素 static <K, V> Consumer<Map.Entry<K, V>> entryConsumer(Consumer<? super Entry<K, V>> action) { return e -> action.accept(new UnmodifiableEntry<>(e)); } // 遍历 public void forEach(Consumer<? super Entry<K, V>> action) { Objects.requireNonNull(action); c.forEach(entryConsumer(action)); } // 不可变entryset的可分割迭代器（下面方法和Spliterator的差不多，没有什么好说） static final class UnmodifiableEntrySetSpliterator<K, V> implements Spliterator<Entry<K,V>> { final Spliterator<Map.Entry<K, V>> s;
UnmodifiableEntrySetSpliterator(Spliterator<Entry<K, V>> s) { this.s = s; }
@Override public boolean tryAdvance(Consumer<? super Entry<K, V>> action) { Objects.requireNonNull(action); return s.tryAdvance(entryConsumer(action)); }
@Override public void forEachRemaining(Consumer<? super Entry<K, V>> action) { Objects.requireNonNull(action); s.forEachRemaining(entryConsumer(action)); }
@Override public Spliterator<Entry<K, V>> trySplit() { Spliterator<Entry<K, V>> split = s.trySplit(); return split == null ? null : new UnmodifiableEntrySetSpliterator<>(split); }
@Override public long estimateSize() { return s.estimateSize(); }
@Override public long getExactSizeIfKnown() { return s.getExactSizeIfKnown(); }
@Override public int characteristics() { return s.characteristics(); }
@Override public boolean hasCharacteristics(int characteristics) { return s.hasCharacteristics(characteristics); }
@Override public Comparator<? super Entry<K, V>> getComparator() { return s.getComparator(); } }
@SuppressWarnings("unchecked") public Spliterator<Entry<K,V>> spliterator() { return new UnmodifiableEntrySetSpliterator<>( (Spliterator<Map.Entry<K, V>>) c.spliterator()); }
@Override public Stream<Entry<K,V>> stream() { return StreamSupport.stream(spliterator(), false); }
@Override public Stream<Entry<K,V>> parallelStream() { return StreamSupport.stream(spliterator(), true); }
public Iterator<Map.Entry<K,V>> iterator() { return new Iterator<Map.Entry<K,V>>() { private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
public boolean hasNext() { return i.hasNext(); } public Map.Entry<K,V> next() { return new UnmodifiableEntry<>(i.next()); } public void remove() { throw new UnsupportedOperationException(); } }; }
@SuppressWarnings("unchecked") public Object[] toArray() { Object[] a = c.toArray(); for (int i=0; i<a.length; i++) a[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)a[i]); return a; }
@SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { // We don't pass a to c.toArray, to avoid window of // vulnerability wherein an unscrupulous multithreaded client // could get his hands on raw (unwrapped) Entries from c. Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
for (int i=0; i<arr.length; i++) arr[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)arr[i]);
if (arr.length > a.length) return (T[])arr;
System.arraycopy(arr, 0, a, 0, arr.length); if (a.length > arr.length) a[arr.length] = null; return a; }
/** * This method is overridden to protect the backing set against * an object with a nefarious equals function that senses * that the equality-candidate is Map.Entry and calls its * setValue method. */ public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; return c.contains( new UnmodifiableEntry<>((Map.Entry<?,?>) o)); }
/** * The next two methods are overridden to protect against * an unscrupulous List whose contains(Object o) method senses * when o is a Map.Entry, and calls o.setValue. */ public boolean containsAll(Collection<?> coll) { for (Object e : coll) { if (!contains(e)) // Invokes safe contains() above return false; } return true; } public boolean equals(Object o) { if (o == this) return true;
if (!(o instanceof Set)) return false; Set<?> s = (Set<?>) o; if (s.size() != c.size()) return false; return containsAll(s); // Invokes safe containsAll() above }
/** * This "wrapper class" serves two purposes: it prevents * the client from modifying the backing Map, by short-circuiting * the setValue method, and it protects the backing Map against * an ill-behaved Map.Entry that attempts to modify another * Map Entry when asked to perform an equality check. */ private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> { private Map.Entry<? extends K, ? extends V> e;
UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = Objects.requireNonNull(e);}
public K getKey() {return e.getKey();} public V getValue() {return e.getValue();} public V setValue(V value) { throw new UnsupportedOperationException(); } public int hashCode() {return e.hashCode();} public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> t = (Map.Entry<?,?>)o; return eq(e.getKey(), t.getKey()) && eq(e.getValue(), t.getValue()); } public String toString() {return e.toString();} } } }复制代码
UnmodifiableMap稍微复杂一点，就是里面分成了entry<key,value>,key,value三个维度，UnmodifiableEntrySet<K,V>继承了UnmodifiableEntry<K,V>而UnmodifiableEntry<K,V>实现了Map.Entry<K,V>，事实上也是持有对集合的引用，把修改操作全部禁掉，一旦调用就会抛出异常。
上面的不可变集合提供方法直接获取，如下图：
2、提供同步的集合
看下面的图片，我们可以看到这个工具类其实提供了很多同步的集合类，但是都是基于 Synchronize 来实现的，开销相对比较大，有点点暴力了。源头就是SynchronizedCollection,实现了Collection接口。
我们来看源码,明显可以发现，里面处理集合的引用外，还有一个对象，mutex，这就是锁的关键了，也就是同步的对象，可以看到下面几乎所有的方法都被加上了Synchronize同步，这样子确实保持了线程安全，但是这样有点影响效率，如果不那么考虑效率的话，也可以使用这个。
static class SynchronizedCollection<E> implements Collection<E>, Serializable { private static final long serialVersionUID = 3053995032091335093L;
final Collection<E> c; // Backing Collection final Object mutex; // Object on which to synchronize
SynchronizedCollection(Collection<E> c) { this.c = Objects.requireNonNull(c); mutex = this; }
SynchronizedCollection(Collection<E> c, Object mutex) { this.c = Objects.requireNonNull(c); this.mutex = Objects.requireNonNull(mutex); }
public int size() { synchronized (mutex) {return c.size();} } public boolean isEmpty() { synchronized (mutex) {return c.isEmpty();} } public boolean contains(Object o) { synchronized (mutex) {return c.contains(o);} } public Object[] toArray() { synchronized (mutex) {return c.toArray();} } public <T> T[] toArray(T[] a) { synchronized (mutex) {return c.toArray(a);} }
public Iterator<E> iterator() { return c.iterator(); // Must be manually synched by user! }
public boolean add(E e) { synchronized (mutex) {return c.add(e);} } public boolean remove(Object o) { synchronized (mutex) {return c.remove(o);} }
public boolean containsAll(Collection<?> coll) { synchronized (mutex) {return c.containsAll(coll);} } public boolean addAll(Collection<? extends E> coll) { synchronized (mutex) {return c.addAll(coll);} } public boolean removeAll(Collection<?> coll) { synchronized (mutex) {return c.removeAll(coll);} } public boolean retainAll(Collection<?> coll) { synchronized (mutex) {return c.retainAll(coll);} } public void clear() { synchronized (mutex) {c.clear();} } public String toString() { synchronized (mutex) {return c.toString();} } // Override default methods in Collection @Override public void forEach(Consumer<? super E> consumer) { synchronized (mutex) {c.forEach(consumer);} } @Override public boolean removeIf(Predicate<? super E> filter) { synchronized (mutex) {return c.removeIf(filter);} } @Override public Spliterator<E> spliterator() { return c.spliterator(); // Must be manually synched by user! } @Override public Stream<E> stream() { return c.stream(); // Must be manually synched by user! } @Override public Stream<E> parallelStream() { return c.parallelStream(); // Must be manually synched by user! } private void writeObject(ObjectOutputStream s) throws IOException { synchronized (mutex) {s.defaultWriteObject();} } }复制代码
值得注意的是，还有几个方法没有被加上锁，那就是所有获取流和迭代器的方法都没有，iterator(),spliterator,stream,parallelStream,都有一句话注释：Must be manually synched by user!,就是叫我们长点心，如果迭代或者流计算设计涉及到并发操作，可能会有问题，要使用者自己考虑。
至此，以上的同步内部类都有方法与之对应，也就是传进来集合就行了，会给我们返回一个同步类，可以直接获取，这也太方便了吧🙈🙈🙈没听过鲁迅说便宜的东西往往最贵么（鲁迅说没有说过）,也就是效率自己权衡好就行啦👀~
3、类型检查
这个包装类还提供了很多关于类型检查的方法：
我们来看看是干啥的，挑一个checkedCollection()看看：
public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type) { return new CheckedCollection<>(c, type); }复制代码
首先这个方法是返回了一个CheckedCollection，我猜这个类也是封装了Collection,跟进去源码看看：
static class CheckedCollection<E> implements Collection<E>, Serializable { private static final long serialVersionUID = 1578914078182001775L;
final Collection<E> c;//持有引用 final Class<E> type;//持有传进来的类型
// 检查类型的函数 @SuppressWarnings("unchecked") E typeCheck(Object o) { if (o != null && !type.isInstance(o)) throw new ClassCastException(badElementMsg(o)); return (E) o; } //类型不对则打印错误信息 private String badElementMsg(Object o) { return "Attempt to insert " + o.getClass() + " element into collection with element type " + type; }
CheckedCollection(Collection<E> c, Class<E> type) { this.c = Objects.requireNonNull(c, "c"); this.type = Objects.requireNonNull(type, "type"); }
public int size() { return c.size(); } public boolean isEmpty() { return c.isEmpty(); } public boolean contains(Object o) { return c.contains(o); } public Object[] toArray() { return c.toArray(); } public <T> T[] toArray(T[] a) { return c.toArray(a); } public String toString() { return c.toString(); } public boolean remove(Object o) { return c.remove(o); } public void clear() { c.clear(); }
public boolean containsAll(Collection<?> coll) { return c.containsAll(coll); } public boolean removeAll(Collection<?> coll) { return c.removeAll(coll); } public boolean retainAll(Collection<?> coll) { return c.retainAll(coll); }
public Iterator<E> iterator() { // JDK-6363904 - unwrapped iterator could be typecast to // ListIterator with unsafe set() final Iterator<E> it = c.iterator(); return new Iterator<E>() { public boolean hasNext() { return it.hasNext(); } public E next() { return it.next(); } public void remove() { it.remove(); }}; } // 添加的时候执行类型检查 public boolean add(E e) { return c.add(typeCheck(e)); }
private E[] zeroLengthElementArray; // Lazily initialized
private E[] zeroLengthElementArray() { return zeroLengthElementArray != null ? zeroLengthElementArray : (zeroLengthElementArray = zeroLengthArray(type)); } // copy的时候检查每一个元素 @SuppressWarnings("unchecked") Collection<E> checkedCopyOf(Collection<? extends E> coll) { Object[] a; try { E[] z = zeroLengthElementArray(); a = coll.toArray(z); // Defend against coll violating the toArray contract if (a.getClass() != z.getClass()) a = Arrays.copyOf(a, a.length, z.getClass()); } catch (ArrayStoreException ignore) { // To get better and consistent diagnostics, // we call typeCheck explicitly on each element. // We call clone() to defend against coll retaining a // reference to the returned array and storing a bad // element into it after it has been type checked. a = coll.toArray().clone(); for (Object o : a) typeCheck(o); } // A slight abuse of the type system, but safe here. return (Collection<E>) Arrays.asList(a); } // 批量添加的时候执行拷贝检查机制 public boolean addAll(Collection<? extends E> coll) { // Doing things this way insulates us from concurrent changes // in the contents of coll and provides all-or-nothing // semantics (which we wouldn't get if we type-checked each // element as we added it) return c.addAll(checkedCopyOf(coll)); }
// Override default methods in Collection @Override public void forEach(Consumer<? super E> action) {c.forEach(action);} @Override public boolean removeIf(Predicate<? super E> filter) { return c.removeIf(filter); } @Override public Spliterator<E> spliterator() {return c.spliterator();} @Override public Stream<E> stream() {return c.stream();} @Override public Stream<E> parallelStream() {return c.parallelStream();} }复制代码
上面的源码可以看出，这些封装类没有什么特殊的地方，只是包装了一层，执行添加的时候，检查类型，如果不符合则抛出异常。
4.提供空集合或者迭代器
这个类还提供了一些方法可以获取到空集合，会生成指定类型的空 List, Set, Map，而且是不可变的，如进行 add() 操作会报 java.lang.UnsupportedOperationException。
我们来看EmptyIterator的源码,里面有可以 final 的对象EMPTY_ITERATOR，里面的hashNext()方法直接返回 false，remove(),next()方法直接不合法。
private static class EmptyIterator<E> implements Iterator<E> { static final EmptyIterator<Object> EMPTY_ITERATOR = new EmptyIterator<>();
public boolean hasNext() { return false; } public E next() { throw new NoSuchElementException(); } public void remove() { throw new IllegalStateException(); } @Override public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); } }复制代码
为啥要做这样的集合呢？看了一下其他的空集合，都是空的。🐶我想了很久🤔🤔
我们写测试用例的时候可能需要一个空的集合，有可能用到，还有就是它是空集合，但是它不为 null，如果遍历 null 就会抛空指针，这样的话还是用一个空集合好了。还是蛮有道理的，而且当有这样的需求的时候，使用这样初始化大小为 0 的集合省空间啊，还是蛮方便的💯
然后就是Set，List，Map都有对应的对象可以直接Collections.EMPTY_SET即可。
5.提供 singleton 的集合或者迭代器
从下面的图片啊，我们可以看到这个类还提供了获取 singleton 的 List,Set,Map,还有 Iterator,Spliterator。
这些是啥，有啥用？🤔🤔
先看看singletonIterator源码：
return new Iterator<E>() { private boolean hasNext = true; public boolean hasNext() { return hasNext; } // hashNext只能使用一次就置为false，第二次next方法调用会抛异常 public E next() { if (hasNext) { hasNext = false; return e; } throw new NoSuchElementException(); } // 不可移除 public void remove() { throw new UnsupportedOperationException(); } //只能遍历一个元素 @Override public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); if (hasNext) { action.accept(e); hasNext = false; } } }; }复制代码
SingletonList 的源码：
private static class SingletonList<E> extends AbstractList<E> implements RandomAccess, Serializable {
private static final long serialVersionUID = 3093736618740652951L;
private final E element;
SingletonList(E obj) {element = obj;} // 获取迭代器，只能遍历一次的迭代器 public Iterator<E> iterator() { return singletonIterator(element); }
public int size() {return 1;}
public boolean contains(Object obj) {return eq(obj, element);} //只允许取一个元素 public E get(int index) { if (index != 0) throw new IndexOutOfBoundsException("Index: "+index+", Size: 1"); return element; }
// Override default methods for Collection @Override public void forEach(Consumer<? super E> action) { action.accept(element); } @Override public boolean removeIf(Predicate<? super E> filter) { throw new UnsupportedOperationException(); } @Override public void replaceAll(UnaryOperator<E> operator) { throw new UnsupportedOperationException(); } @Override public void sort(Comparator<? super E> c) { } @Override public Spliterator<E> spliterator() { return singletonSpliterator(element); } }复制代码
如果我们只有一个元素并且永远只有一个元素，那么我们可以考虑使用这些类，迭代器因为这些类都可以通过迭代器进行遍历，所以迭代器也限制了只能遍历一个元素。在创建的时候，就将唯一的元素传进去，不允许改变，也不允许删除。
三、从源码看其他常用方法
1. Sort（排序）
public static <T extends Comparable<? super T>> void sort(List<T> list)，元素需要实现Comparable接口，按照比较器进行排序。内部调用的是 List 的 sort()方法,先转成数组，再对数组进行排序，排好序之后再 set 修改值。
一共有两种排序方法，第一种：
public static <T extends Comparable<? super T>> void sort(List<T> list) { list.sort(null); }复制代码
第二种：
public static <T> void sort(List<T> list, Comparator<? super T> c) { list.sort(c); }复制代码
两种看起来的区别在于有没有比较器Comparator，内部都是调用了List的sort()方法，这个方法的源码如下，内部其实是调用了数组的排序方法。
default void sort(Comparator<? super E> c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); ListIterator<E> i = this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } }````使用方式，如果没有传入Comparator，那么所排序的类需要继承Comparable接口并重写compareTo方法，注意：String，Integer这些类已经实现了Comparable接口，所以不需要传入比较器也是可以默认排序的。
## 2. binarySearch（二分搜索）二分搜索同样有两个：```java int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); } public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) { if (c==null) return binarySearch((List<? extends Comparable<? super T>>) list, key);
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) //可以快速查找的，直接用索引二分 return Collections.indexedBinarySearch(list, key, c); else //迭代器二分 return Collections.iteratorBinarySearch(list, key, c); } 复制代码
一个需要 List 里面的对象继承Comparable，实现里面的方法，另一个则是不需要，但是需要传入Comparator，这其实都是一个意思，也就是你得告诉我怎么比较啊是不是😬😬😬
我们可以看到里面还是有两个分支，一个是使用索引二分，一个是迭代器二分，这是啥？这不得不说RandomAccess,ArrayList实现了一个叫做 RandomAccess 的接口，而 LinkedList 是没有的,这个接口的意思是一个标识，谁实现了，谁就（牛逼），开玩笑的，谁实现了，就说明这个接口是支持快速随机访问的，所谓快速随机访问就是底层不是链表，而是数组，数组是可以直接通过下标就能快速查找的嘛，牛逼牛逼~再底层的细节就后面再研究研究了。
3. reverse(反转)
老样子，看源码:
public static void reverse(List<?> list) { int size = list.size(); if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) { for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--) swap(list, i, j); } else { // instead of using a raw type here, it's possible to capture // the wildcard but it will require a call to a supplementary // private method ListIterator fwd = list.listIterator(); ListIterator rev = list.listIterator(size); for (int i=0, mid=list.size()>>1; i<mid; i++) { Object tmp = fwd.next(); fwd.set(rev.previous()); rev.set(tmp); } } }复制代码
REVERSE_THRESHOLD叫反转阈值，看上面的源码实说 list 的大小还有是否是 RandomAccess 会导致使用两种不同的算法进行反转，一种是基于数组索引，一种是基于 Iterator 的思路。
4. Shuffling(混排)
public static void shuffle(List<?> list),将 list 的元素随机打乱，这个方法也有两种参数，一种是只需要 list，一种还需要随机值 Random，但是底层一样，没有随机数的会方法内部生成再进行调用。
public static void shuffle(List<?> list, Random rnd) { int size = list.size(); if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { for (int i=size; i>1; i--) swap(list, i-1, rnd.nextInt(i)); } else { Object arr[] = list.toArray();
// Shuffle array for (int i=size; i>1; i--) swap(arr, i-1, rnd.nextInt(i)); ListIterator it = list.listIterator(); for (int i=0; i<arr.length; i++) { it.next(); it.set(arr[i]); } } }复制代码
里面同样是分成根据索引混排和迭代器混排，老套路了，混排的关键就是根据随机数，将顺序打乱，说是打乱，其实就是两个两个随机互换啦。
5. 交换（swap）
public static void swap(List<?> list, int i, int j) 交换两个索引的元素
上面的混排接口，打乱顺序调用的就是交换接口，这个就是 set 和 get，直接上源码。
public static void swap(List<?> list, int i, int j) { final List l = list; l.set(i, l.set(j, l.get(i))); }复制代码
6. 拷贝（copy）
public static <T> void copy(List<? super T> dest, List<? extends T> src)，copy 出一个内容一致的list。
public static <T> void copy(List<? super T> dest, List<? extends T> src) { int srcSize = src.size(); // 大小得满足条件 if (srcSize > dest.size()) throw new IndexOutOfBoundsException("Source does not fit in dest");
if (srcSize < COPY_THRESHOLD || (src instanceof RandomAccess && dest instanceof RandomAccess)) { //索引copy for (int i=0; i<srcSize; i++) dest.set(i, src.get(i)); } else { //迭代器copy ListIterator<? super T> di=dest.listIterator(); ListIterator<? extends T> si=src.listIterator(); for (int i=0; i<srcSize; i++) { di.next(); di.set(si.next()); } } }复制代码
这里面也是分为两种，一种是迭代器 copy，一种是索引，看来是惯用手法了啊，条件都是src instanceof RandomAccess或者超过某个阈值。
7. 返回最小的元素（min）
所谓大小，根据指定的比较器决定，static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
同样分为有比较器和无比较器，有的话直接使用传进来的参数，没有的话，就会使用对象的。
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) { Iterator<? extends T> i = coll.iterator(); T candidate = i.next(); //挨个遍历一遍，找出最小 while (i.hasNext()) { T next = i.next(); if (next.compareTo(candidate) < 0) candidate = next; } return candidate; }复制代码
8. 返回最大的元素（max）
static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
这个和找最小一个道理，就是比较的时候相反。
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) { Iterator<? extends T> i = coll.iterator(); T candidate = i.next();
while (i.hasNext()) { T next = i.next(); if (next.compareTo(candidate) > 0) candidate = next; } return candidate; }复制代码
9. 旋转（Rotate）
将一个 List 旋转，假如有个序列列 list 是[1,2,3,4]，调用方法 Collections.rotate(list, 1)后，得到 list 就变成[4,1,2,3]，public static void rotate(List<?> list, int distance)
也是分成两种，一种基于索引一种基于迭代器：
public static void rotate(List<?> list, int distance) { if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD) rotate1(list, distance); else rotate2(list, distance); }复制代码
我们来看看基于索引的旋转,首先把非法情况处理，再通过取余数计算出旋转距离，然后两层循环进行旋转，说实话，这代码写得值得我学习。牛啊🐮🐮🐮
private static <T> void rotate1(List<T> list, int distance) { int size = list.size(); if (size == 0) return; distance = distance % size; if (distance < 0) distance += size; if (distance == 0) return;
for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) { T displaced = list.get(cycleStart); int i = cycleStart; do { i += distance; if (i >= size) i -= size; displaced = list.set(i, displaced); nMoved ++; } while (i != cycleStart); } }复制代码
10. 替换所有元素（replaceAll）
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)
这个没啥好说啊，就是替换元素。写代码的人是觉得代码太短了么，根据索引替换和根据迭代器的都写到一个方法，老长了这🙄🙄🙄
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) { boolean result = false; int size = list.size(); if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) { if (oldVal==null) { for (int i=0; i<size; i++) { if (list.get(i)==null) { list.set(i, newVal); result = true; } } } else { for (int i=0; i<size; i++) { if (oldVal.equals(list.get(i))) { list.set(i, newVal); result = true; } } } } else { ListIterator<T> itr=list.listIterator(); if (oldVal==null) { for (int i=0; i<size; i++) { if (itr.next()==null) { itr.set(newVal); result = true; } } } else { for (int i=0; i<size; i++) { if (oldVal.equals(itr.next())) { itr.set(newVal); result = true; } } } } return result; }复制代码
11.填充所有的元素(fill)
public static <T> void fill(List<? super T> list, T obj) { int size = list.size();
if (size < FILL_THRESHOLD || list instanceof RandomAccess) { for (int i=0; i<size; i++) list.set(i, obj); } else { ListIterator<? super T> itr = list.listIterator(); for (int i=0; i<size; i++) { itr.next(); itr.set(obj); } } }复制代码
这个接口主要是将 list 中的元素全部替换成传入的 obj，底层也是分成两种，一个是按照索引来遍历，一种是按照迭代器来遍历。
12.查找子序列的索引位置（indexOfSubList）
参数是两个 list，一个是源 List，一个是目标 list,作用主要是查找到目标 list 在源 list 中的起始位置，需要是连续的，底层用了两层循环，同样分为两种情况来讨论。
public static int indexOfSubList(List<?> source, List<?> target) { int sourceSize = source.size(); int targetSize = target.size(); int maxCandidate = sourceSize - targetSize;
if (sourceSize < INDEXOFSUBLIST_THRESHOLD || (source instanceof RandomAccess&&target instanceof RandomAccess)) { nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) { for (int i=0, j=candidate; i<targetSize; i++, j++) if (!eq(target.get(i), source.get(j))) continue nextCand; // Element mismatch, try next cand return candidate; // All elements of candidate matched target } } else { // Iterator version of above algorithm ListIterator<?> si = source.listIterator(); nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) { ListIterator<?> ti = target.listIterator(); for (int i=0; i<targetSize; i++) { if (!eq(ti.next(), si.next())) { // Back up source iterator to next candidate for (int j=0; j<i; j++) si.previous(); continue nextCand; } } return candidate; } } return -1; // No candidate matched the target }复制代码
13.查找子序列的索引位置（lastIndexOfSubList）
和上面不太一样的地方是，这个是从后面开始查找，其他的差不多一样，只要有一个匹配不满足，则需要改变匹配位置。
public static int lastIndexOfSubList(List<?> source, List<?> target) { int sourceSize = source.size(); int targetSize = target.size(); int maxCandidate = sourceSize - targetSize;
if (sourceSize < INDEXOFSUBLIST_THRESHOLD || source instanceof RandomAccess) { // Index access version nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) { for (int i=0, j=candidate; i<targetSize; i++, j++) if (!eq(target.get(i), source.get(j))) continue nextCand; // Element mismatch, try next cand return candidate; // All elements of candidate matched target } } else { // Iterator version of above algorithm if (maxCandidate < 0) return -1; ListIterator<?> si = source.listIterator(maxCandidate); nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) { ListIterator<?> ti = target.listIterator(); for (int i=0; i<targetSize; i++) { if (!eq(ti.next(), si.next())) { if (candidate != 0) { // Back up source iterator to next candidate for (int j=0; j<=i+1; j++) si.previous(); } continue nextCand; } } return candidate; } } return -1; // No candidate matched the target }复制代码
14.拷贝元素一样的 list（nCopies）
这个方法功能是返回一个大小为 n，元素全是 o 的 list。
public static <T> List<T> nCopies(int n, T o) { if (n < 0) throw new IllegalArgumentException("List length = " + n); return new CopiesList<>(n, o); }复制代码
里面用到了CopiesList，这个主要是继承AbstractList,封装了只有一种元素的大小为 n 的 list。
15.获取反转的比较器(reverseOrder)
public static <T> Comparator<T> reverseOrder() { return (Comparator<T>) ReverseComparator.REVERSE_ORDER; }复制代码
在方法调用返回一个比较器，实现 Comparable 接口的对象的集合的自然顺序相反。
16.返回集合的枚举（enumration）
主要是用来获取一个枚举指定集合
public static <T> Enumeration<T> enumeration(final Collection<T> c) { return new Enumeration<T>() { private final Iterator<T> i = c.iterator();
public boolean hasMoreElements() { return i.hasNext(); }
public T nextElement() { return i.next(); } }; }复制代码
17.返回枚举集合的 list(list)
正好和上面的相反，这个是根据枚举类型集合返回一个 list。
public static <T> ArrayList<T> list(Enumeration<T> e) { ArrayList<T> l = new ArrayList<>(); while (e.hasMoreElements()) l.add(e.nextElement()); return l; }复制代码
18.返回某个元素出现的频率（frequency）
主要是通过 equals 比较，遍历一遍，相等则次数加一。
public static int frequency(Collection<?> c, Object o) { int result = 0; if (o == null) { for (Object e : c) if (e == null) result++; } else { for (Object e : c) if (o.equals(e)) result++; } return result; }复制代码
19.判断是否有相同的元素（disjoint）
主要是比较两个集合中是否有相同的元素，当两个集合中没有相同的元素的时候 返回 true ，当有相同的元素的时候返回 false.
public static boolean disjoint(Collection<?> c1, Collection<?> c2) {
Collection<?> contains = c2; Collection<?> iterate = c1;
if (c1 instanceof Set) { iterate = c2; contains = c1; } else if (!(c2 instanceof Set)) { int c1size = c1.size(); int c2size = c2.size(); if (c1size == 0 || c2size == 0) {
return true; } if (c1size > c2size) { iterate = c2; contains = c1; } } for (Object e : iterate) { if (contains.contains(e)) { return false; } }
return true; }复制代码
20.批量添加（addAll）
支持可变参数，可以实现添加多个元素。
public static <T> boolean addAll(Collection<? super T> c, T... elements) { boolean result = false; for (T element : elements) result |= c.add(element); return result; }复制代码
21.Map 转成 Set(newSetFromMap)
将 Map 转成一个 Set(SetFromMap)，这也是一个封装的 Set,实现没有什么特别的。
public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) { return new SetFromMap<>(map); }复制代码
22.转换成后进先出队列（asLifoQueue）
传参数为双向队列，是先进先出的，转换之后，成为后进先出队列，也就是再调用 add()方法，会插入在队列的最前面。
public static <T> Queue<T> asLifoQueue(Deque<T> deque) { return new AsLIFOQueue<>(deque); }复制代码
四、总结
Collections这个类就是个工具类，主要的方法都是获取线程安全集合，集合类型检查，转换，截取，获取单个对象的集合或者空集合，排序，查找，旋转，混排等等，这些都是我们日常的操作，使用频率比较高，所以都给封装成工具类了。
里面很多地方都根据阈值或者类型来使用不同的索引遍历或者迭代器遍历，里面比较偏心List，大多都是List相关的呢...
看看源码也挺好的，有时候知道的越多，感觉自己不知道的越多。不知道自己不知道，才是最大的阻碍，继续加油💪💪💪
PS:如有错误，劳烦指出，感谢~
此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~
技术之路不在一时，山高水长，纵使缓慢，驰而不息。
公众号：秦怀杂货店
划线
评论
复制
发布于: 2020 年 11 月 16 日阅读数: 74
版权声明: 本文为 InfoQ 作者【秦怀杂货店】的原创文章。
原文链接:【http://xie.infoq.cn/article/be7ccdc2dfd366be24e1d0170】。文章转载请联系作者。
秦怀杂货店
关注
纵使缓慢，驰而不息。 2018.05.17 加入
慢慢走，比较快。公众号：秦怀杂货店
评论