首页 > 编程语言 >Java工具类Collections

Java工具类Collections

时间：2023-02-17 16:58:56浏览次数：53  
标签：Java int list List Collections static 工具 public

一、概述

Collections工具类提供了大量针对Collection和Map的操作，都为静态(static)方法，总体可分为四类：

  • 排序操作
  • 查找、替换操作
  • 同步控制
  • 设置不可变(只读)集合

二、排序操作

Collections提供以下方法对List进行排序操作：

  • void reverse(List<?> list)：翻转列表顺序。
  • void shuffle(List<?> list)：随机排序。
  • void sort(List list)：按自然排序的升序排序。
  • void sort(List list, Comparator c)：定制排序，由Comparator控制排序逻辑。
  • void swap(List<?> list, int i, int j)：交换两个索引位置的元素。
  • void rotate(List<?> list, int distance)：旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将list的前distance个元素整体移到后面。

2.1 reverse方法

将list中的元素顺序翻转过来。实现思路就是将第一个和最后一个交换，第二个和倒数第二个交换，依次类推直到中间两个元素交换完毕。

如果list实现了RandomAccess接口或列表比较小，根据索引位置，使用上面的swap方法进行交换，否则，由于直接根据索引位置定位元素效率比较低，使用一前一后两个listIterator定位待交换的元素。具体代码为：

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

案例：

public class CollectionsTest {

    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(new Integer[]{
                8, -3, 2, 9, -2
        });
        System.out.println(nums);
        Collections.reverse(nums);
        System.out.println(nums);
    }
}

输出：

[8, -3, 2, 9, -2]
[-2, 9, 2, -3, 8]

2.2 shuffle方法

Collections直接提供了对List元素洗牌的方法：

public static void shuffle(List<?> list);
public static void shuffle(List<?> list, Random rnd);

实现思路是从后往前遍历列表，逐个给每个位置重新赋值，值从前面的未重新赋值的元素中随机挑选。如果列表实现了RandomAccess接口，或者列表比较小，直接使用前面swap方法进行交换，否则，先将列表内容拷贝到一个数组中，洗牌，再拷贝回列表。代码如下：

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

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i = 0; i < arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

演示:

public class CollectionsTest {

    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(new Integer[]{
                8, -3, 2, 9, -2
        });
        System.out.println(nums);

        Collections.shuffle(nums);
        
        System.out.println(nums);
    }
}

结果:

[8, -3, 2, 9, -2]
[-3, 8, -2, 2, 9]

2.3 rotate方法

public static void rotate(List<?> list, int distance);

distance表示循环移位个数，一般正数表示向右移，负数表示向左移，比如：

public class CollectionsTest {

    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(new Integer[]{
                8, 5, 3, 6, 2
        });
        Collections.rotate(list1, 2);
        System.out.println(list1);

        List<Integer> list2 = Arrays.asList(new Integer[]{
                8, 5, 3, 6, 2
        });
        Collections.rotate(list2, -2);
        System.out.println(list2);
    }
}

输出为：

[6, 2, 8, 5, 3]
[3, 6, 2, 8, 5]

这个方法很有用的一点是，它也可以用于子列表，可以调整子列表内的顺序而不改变其他元素的位置。比如，将第j个元素向前移动到k (k>j)，可以这么写：

Collections.rotate(list.subList(j, k + 1), -1);

再举个例子：

public class CollectionsTest {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(new Integer[]{
                8, 5, 3, 6, 2, 19, 21
        });
        Collections.rotate(list.subList(1, 5), 2);
        System.out.println(list);
    }
}

输出为：

[8, 6, 2, 5, 3, 19, 21]

这个类似于列表内的"剪切"和"粘贴"，将子列表[5, 3]"剪切"，"粘贴"到2后面。如果需要实现类似"剪切"和"粘贴"的功能，可以使用rotate方法。

循环移位的内部实现比较巧妙，根据列表大小和是否实现了RandomAccess接口，有两个算法，都比较巧妙，两个算法在《编程珠玑》这本书的2.3节有描述。

篇幅有限，我们只解释下其中的第二个算法，它将循环移位看做是列表的两个子列表进行顺序交换。再来看上面的例子，循环左移2位：

[8, 5, 3, 6, 2] -> [3, 6, 2, 8, 5]

就是将[8, 5]和[3, 6, 2]两个子列表的顺序进行交换。

循环右移两位：

[8, 5, 3, 6, 2] -> [6, 2, 8, 5, 3]

就是将[8, 5, 3]和[6, 2]两个子列表的顺序进行交换。

根据列表长度size和移位个数distance，可以计算出两个子列表的分隔点，有了两个子列表后，两个子列表的顺序交换可以通过三次翻转实现，比如有A和B两个子列表，A有m个元素，B有n个元素：

\[a_{1}a_{2}...a_{m}b_{1}b_{2}...b_{n} \]

要变为：

\[b_{1}b_{2}...b_{n}a_{1}a_{2}...a_{m} \]

可经过三次翻转实现：

  1. 翻转子列表A

\[a_{1}a_{2}...a_{m}b_{1}b_{2}...b_{n} \rightarrow a_{m}...a_{2}a_{1}b_{1}b_{2}...b_{n} \]

  1. 翻转子列表B

\[a_{m}...a_{2}a_{1}b_{1}b_{2}...b_{n} \rightarrow a_{m}...a_{2}a_{1}b_{n}...b_{2}b_{1} \]

  1. 翻转整个列表

\[a_{m}...a_{2}a_{1}b_{m}...b_{2}b_{1} \rightarrow b_{1}b_{2}...b_{n}a_{1}a_{2}...a_{m} \]

这个算法的整体实现代码为：

private static void rotate2(List<?> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    int mid = -distance % size;
    if (mid < 0)
        mid += size;
    if (mid == 0)
        return;

    reverse(list.subList(0, mid));
    reverse(list.subList(mid, size));
    reverse(list);
}

mid为两个子列表的分割点，调用了三次reverse以实现子列表顺序交换。

三、查找，替换操作

  • int binarySearch(List list, Object key),：对List进行二分查找，返回索引，注意List必须是有序的。
  • int max(Collection coll)：根据元素的自然顺序，返回最大的元素。类比int min(Collection coll)。
  • int max(Collection coll, Comparator c)：根据定制排序，返回最大元素，排序规则由Comparator类控制。类比int min(Collection coll, Comparator c)。
  • void fill(List list, Object obj)：用元素obj填充list中所有元素。
  • int frequency(Collection c, Object o)：统计元素出现次数。
  • int indexOfSubList(List list, List target)：统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)。
  • boolean replaceAll(List list, Object oldVal, Object newVal)：用新元素替换旧元素。

3.1 binarySearch方法

List的二分查找的基本思路与Arrays中的是一样的，但数组可以根据索引直接定位任意元素，实现效率很高，List就不一定了，我们来看它的实现代码：

public static <T> 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);
}

分为两种情况，如果List可以随机访问(如数组)，即实现了RandomAccess接口，或者元素个数比较少，则实现思路与Arrays一样，调用indexedBinarySearch根据索引直接访问中间元素进行查找，否则调用iteratorBinarySearch使用迭代器的方式访问中间元素进行查找。

indexedBinarySearch的代码为：

private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
    int low = 0;
    int high = list.size()-1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = list.get(mid);
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found
}

调用list.get(mid)访问中间元素。

iteratorBinarySearch的代码为：

private static <T> int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key) {
    int low = 0;
    int high = list.size()-1;
    ListIterator<? extends Comparable<? super T>> i = list.listIterator();

    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = get(i, mid);
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found
}

调用get(i, mid)寻找中间元素，get方法的代码为：

private static <T> T get(ListIterator<? extends T> i, int index) {
    T obj = null;
    int pos = i.nextIndex();
    if (pos <= index) {
        do {
            obj = i.next();
        } while (pos++ < index);
    } else {
        do {
            obj = i.previous();
        } while (--pos > index);
    }
    return obj;
}

通过迭代器方法逐个移动到期望的位置。

我们来分析下效率，如果List支持随机访问，效率为\(O(log2(N))\)，如果通过迭代器，比较的次数为\(O(log2(N))\)，但遍历移动的次数为\(O(N)\)，N为列表长度。

3.2 max方法

Collections提供了如下查找最大最小值的方法：

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)

含义和用法都很直接，实现思路也很简单，就是通过迭代器进行比较，比如，其中一个方法的代码为：

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

3.3 frequency方法

方法为：

public static int frequency(Collection<?> c, Object o);

返回元素o在容器c中出现的次数，o可以为null。含义很简单，实现思路也是，就是通过迭代器进行比较计数。

3.4 indexOfSubList方法

对List接口对象，Collections提供了类似方法，在source List中查找target List的位置：

public static int indexOfSubList(List<?> source, List<?> target);
public static int lastIndexOfSubList(List<?> source, List<?> target);

indexOfSubList从开头找，lastIndexOfSubList从结尾找，没找到返回-1，找到返回第一个匹配元素的索引位置，比如：

public class CollectionsTest {

    public static void main(String[] args) {
        List<Integer> source = Arrays.asList(new Integer[]{
                35, 24, 13, 12, 8, 24, 13, 7, 1
        });
        System.out.println(Collections.indexOfSubList(source, Arrays.asList(new Integer[]{24, 13})));
        System.out.println(Collections.lastIndexOfSubList(source, Arrays.asList(new Integer[]{24, 13})));
    }
}

输出为：

1
5

这两个方法的实现都是属于"暴力破解"型的，将target列表与source从第一个元素开始的列表逐个元素进行比较，如果不匹配，则与source从第二个元素开始的列表比较，再不匹配，与source从第三个元素开始的列表比较，依次类推。

3.5 replaceAll方法

替换方法为：

public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal);

将List中的所有oldVal替换为newVal，如果发生了替换，返回值为true，否则为false。

四、同步控制

Collections中几乎对每个集合都定义了同步控制方法，例如SynchronizedList()，SynchronizedMap()等方法，来将集合包装成线程安全的集合。下面是Collections将普通集合包装成线程安全集合的用法，

public class SynchronizedTest {

    public static void main(String[] args) {
        Collection<String> collection = Collections.synchronizedCollection(new ArrayList<>());
        List<String> list = Collections.synchronizedList(new ArrayList<>());
        Set<String> set = Collections.synchronizedSet(new HashSet<>());
        Map<String, String> map = Collections.synchronizedMap(new HashMap<>());
    }
}

4.1 SynchronizedMap源码

Collections.synchronizedMap静态调用如下：

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

在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁mutex。

private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {

    private final Map<K, V> m;     // Backing Map
    final Object mutex;        // Object on which to synchronize

    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 V put(K key, V value) {
        synchronized (mutex) {
            return m.put(key, value);
        }
    }
    //...
}

我们在调用这个方法的时候就需要传入一个Map，可以看到有两个构造器，如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。

如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象，就是上面的Map。创建出synchronizedMap之后，再操作map的时候，就会对方法上锁。

五、设置不可变(只读)集合

Collections提供了三类方法返回一个不可变集合，

  • emptyXXX()：返回一个空的只读集合。
  • singleXXX()：返回一个只包含指定对象，只有一个元素，只读的集合。
  • unmodifiableXXX()：返回指定集合对象的只读视图。

用法如下：

public class UnmodifiableCollection {

    public static void main(String[] args) {
        List<Integer> list = Collections.emptyList();
        Set<String> set = Collections.singleton("avs");
        Map<String, Integer> map = new HashMap<>();
        map.put("a", 100);
        map.put("b", 200);
        map.put("c", 150);
        Map<String, Integer> readOnlyMap = Collections.unmodifiableMap(map);

        //下面会报错
        list.add(100);
        set.add("sdf");
        map.put("d", 300);
    }
}

执行结果:

Exception in thread "main" java.lang.UnsupportedOperationException
 at java.util.AbstractList.add(Unknown Source)
 at java.util.AbstractList.add(Unknown Source)
 at collection.collections.UnmodifiableCollection.main(UnmodifiableCollection.java:22)

5.1 emptyList

emptyList返回的是一个静态不可变对象，它可以节省创建新对象的内存和时间开销。我们来看下emptyList的具体定义：

public static final <T> List<T> emptyList() {
    return (List<T>) EMPTY_LIST;
}

EMPTY_LIST的定义为：

public static final List EMPTY_LIST = new EmptyList<>();

是一个静态不可变对象，类型为EmptyList，它是一个私有静态内部类，继承自AbstractList，主要代码为：

private static class EmptyList<E>
        extends AbstractList<E>
        implements RandomAccess {

    public Iterator<E> iterator() {
        return emptyIterator();
    }
    public ListIterator<E> listIterator() {
        return emptyListIterator();
    }

    public int size() {return 0;}
    public boolean isEmpty() {return true;}

    public boolean contains(Object obj) {return false;}
    public boolean containsAll(Collection<?> c) { return c.isEmpty(); }

    public Object[] toArray() { return new Object[0]; }

    public <T> T[] toArray(T[] a) {
        if (a.length > 0)
            a[0] = null;
        return a;
    }

    public E get(int index) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }

    public boolean equals(Object o) {
        return (o instanceof List) && ((List<?>)o).isEmpty();
    }

    public int hashCode() { return 1; }
}

如果返回值只是用于读取，可以使用emptyList方法，但如果返回值还用于写入，则需要新建一个对象。

六、其他

  • disjoint(Collection c1, Collection c2)：如果两个指定collection中没有相同的元素，则返回true。
  • addAll(Collection<? super T> c, T... a)：一种方便的方式，将所有指定元素添加到指定collection中。示范：Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
  • Comparator reverseOrder(Comparator cmp)：返回一个比较器，它强行反转指定比较器的顺序。如果指定比较器为null，则此方法等同于reverseOrder()(换句话说，它返回一个比较器，该比较器将强行反转实现Comparable接口那些对象collection上的自然顺序)。
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class OtherCollection {

    public static void main(String[] args) {
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();

        // addAll增加变长参数
        Collections.addAll(list1, "大家好", "你好", "我也好");
        Collections.addAll(list2, "大家好", "a李四", "我也好");

        // disjoint检查两个Collection是否的交集
        boolean b1 = Collections.disjoint(list, list1);
        boolean b2 = Collections.disjoint(list, list2);
        System.out.println(b1 + "\t" + b2);

        // 利用reverseOrder倒序
        Collections.sort(list1, Collections.reverseOrder());
        System.out.println(list1);
    }
}

输出

true false
[我也好, 大家好, 你好]

6.1 disjoint方法

方法为：

public static boolean disjoint(Collection<?> c1, Collection<?> c2);

如果c1和c2有交集，返回值为false，没有交集，返回值为true。

实现原理也很简单，遍历其中一个容器，对每个元素，在另一个容器里通过contains方法检查是否包含该元素，如果包含，返回false，如果最后不包含任何元素返回true。这个方法的代码会根据容器是否为Set以及集合大小进行性能优化，即选择哪个容器进行遍历，哪个容器进行检查，以减少总的比较次数，具体我们就不介绍了。

参考文章

标签：Java,int,list,List,Collections,static,工具,public
From： https://www.cnblogs.com/ciel717/p/17112658.html

相关文章

  • 求1到100的总和 java 230217
    新增一个变量s保存总结果给这个s初始化值为0每次得到循环的数字后就给这个变量s进行累加代码：publicclassTest{publicstaticvoidmain(String[]args){//......
  • 超好用的 Redis GUI 工具，你值得拥有
    超好用的RedisGUI工具，你值得拥有提供原生的性能，并且比使用Electron等Web技术开发的同等应用程序消耗的资源少得多。下载地址：http://www.redisant.cn/功能介绍实......
  • 介绍一款读写分离工具
    一、读写分离介绍1、What读写分离？基本的原理是让主数据库处理事务增、改、删操作（INSERT、UPDATE、DELETE），而从数据库处理SELECT查询操作。2、why为何要读写分离？......
  • JavaEE_使用mybatis从数据库中获取分页数据，并在web端显示
    idea+servlet+jsp+jstl+mysql+mybatis。    一、准备数据库数据表（数据）二、准备数据对象（pojo），创建对象set/get方法2.1单个数据对象2.2页内数据对象......
  • 10个常用的JS工具库，80%的项目都在用
    Day.js一个极简的处理时间和日期的JavaScript库，和 Moment.js的API设计保持一样,但体积仅有2KB。qs一个轻量的url参数转换的JavaScript库js-cookie一个简单......
  • 如何复制一个java对象（浅克隆与深度克隆）
    在项目中，有时候有一些比较重要的对象经常被当作参数传来传去，和C语言的值传递不同，java语言的传递都是引用传递，在任何一个地方修改了这个对象的值，就会导......
  • java异常信息打印
    如果你不仅想在日志中查看异常信息，也想把异常信息保存起来作为数据查看，那么你可以这样做 publicvoidprintException(Exceptione){ByteArrayOutputStr......
  • java的历史 230217
    Java是由SunMicrosystems公司于1995年5月推出的高级程序设计语言。它由JamesGosling和其他Sun工程师们一起研发，主要服务于消费电子产品，如智能手机、平板电脑、家用电器等......
  • Java-webshell 排查
    参考：https://javasec.org/javaweb/MemoryShell/https://goodapple.top/archives/1355简介本次分享为javawebshell排查初级。抛砖引玉java获取web权限的shell......
  • JavaScript常见问题梳理
    1、this指向1、全局函数this指向全局对象window，注意严格模式下，this为undefined//[objectWindow]alert(this);functionf(){alert(this)}f()//undefinedfu......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99