Java Collections源码剖析

这篇具有很好参考价值的文章主要介绍了Java Collections源码剖析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Collections以静态方法的方式提供了很多通用算法和功能,这些功能大概可以分为以下两类。

一类是对容器接口对象进行操作,包括查找、排序、添加和修改。

另一类返回一个容器接口对象,适配器:将其他类型的数据转换为容器接口对象+装饰器:修饰一个给定容器接口对象,增加某种性质。

操作容器

查找

Arrays类有针对数组对象的二分查找方法,而Collections提供了针对List接口的二分查找,如下所示:

public static <T> int binarySearch(
       List<? extends Comparable<? super T>> list, T key)
public static <T> int binarySearch(List<? extends T> list,
       T key, Comparator<? super T> c)

从方法参数角度而言,一个要求List的每个元素实现Comparable接口,另一个不需要,但要求提供Comparator。二分查找假定List中的元素是从小到大排序的。List的二分查找的基本思路与Arrays中的是一样的,数组可以根据索引直接定位任意元素,实现效率很高,但List就不一定了,具体分为两种情况,如果List可以随机访问(如数组),即实现了RandomAccess接口,或者元素个数比较少,则实现思路与Arrays一样,根据索引直接访问中间元素进行比较,否则使用选代器的方式移动到中间元素进行比较。从效率角度,如果List支持随机访问,效率O(log2(N)),如果通过选代器,那么比较的次数为O(log2(N)),但遍历移动的次数为O(N),N为列表长度。

此外Collections提供了如下查找最大值/最小值的方法,实现思路也很简单,就是通过迭代器进行比较:

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

还可以查找元素出现次数,返回元素o在容器c中出现的次数,o可以为null,实现思路就是通过迭代器进行比较计数。

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

Collections还提供了查找元素位置的方法,在List中查找target的位置:

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

indexOfSubList从开头找,lastIndexOfSubList从结尾找,没找到返回-1,找到返回第一个匹配元素的索引位置。这两个方法的实现都是属于“暴力破解”型的,将target列表与source从第一个元素开始的列表逐个元素进行比较,如果不匹配,则与source从第二个元素开始的列表比较,再不匹配,与source从第三个元素开始的列表比较,以此类推。

排序

针对List接口对象,Collections除了提供基础的排序,还提供了若干调整顺序的方法,包括交换元素位置、翻转列表顺序、随机化重排、循环移位等。

Arrays类有针对数组对象的排序方法,Collections提供了针对List接口的排序方法,如下所示:

public static <T extends Comparable<? super T>> void sort(List<T> list)
public static <T> void sort(List<T> list, Comparator<? super T> c)

内部是通过Arrays.sort实现的,先将List元素复制到一个数组中,然后使用Arrays.sort,排序后,再复制回List。代码如下所示:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
       Object[] a = list.toArray();
       Arrays.sort(a);
       ListIterator<T> i = list.listIterator();
       for(int j=0; j<a.length; j++) {
           i.next();
           i.set((T)a[j]);
       }
}

交换元素位置的方法为:

public static void swap(List<?> list, int i, int j)

交换List中第i个和第j个元素的内容。实现代码为:

public static void swap(List<?> list, int i, int j) {
       final List l = list;
       l.set(i, l.set(j, l.get(i)));
}

翻转列表顺序的方法为:

public static void reverse(List<?> list)

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

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

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

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

public static <T> void shuffle(List<T> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i = size; i > 1; i--) {
                int swapIndex = rnd.nextInt(i);
                Collections.swap(list, i - 1, swapIndex);
            }
        } else {
            Object[] arr = list.toArray();
            for (int i = size; i > 1; i--) {
                int swapIndex = rnd.nextInt(i);
                Object temp = arr[i - 1];
                arr[i - 1] = arr[swapIndex];
                arr[swapIndex] = temp;
            }
            ListIterator<T> it = list.listIterator();
            for (int i = 0; i < arr.length; i++) {
                it.next();
                it.set((T) arr[i]);
            }
        }
    }

添加和修改

Collections也提供了几个批量添加和修改的方法

批量添加,方法为:

public static <T> boolean addAll(Collection<? super T> c, T... elements)

批量填充固定值,方法为:

public static <T> void fill(List<? super T> list, T obj)

这个方法与Arrays类中的fill方法是类似的,给每个元素设置相同的值。

批量复制,方法为:

public static <T> void copy(List<? super T> dest, List<? extends T> src)

将列表src中的每个元素复制到列表dest的对应位置处,覆盖dest中原来的值,dest的列表长度不能小于src,dest中超过src长度部分的元素不受影响。

返回容器

适配器

适配器,就是将一种类型的接口转换成另一种接口,类似于电子设备中的各种USB转接头,一端
连接某种特殊类型的接口,一段连接标准的USB接口。Collections类提供了几组类似于适配器的方法:
·空容器方法:类似于将null或“空”转换为一个标准的容器接口对象。
·单一对象方法:将一个单独的对象转换为一个标准的容器接口对象。
·其他适配方法:将Map转换为Set等。

空容器方法返回一个不包含任何元素的容器接口对象,分别返回一个空的List、Set、Map和Iterator对象。实际使用中,空容器对象经常用作方法返回值。

public static final <T> List<T> emptyList()
public static final <T> Set<T> emptySet()
public static final <K,V> Map<K,V> emptyMap()
public static <T> Iterator<T> emptyIterator()

Collections中还有一组方法,可以将一个单独的对象转换为一个标准的容器接口对象,比如:

public static <T> Set<T> singleton(T o)
public static <T> List<T> singletonList(T o)
public static <K,V> Map<K,V> singletonMap(K key, V value)

这些方法也经常用于构建方法返回值,相比新建容器对象并添加元素,这些方法更为简洁方便,此外,它们的实现更为高效,它们的实现类都针对单一对象进行了优化。

装饰器

装饰器接受一个接口对象,并返回一个同样接口的对象,不过,新对象可能会扩展一些新的方法或属性,扩展的方法或属性就是所谓的“装饰”,也可能会对原有的接口方法做一些修改,达到一定的“装饰"目的。Collections有三组装饰器方法,它们的返回对象都没有新的方法或属性,但改变了原有接口方法的性质,经过“装饰”后,它们更为安全了,具体分别是写安全、类型安全和线程安全。

public static <T> Collection<T> unmodifiableCollection(
Collection<? extends T> c)
public static <T> List<T> unmodifiableList(List<? extends T> list)
public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m)
public static <T> Set<T> unmodifiableSet(Set<? extends T> s)

这组unmodifiableXXX方法是使容器对象变为只读的,写入会报UnsupportedOperationException异常。典型场景是:需要传递一个容器对象给一个方法,这个方法可能是第三方提供的,为避免第三方误写,所以在传递前,变为只读的。

这些方法是如何实现的呢?每个方法内部都对应一个类,这个类实现了对应的容器接口,它内部是待装饰的对象,只读方法传递给这个内部对象,写方法抛出异常。比如unmodifiableCollection方法的代码为:

public static <T> Collection<T> unmodifiableCollection(
       Collection<? extends T> c) {
       return new UnmodifiableCollection<>(c);
}

所谓类型安全是指确保容器中不会保存错误类型的对象。

如果我们创建了一个Integer类型的List对象,但添加了字符串类型的对象"hello",编译没有错误,运行也没有异常,程序输出为"[hello]"。
之所以会出现这种情况,是因为Java是通过擦除来实现泛型的,而且类型参数是可选的。正常情况下,我们会加上类型参数,让泛型机制来保证类型的正确性。但是,由于泛型是Java5以后才加入的,之前的代码可能没有类型参数,而新的代码可能需要与老的代码互动。为了避免老的代码用错类型,确保在泛型机制失灵的情况下类型的正确性,可以在传递容器对象给老代码之前,使用类似如下方法“装饰”容器对象:

public static <E> List<E> checkedList(List<E> list, Class<E> type)
public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
Class<K> keyType, Class<V> valueType)
public static <E> Set<E> checkedSet(Set<E> s, Class<E> type)

使用这组checkedXXX方法,都需要传递类型对象,这些方法都会使容器对象的方法在运行时检查类型的正确性,如果不匹配,会抛出ClassCastException异常。

当多个线程同时读写同一个容器对象,是不安全的。Collections提供了一组方法,可以将一个容器对象变为线程安全的,比如:

public static <T> Collection<T> synchronizedCollection(Collection<T> c)
public static <T> List<T> synchronizedList(List<T> list)
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)

这些方法都是通过给所有容器方法加锁来实现的,这种实现并不是最优的。对此,Java提供了很多专门针对并发访问的容器类。文章来源地址https://www.toymoban.com/news/detail-825687.html

到了这里,关于Java Collections源码剖析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java API - Object类的常用API

    API概念 什么是API? API(Application Programming interface) 应用程序编程接口。 简单来说:就是Java帮我们已经写好的一些方法**, 我们直接拿过来用就可以了 。** Object类 Object类的作用: Object类的方法是一切子类对象都可以直接使用的,所以我们要学习Object类的方法。 一个类要么默认继

    2023年04月08日
    浏览(45)
  • Java中的String类的常用方法(对于字符串的常用操作)

    目录 一、获取指定索引的字符 二、 获取指定字符或者字符串的索引位置 三、判断字符串是否以指定内容开头或结尾 四、替换指定的字符或者是字符串 五、获取字符串的子串 六、将字符串转换为字符数组  七、比较字符串的内容是否相等  八、连接字符串 九、比较两个字

    2024年02月20日
    浏览(73)
  • JVM源码剖析之Java对象创建过程

    关于 \\\"Java的对象创建\\\" 这个话题分布在各种论坛、各种帖子,文章的水平参差不齐。并且大部分仅仅是总结 \\\"面试宝典\\\" 的流程,小部分就是copy其他帖子,极少能看到拿源码作为论证。所以特意写下这篇文章。 版本信息如下: 首先把总结图放在这。接下来分析源码~  用一个

    2024年02月12日
    浏览(48)
  • Java中创建List接口、ArrayList类和LinkedList类的常用方法(一)

    要了解List接口,就不得不说起Java的集合框架。 (该图来自菜鸟教程) Java 集合框架主要包括两种类型的容器,集合Collection和图Map。 Collection接口代表了 单列集合 ,它包含了一组Object元素,每个元素都有一个值。 (这里有个“泛型擦除”的概念,在此不提及有兴趣可自行了

    2024年01月19日
    浏览(50)
  • Java语言------四种内部类的详细讲解

    目录 一.内部类的介绍 二.内部类的种类 2.1实例内部类       2.2.静态内部类 2.3局部内部类 2.4匿名内部类 总结        内部类: 一个类定义在  另一个类  的  内部。        内部类分为 四种 : 实例内部类、静态内部类、局部内部类、匿名内部类。 使用时机:当一个事

    2023年04月25日
    浏览(43)
  • 进阶JAVA篇- LocalDate 类与 LocalTime 类、LocalDateTime 类的常用API(六)

    目录 API                      1.0 LocalDate 类与 LocalTime 类、LocalDateTime 类的API说明         1.1 如何 创建 LocalDate 类与 LocalTime 类、LocalDateTime 类的对象         1.2 LocalDate 类与 LocalTime 类、LocalDateTime 类中的以  get 开头实例方法         1.3 LocalDateTime 类中的 toL

    2024年02月08日
    浏览(45)
  • Java中List接口两个实现,ArrayList类和LinkedList类的常用方法(一)

    要了解List接口,就不得不说起Java的集合框架。 (该图来自菜鸟教程) Java 集合框架主要包括两种类型的容器,集合Collection和图Map。 Collection接口代表了 单列集合 ,它包含了一组Object元素,每个元素都有一个值。 (这里有个“泛型擦除”的概念,在此不提及有兴趣可自行了

    2024年01月19日
    浏览(39)
  • Java语言开发的AI智慧导诊系统源码springboot+redis 3D互联网智导诊系统源码

    Java 语言开发的AI智慧导诊系统源码 springboot+redis 3D 互联网智导诊系统源码 智慧导诊解决盲目就诊问题,减轻分诊工作压力。降低挂错号比例,优化就诊流程,有效提高线上线下医疗机构接诊效率。可通过人体画像选择症状部位,了解对应病症信息和推荐就医科室。 智慧导诊

    2024年04月23日
    浏览(48)
  • 进阶JAVA篇- Collection 类的常用的API与 Collection 集合的遍历方式

    目录         1.0 Collection 类的说明         1.1 Collection 类中的实例方法         2.0 Collection 集合的遍历方式(重点)         2.1 使用迭代器( Iterator )进行遍历         2.2 使用增强型 for 循环进行遍历         2.3 使用 Java 8的 Stream API 进行遍历(使用 Lambda 表达式进

    2024年02月08日
    浏览(47)
  • Java开发 - 不知道算不算详细的MySQL多维度性能优化剖析

    MySQL性能优化是一个很大的话题,小到一句SQL,大到一个系统,都是我们优化的目标,博主之前曾写过一篇关于SQL优化的博客,感兴趣的小伙伴直接点击即可。本篇,我们将从多个维度来讲解MYSQL性能优化相关的内容,读完此篇,你将初步了解有哪些MySQL的优化策略,以及怎么

    2024年02月06日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包