简介

  • 上一篇我们学习了 Arrays的工具类，同样的，Collections 也是JDK提供的工具类。

  • 因为Collections是JDK官方提供的操作集合的工具类，所以很多部分都是重载方法，本篇只举例说明，因为使用的方法是一致的。本篇暂时不学习其内部过多的内部类

    1. public class Collections {
    3.   private Collections() {
    4.   }
    6.   private static final int BINARYSEARCH_THRESHOLD   = 5000;
    7.   private static final int REVERSE_THRESHOLD        =   18;
    8.   private static final int SHUFFLE_THRESHOLD        =    5;
    9.   private static final int FILL_THRESHOLD           =   25;
    10.   private static final int ROTATE_THRESHOLD         =  100;
    11.   private static final int COPY_THRESHOLD           =   10;
    12.   private static final int REPLACEALL_THRESHOLD     =   11;
    13.   private static final int INDEXOFSUBLIST_THRESHOLD =   35;
    15.   // 排序
    16.   public static <T extends Comparable<? super T>> void sort(List<T> list) {
    17.       list.sort(null);
    18.   }
    20.   // 二分查找
    21.   public static <T>
    22.       int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    23.       if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
    24.           return Collections.indexedBinarySearch(list, key);
    25.       else
    26.           return Collections.iteratorBinarySearch(list, key);
    27.   }
    29.   // 二分查找辅助类
    30.   private static <T>
    31.       int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
    32.       int low = 0;
    33.       int high = list.size()-1;
    35.       while (low <= high) {
    36.           int mid = (low + high) >>> 1;
    37.           Comparable<? super T> midVal = list.get(mid);
    38.           int cmp = midVal.compareTo(key);
    40.           if (cmp < 0)
    41.               low = mid + 1;
    42.           else if (cmp > 0)
    43.               high = mid - 1;
    44.           else
    45.               return mid; // key found
    46.       }
    47.       return -(low + 1);  // key not found
    48.   }
    50.   private static <T>
    51.       int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
    52.   {
    53.       int low = 0;
    54.       int high = list.size()-1;
    55.       ListIterator<? extends Comparable<? super T>> i = list.listIterator();
    57.       while (low <= high) {
    58.           int mid = (low + high) >>> 1;
    59.           Comparable<? super T> midVal = get(i, mid);
    60.           int cmp = midVal.compareTo(key);
    62.           if (cmp < 0)
    63.               low = mid + 1;
    64.           else if (cmp > 0)
    65.               high = mid - 1;
    66.           else
    67.               return mid; // key found
    68.       }
    69.       return -(low + 1);  // key not found
    70.   }
    72.   // 获取第i个元素
    73.   private static <T> T get(ListIterator<? extends T> i, int index) {
    74.       T obj = null;
    75.       int pos = i.nextIndex();
    76.       if (pos <= index) {
    77.           do {
    78.               obj = i.next();
    79.           } while (pos++ < index);
    80.       } else {
    81.           do {
    82.               obj = i.previous();
    83.           } while (--pos > index);
    84.       }
    85.       return obj;
    86.   }
    88.   // 反转指定列表中元素的顺序。
    89.   // 此方法以线性时间运行。
    90.   public static void reverse(List<?> list) {
    91.       int size = list.size();
    92.       if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
    93.           for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
    94.               swap(list, i, j);
    95.       } else {
    96.           // instead of using a raw type here, it's possible to capture
    97.           // the wildcard but it will require a call to a supplementary
    98.           // private method
    99.           ListIterator fwd = list.listIterator();
    100.           ListIterator rev = list.listIterator(size);
    101.           for (int i=0, mid=list.size()>>1; i<mid; i++) {
    102.               Object tmp = fwd.next();
    103.               fwd.set(rev.previous());
    104.               rev.set(tmp);
    105.           }
    106.       }
    107.   }
    109.   // 随机的置换使用随机的默认源指定列表 随机置换列表
    110.   public static void shuffle(List<?> list) {
    111.       Random rnd = r;
    112.       if (rnd == null)
    113.           r = rnd = new Random(); // harmless race.
    114.       shuffle(list, rnd);
    115.   }
    117.   // 随机对象
    118.   private static Random r;
    120.   // 元素互换操作
    121.   public static void swap(List<?> list, int i, int j) {
    122.       final List l = list;
    123.       l.set(i, l.set(j, l.get(i)));
    124.   }
    125.   private static void swap(Object[] arr, int i, int j) {
    126.       Object tmp = arr[i];
    127.       arr[i] = arr[j];
    128.       arr[j] = tmp;
    129.   }
    131.   // 替换所有指定列表与指定元素的元素。
    132.   public static <T> void fill(List<? super T> list, T obj) {
    133.       int size = list.size();
    135.       if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
    136.           for (int i=0; i<size; i++)
    137.               list.set(i, obj);
    138.       } else {
    139.           ListIterator<? super T> itr = list.listIterator();
    140.           for (int i=0; i<size; i++) {
    141.               itr.next();
    142.               itr.set(obj);
    143.           }
    144.       }
    145.   }
    147.   // 将所有从一个列表中的元素到另一个的
    148.   public static <T> void copy(List<? super T> dest, List<? extends T> src) {
    149.       int srcSize = src.size();
    150.       if (srcSize > dest.size())
    151.           throw new IndexOutOfBoundsException("Source does not fit in dest");
    153.       if (srcSize < COPY_THRESHOLD ||
    154.           (src instanceof RandomAccess && dest instanceof RandomAccess)) {
    155.           for (int i=0; i<srcSize; i++)
    156.               dest.set(i, src.get(i));
    157.       } else {
    158.           ListIterator<? super T> di=dest.listIterator();
    159.           ListIterator<? extends T> si=src.listIterator();
    160.           for (int i=0; i<srcSize; i++) {
    161.               di.next();
    162.               di.set(si.next());
    163.           }
    164.       }
    165.   }
    167.   // 返回集合中的最小元素
    168.   public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
    169.       Iterator<? extends T> i = coll.iterator();
    170.       T candidate = i.next();
    172.       while (i.hasNext()) {
    173.           T next = i.next();
    174.           if (next.compareTo(candidate) < 0)
    175.               candidate = next;
    176.       }
    177.       return candidate;
    178.   }
    180.   // 返回集合自然排序最大的元素
    181.   public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
    182.       Iterator<? extends T> i = coll.iterator();
    183.       T candidate = i.next();
    185.       while (i.hasNext()) {
    186.           T next = i.next();
    187.           if (next.compareTo(candidate) > 0)
    188.               candidate = next;
    189.       }
    190.       return candidate;
    191.   }
    193.   // 旋转在指定列表中的元素由所述指定的距离
    194.   public static void rotate(List<?> list, int distance) {
    195.       if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
    196.           rotate1(list, distance);
    197.       else
    198.           rotate2(list, distance);
    199.   }
    201.   private static <T> void rotate1(List<T> list, int distance) {
    202.       int size = list.size();
    203.       if (size == 0)
    204.           return;
    205.       distance = distance % size;
    206.       if (distance < 0)
    207.           distance += size;
    208.       if (distance == 0)
    209.           return;
    211.       for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
    212.           T displaced = list.get(cycleStart);
    213.           int i = cycleStart;
    214.           do {
    215.               i += distance;
    216.               if (i >= size)
    217.                   i -= size;
    218.               displaced = list.set(i, displaced);
    219.               nMoved ++;
    220.           } while (i != cycleStart);
    221.       }
    222.   }
    224.   private static void rotate2(List<?> list, int distance) {
    225.       int size = list.size();
    226.       if (size == 0)
    227.           return;
    228.       int mid =  -distance % size;
    229.       if (mid < 0)
    230.           mid += size;
    231.       if (mid == 0)
    232.           return;
    234.       reverse(list.subList(0, mid));
    235.       reverse(list.subList(mid, size));
    236.       reverse(list);
    237.   }
    239.   // 替换
    240.   public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
    241.       boolean result = false;
    242.       int size = list.size();
    243.       if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
    244.           if (oldVal==null) {
    245.               for (int i=0; i<size; i++) {
    246.                   if (list.get(i)==null) {
    247.                       list.set(i, newVal);
    248.                       result = true;
    249.                   }
    250.               }
    251.           } else {
    252.               for (int i=0; i<size; i++) {
    253.                   if (oldVal.equals(list.get(i))) {
    254.                       list.set(i, newVal);
    255.                       result = true;
    256.                   }
    257.               }
    258.           }
    259.       } else {
    260.           ListIterator<T> itr=list.listIterator();
    261.           if (oldVal==null) {
    262.               for (int i=0; i<size; i++) {
    263.                   if (itr.next()==null) {
    264.                       itr.set(newVal);
    265.                       result = true;
    266.                   }
    267.               }
    268.           } else {
    269.               for (int i=0; i<size; i++) {
    270.                   if (oldVal.equals(itr.next())) {
    271.                       itr.set(newVal);
    272.                       result = true;
    273.                   }
    274.               }
    275.           }
    276.       }
    277.       return result;
    278.   }
    280.   // 返回指定目标列表中第一次出现的指定源列表中的起始位置，或-1
    281.   public static int indexOfSubList(List<?> source, List<?> target) {
    282.       int sourceSize = source.size();
    283.       int targetSize = target.size();
    284.       int maxCandidate = sourceSize - targetSize;
    286.       if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
    287.           (source instanceof RandomAccess&&target instanceof RandomAccess)) {
    288.           nextCand:
    289.           for (int candidate = 0; candidate <= maxCandidate; candidate++) {
    290.               for (int i=0, j=candidate; i<targetSize; i++, j++)
    291.                   if (!eq(target.get(i), source.get(j)))
    292.                       continue nextCand;  // Element mismatch, try next cand
    293.               return candidate;  // All elements of candidate matched target
    294.           }
    295.       } else {  // Iterator version of above algorithm
    296.           ListIterator<?> si = source.listIterator();
    297.           nextCand:
    298.           for (int candidate = 0; candidate <= maxCandidate; candidate++) {
    299.               ListIterator<?> ti = target.listIterator();
    300.               for (int i=0; i<targetSize; i++) {
    301.                   if (!eq(ti.next(), si.next())) {
    302.                       // Back up source iterator to next candidate
    303.                       for (int j=0; j<i; j++)
    304.                           si.previous();
    305.                       continue nextCand;
    306.                   }
    307.               }
    308.               return candidate;
    309.           }
    310.       }
    311.       return -1;  // No candidate matched the target
    312.   }
    314.   // 返回指定目标列表中最后一次出现的指定源列表中的起始位置，或-1
    315.   public static int lastIndexOfSubList(List<?> source, List<?> target) {
    316.       int sourceSize = source.size();
    317.       int targetSize = target.size();
    318.       int maxCandidate = sourceSize - targetSize;
    320.       if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
    321.           source instanceof RandomAccess) {   // Index access version
    322.           nextCand:
    323.           for (int candidate = maxCandidate; candidate >= 0; candidate--) {
    324.               for (int i=0, j=candidate; i<targetSize; i++, j++)
    325.                   if (!eq(target.get(i), source.get(j)))
    326.                       continue nextCand;  // Element mismatch, try next cand
    327.               return candidate;  // All elements of candidate matched target
    328.           }
    329.       } else {  // Iterator version of above algorithm
    330.           if (maxCandidate < 0)
    331.               return -1;
    332.           ListIterator<?> si = source.listIterator(maxCandidate);
    333.           nextCand:
    334.           for (int candidate = maxCandidate; candidate >= 0; candidate--) {
    335.               ListIterator<?> ti = target.listIterator();
    336.               for (int i=0; i<targetSize; i++) {
    337.                   if (!eq(ti.next(), si.next())) {
    338.                       if (candidate != 0) {
    339.                           // Back up source iterator to next candidate
    340.                           for (int j=0; j<=i+1; j++)
    341.                               si.previous();
    342.                       }
    343.                       continue nextCand;
    344.                   }
    345.               }
    346.               return candidate;
    347.           }
    348.       }
    349.       return -1;  // No candidate matched the target
    350.   }
    352.   // 内部类 SynchronizedCollection 实现了Collection接口 内部的方法使用 关键字 synchronized修饰，是线程安全的
    353.   static class SynchronizedCollection<E> implements Collection<E>, Serializable {
    354.       private static final long serialVersionUID = 3053995032091335093L;
    356.       final Collection<E> c;  // Backing Collection
    357.       final Object mutex;     // Object on which to synchronize
    359.       SynchronizedCollection(Collection<E> c) {
    360.           this.c = Objects.requireNonNull(c);
    361.           mutex = this;
    362.       }
    364.       SynchronizedCollection(Collection<E> c, Object mutex) {
    365.           this.c = Objects.requireNonNull(c);
    366.           this.mutex = Objects.requireNonNull(mutex);
    367.       }
    369.       public int size() {
    370.           synchronized (mutex) {return c.size();}
    371.       }
    372.       public boolean isEmpty() {
    373.           synchronized (mutex) {return c.isEmpty();}
    374.       }
    375.       public boolean contains(Object o) {
    376.           synchronized (mutex) {return c.contains(o);}
    377.       }
    378.       public Object[] toArray() {
    379.           synchronized (mutex) {return c.toArray();}
    380.       }
    381.       public <T> T[] toArray(T[] a) {
    382.           synchronized (mutex) {return c.toArray(a);}
    383.       }
    385.       public Iterator<E> iterator() {
    386.           return c.iterator(); // Must be manually synched by user!
    387.       }
    389.       public boolean add(E e) {
    390.           synchronized (mutex) {return c.add(e);}
    391.       }
    392.       public boolean remove(Object o) {
    393.           synchronized (mutex) {return c.remove(o);}
    394.       }
    396.       public boolean containsAll(Collection<?> coll) {
    397.           synchronized (mutex) {return c.containsAll(coll);}
    398.       }
    399.       public boolean addAll(Collection<? extends E> coll) {
    400.           synchronized (mutex) {return c.addAll(coll);}
    401.       }
    402.       public boolean removeAll(Collection<?> coll) {
    403.           synchronized (mutex) {return c.removeAll(coll);}
    404.       }
    405.       public boolean retainAll(Collection<?> coll) {
    406.           synchronized (mutex) {return c.retainAll(coll);}
    407.       }
    408.       public void clear() {
    409.           synchronized (mutex) {c.clear();}
    410.       }
    411.       public String toString() {
    412.           synchronized (mutex) {return c.toString();}
    413.       }
    414.       // Override default methods in Collection
    415.       @Override
    416.       public void forEach(Consumer<? super E> consumer) {
    417.           synchronized (mutex) {c.forEach(consumer);}
    418.       }
    419.       @Override
    420.       public boolean removeIf(Predicate<? super E> filter) {
    421.           synchronized (mutex) {return c.removeIf(filter);}
    422.       }
    423.       @Override
    424.       public Spliterator<E> spliterator() {
    425.           return c.spliterator(); // Must be manually synched by user!
    426.       }
    427.       @Override
    428.       public Stream<E> stream() {
    429.           return c.stream(); // Must be manually synched by user!
    430.       }
    431.       @Override
    432.       public Stream<E> parallelStream() {
    433.           return c.parallelStream(); // Must be manually synched by user!
    434.       }
    435.       private void writeObject(ObjectOutputStream s) throws IOException {
    436.           synchronized (mutex) {s.defaultWriteObject();}
    437.       }
    438.   }
    440.   // 再来看一个 
    441.   // SynchronizedSet 也是线程安全的
    442.   static class SynchronizedSortedSet<E>
    443.       extends SynchronizedSet<E>
    444.       implements SortedSet<E>
    445.   {
    446.       private static final long serialVersionUID = 8695801310862127406L;
    448.       private final SortedSet<E> ss;
    450.       SynchronizedSortedSet(SortedSet<E> s) {
    451.           super(s);
    452.           ss = s;
    453.       }
    454.       SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
    455.           super(s, mutex);
    456.           ss = s;
    457.       }
    459.       public Comparator<? super E> comparator() {
    460.           synchronized (mutex) {return ss.comparator();}
    461.       }
    463.       public SortedSet<E> subSet(E fromElement, E toElement) {
    464.           synchronized (mutex) {
    465.               return new SynchronizedSortedSet<>(
    466.                   ss.subSet(fromElement, toElement), mutex);
    467.           }
    468.       }
    469.       public SortedSet<E> headSet(E toElement) {
    470.           synchronized (mutex) {
    471.               return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex);
    472.           }
    473.       }
    474.       public SortedSet<E> tailSet(E fromElement) {
    475.           synchronized (mutex) {
    476.               return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex);
    477.           }
    478.       }
    480.       public E first() {
    481.           synchronized (mutex) {return ss.first();}
    482.       }
    483.       public E last() {
    484.           synchronized (mutex) {return ss.last();}
    485.       }
    486.   }
    488.   // SynchronizedList 也是内部通过 synchronized 实现线程安全
    489.   static class SynchronizedRandomAccessList<E>
    490.       extends SynchronizedList<E>
    491.       implements RandomAccess {
    493.       SynchronizedRandomAccessList(List<E> list) {
    494.           super(list);
    495.       }
    497.       SynchronizedRandomAccessList(List<E> list, Object mutex) {
    498.           super(list, mutex);
    499.       }
    501.       public List<E> subList(int fromIndex, int toIndex) {
    502.           synchronized (mutex) {
    503.               return new SynchronizedRandomAccessList<>(
    504.                   list.subList(fromIndex, toIndex), mutex);
    505.           }
    506.       }
    508.       private static final long serialVersionUID = 1530674583602358482L;
    510.       /**
    511.        * Allows instances to be deserialized in pre-1.4 JREs (which do
    512.        * not have SynchronizedRandomAccessList).  SynchronizedList has
    513.        * a readResolve method that inverts this transformation upon
    514.        * deserialization.
    515.        */
    516.       private Object writeReplace() {
    517.           return new SynchronizedList<>(list);
    518.       }
    519.   }
    521.   // 其他的也是一样的原理 此处不在赘述
    523.   // 下面再看几个方法 
    524.   // 获取 SynchronizedCollection对象 
    525.   public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
    526.       return new SynchronizedCollection<>(c);
    527.   }
    529.   // 返回线程安全的list
    530.   public static <T> List<T> synchronizedList(List<T> list) {
    531.       return (list instanceof RandomAccess ?
    532.               new SynchronizedRandomAccessList<>(list) :
    533.               new SynchronizedList<>(list));
    534.   }
    536.   // 返回线程安全的Map
    537.   public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
    538.       return new SynchronizedMap<>(m);
    539.   }
    541.   // 其他的也是一样的原理 此处不在赘述
    542.   // 返回一个 空List
    543.   public static final <T> List<T> emptyList() {
    544.       return (List<T>) EMPTY_LIST;
    545.   }
    547.   public static final List EMPTY_LIST = new EmptyList<>();
    549.   private static class EmptyList<E>
    550.       extends AbstractList<E>
    551.       implements RandomAccess, Serializable {
    552.       private static final long serialVersionUID = 8842843931221139166L;
    554.       public Iterator<E> iterator() {
    555.           return emptyIterator();
    556.       }
    557.       public ListIterator<E> listIterator() {
    558.           return emptyListIterator();
    559.       }
    561.       public int size() {return 0;}
    562.       public boolean isEmpty() {return true;}
    564.       public boolean contains(Object obj) {return false;}
    565.       public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
    567.       public Object[] toArray() { return new Object[0]; }
    569.       public <T> T[] toArray(T[] a) {
    570.           if (a.length > 0)
    571.               a[0] = null;
    572.           return a;
    573.       }
    575.       public E get(int index) {
    576.           throw new IndexOutOfBoundsException("Index: "+index);
    577.       }
    579.       public boolean equals(Object o) {
    580.           return (o instanceof List) && ((List<?>)o).isEmpty();
    581.       }
    583.       public int hashCode() { return 1; }
    585.       @Override
    586.       public boolean removeIf(Predicate<? super E> filter) {
    587.           Objects.requireNonNull(filter);
    588.           return false;
    589.       }
    590.       @Override
    591.       public void replaceAll(UnaryOperator<E> operator) {
    592.           Objects.requireNonNull(operator);
    593.       }
    594.       @Override
    595.       public void sort(Comparator<? super E> c) {
    596.       }
    598.       // Override default methods in Collection
    599.       @Override
    600.       public void forEach(Consumer<? super E> action) {
    601.           Objects.requireNonNull(action);
    602.       }
    604.       @Override
    605.       public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
    607.       // Preserves singleton property
    608.       private Object readResolve() {
    609.           return EMPTY_LIST;
    610.       }
    611.   }
    613.   // 其他方法类似于此
    615.   // 返回指定列表的一个动态类型安全视图
    616.   public static <E> List<E> checkedList(List<E> list, Class<E> type) {
    617.       return (list instanceof RandomAccess ?
    618.               new CheckedRandomAccessList<>(list, type) :
    619.               new CheckedList<>(list, type));
    620.   }
    622.   // 其他方法类似于此
    623. }

    总结

  • 从源码我们可以看出来，Collections 类提供了很多操作集合的方法

  • 尤其是在Java集合框架中不是线程安全的如HashSet、HashMap、ArratList、LinkedList等
  • 但是也可以使用JUC下的线程安全的集合框架