最新要闻
- 天天微资讯!2023油价调整窗口时间表一览
- 马斯克 一统海外充电江湖!
- 新增自动拍摄功能:尼康Z9获4.00版本固件更新
- 90后小伙中1000万大奖 淡定回应先去上个班:不着急领
- 看热讯:阵容强大!长城汽车17位高管集体入驻微博:吉利副总裁盛赞
- 史低价!小米米家无线洗地机2开启618预售:仅1799元-当前视点
- 视点:过山车行情后,建筑钢材市场行情或易涨难跌
- 油价小幅下调 加一箱油将少花2元 全球最资讯
- 中海达(300177)6月13日主力资金净买入525.51万元_天天通讯
- PMR机械硬盘走到尽头了!西数/希捷正疯狂自救
- 6旬老人守株待兔式飞奔撞车碰瓷索赔 车主吓坏:监控还清白 环球精选
- 广东有多热?网友在广东买虾 还没到家就熟了 世界今日讯
- 美国再将31家中企列入“实体清单”!
- 2999元的国产显卡值不值得冲?实测3A大作给你答案
- 焦点信息:天津:“多卡合一”创新服务“城市小蜜蜂”
- 全球快报:小米卢伟冰:小米13 Ultra在意法西德及香港地区正式开售 销售超预期
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
【快播报】Collections类源码初探
最近重温Java知识,遇到不懂的问题搜索互联网/博客很难直接找到答案,还好如今有了chatGPT,比网上大多数CV复读机/纯文档翻译的内容更有用。本文尝试深入探索Java Collections类的底层原理,领悟代码的设计初衷,学习借鉴优秀的编程思想,并启发开发者写出高质量代码。
目录- 包 Package
- 静态成员
- 静态方法
- 排序
- 二分查找
- 反转列表
- 打乱 shuffle
- 覆盖 fill / 拷贝 copy / 替换 replaceAll
- 旋转 rotate
- 其他方法
- 内部类
包 Package
Collections类位于 java.util 包中。源代码第一行 package java.util;
表示Collections所在的包(Package)。java.util包还包含其他的类、接口,在同一个包下Java编译器默认会自动加载这些类。包的设计是为了方便代码的组织和管理,使用时不需要import语句导入每一个文件,也可以避免命名冲突(不同的包名下可以有相同的类名)。
静态成员
Collections是一个算法合集,可以看到构造器是由 private
修饰的,无法实例化。因此成员和方法都是 static 静态的。接下来的代码是静态成员,注释已经说明了这些常量是为了更好算法性能的调整参数。下面所有阈值都是在元素个数较小或者支持随机访问RandomAccess的列表中依据经验选取的参数。变量名第一个单词表示对应的算法。后面通过源码将分析这些成员的作用。
(相关资料图)
private static final int BINARYSEARCH_THRESHOLD = 5000; private static final int REVERSE_THRESHOLD = 18; private static final int SHUFFLE_THRESHOLD = 5; private static final int FILL_THRESHOLD = 25; private static final int ROTATE_THRESHOLD = 100; private static final int COPY_THRESHOLD = 10; private static final int REPLACEALL_THRESHOLD = 11; private static final int INDEXOFSUBLIST_THRESHOLD = 35;
静态方法
排序
排序算法方法体比较简单,根据形参是否带比较器 Comparator,有两种实现。不带比较器的 sort
方法由 public static
修饰,后面是一个泛型定义的语法。先看内层,? super T
是Comparable接口的泛型参数,其中 ? super
是下界通配符,保证Comparable接口能够使用T或T的超类作为类型参数。因此 sort 方法的泛型类型 T 必须是实现了Comparable接口,并且Comparable接口的类型参数是T或者T的父类。Comparator和Comparable区别
- Comparable是一个内部比较器接口,它对实现这个接口的对象进行自然排序的方式提供了统一的规范,因此只有一个方法 compareTo()。
- Comparator是一个外部比较器接口,它允许在实现这个接口的类之外进行比较操作,因此有两个方法 compare() 和 equals()。
- 基本数据类型的装箱类型,也就是包装类,如Integer、Double等都实现了Comparable接口,它们可以进行自然排序,具体实现是通过实现Comparable
接口中的compareTo(T o)方法来实现的。当我们需要自定义实现排序规则时,可以使用Comparator来定义。
public final class Integer extends Number implements Comparable { // ... public int compareTo(Integer anotherInteger) { return compare(this.value, anotherInteger.value); } // ...}
我们回到sort,跟踪调用的 sort
源码,可以看到底层提供了 mergeSort
和 Timsort.sort
两种排序方法。在JDK8中,Arrays.sort()和Collections.sort()都是采用了Timsort算法(LegacyMergeSort.userRequested
默认为 false)。
jdk1.7之前的排序是归并排序,legacyMergeSort此方法就是1.7为了兼容之前版本的归并排序。Timsort是一种排序算法,由Tim Peters在2002年为Python实现的。它是融合归并排序(Merge Sort)和插入排序(Insertion Sort)的一种排序算法,具有稳定性,且在最坏情况下的时间复杂度也能达到O(nlogn)。
二分查找
列表必须有序(根据Comparable升序),只有对于支持随机访问的列表可以达到 O(logn)
的查找性能。否则即便是 logn 次比较,也需要线性的遍历时间(迭代器获得中间节点)。
反转列表
这里 REVERSE_THRESHOLD
派上用场,当列表长度小于18,或者支持随机访问时,直接调用 swap 方法交换首尾元素。否则则用迭代器来进行赋值/设置(set方法)。为什么不都用swap来交换呢?查看swap源码,有两种实现:
public static void swap(List> list, int i, int j) { // 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 final List l = list; l.set(i, l.set(j, l.get(i))); } private static void swap(Object[] arr, int i, int j) { Object tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
对于列表的反转,会调用第一个方法,其中 set 方法赋值会创建新的对象并返回旧的对象引用,因此 list.set(i, list.set(j, list.get(i)))
代码产生了两个中间临时对象。在大规模数据操作中,这种频繁的对象创建和回收会影响系统性能。因此,在列表长度大于等于 18 要进行反转时,Java提供了更加高效的 swap 方式,即仅通过一个对象引用来保存交换过程种的对象位置,然后通过迭代器设置新的位置。
// else 部分 ListIterator fwd = list.listIterator(); ListIterator rev = list.listIterator(size); for (int i=0, mid=list.size()>>1; i
打乱 shuffle
打乱算法用到了洗牌算法,逆序将第 i 个元素与前 i 个的随机元素交换。与前面类似,当列表长度大于等于SHUFFLE_THRESHOLD
时,选择将 List转化为 对象数组 Object[] arr = list.toArray();
,然后执行交换过程,最后再通过迭代器完成赋值。
覆盖 fill / 拷贝 copy / 替换 replaceAll
fill方法将列表中所有元素替换为传入值,copy方法将源列表内容拷贝到目标列表(要求不小于源列表长度),replaceAll将所有原始值替换为新的值。同样,在大于等于对应的阈值 FILL_THRESHOLD
、 COPY_THRESHOLD
和 REPLACEALL_THRESHOLD
时,使用迭代器避免频繁的对象创建和销毁的开销。
旋转 rotate
这个方式实现了列表元素的循环移动(右移)。核心算法逻辑为三次就地反转,这避免了额外的内存开销。
// mid 为 size减去右移距离 reverse(list.subList(0, mid)); reverse(list.subList(mid, size)); reverse(list);
其他方法
- indexOfSubList:查找目标列表在源列表中作为子列表的第一次出现的位置
- lastIndexOfSubList:查找目标列表在源列表中作为子列表的最后一次出现的位置
内部类
按照源码的声明顺序包含有以下静态内部类:
- UnmodifiableCollection
- UnmodifiableSet
- UnmodifiableSortedSet
- UnmodifiableNavigableSet
- UnmodifiableList
- UnmodifiableRandomAccessList
- UnmodifiableMap
- UnmodifiableEntrySet:UnmodifiableMap的内部类
- UnmodifiableSortedMap
- UnmodifiableNavigableMap
- EmptyNavigableMap
- SynchronizedCollection
- SynchronizedSet
- SynchronizedSortedSet
- SynchronizedNavigableSet
- SynchronizedList
- SynchronizedRandomAccessList
- SynchronizedMap
- SynchronizedSortedMap
- SynchronizedNavigableMap
- CheckedCollection
- CheckedSet
- CheckedNavigableSet
- CheckedList
- CheckedRandomAccessList
- CheckedMap
- CheckedEntrySet
- CheckedSortedMap
- CheckedNavigableMap
- EmptyIterator
- EmptyListIterator
- EmptyEnumeration
- EmptySet
- EmptyList
- EmptyMap
- Spliterator
- SingletonSet
- SingletonList
- SingletonMap
- CopiesList:调用
nCopies
方法返回一个包含充分 n 个元素的不可变列表 - ReverseComparator:调用
reverseOrder
方法返回一个逆序比较器,其compare
方法体中,两个形参位置顺序与一般的方法相反 - SetFromMap:将Map作为Set使用,忽略原来Map的值,所有操作都在键集合 keySet() 上
- AsLIFOQueue:将双端队列(Deque)作为后进先出(LIFO)队列使用
根据类的命名,可以分为以下类别
Unmodifiable(不可变)类Unmodifiable 类是用于创建不可更改的工具类。通过使用“包装器”(Wrapper)的方式,将一个已有的集合包装起来生成不可变的集合对象,该对象只支持读取操作,不支持添加、删除和修改集合中的元素。常用方法包括 unmodifiableList()、unmodifiableSet()、unmodifiableMap() 等(注意方法名开头字母为小写),用来返回对应的不可变类型。不可变类可以保护集合数据的不可变性,防止不应该更改的数据被修改,从而保证数据的安全性。
Synchronized(同步)类Synchronized 类是一个用于创建同步化的工具类。通过使用“包装器”(Wrapper)的方式,将一个已有的集合包装起来,从而创建一个线程安全的集合对象。这些集合使用同步化机制来确保在多线程环境下对集合的并发访问时,集合中的数据不会被损坏。要得到Synchronized 类的的对象,通过相应的 synchronizedList()、synchronizedSet()、synchronizedMap() 返回。所有方法的同步操作通过对类中的
mutex
对象加锁实现。Checked(检查)类Checked 类用于确保集合中只包含指定类型的元素,并在插入元素时进行检查。当元素类型不是指定类型时,将引发 ClassCastException 异常,从而发出警告。Checked 类用于增强程序的健壮性和安全,确保程序在运行时能够正确处理集合数据。通过相应的 checkedList()、checkedSet()、checkedMap() 等方法返回检查类。
Empty(空)类以 Empty 开头的类是一组不可变、空(没有元素)的实现类,提供了一种容易使用的、不可变的、空集合的对象。Empty类是单例模式,只存在一个实例,可以省去创建大量的空集合对象的开销。另外,使用空集合对象作为默认值,在避免空指针异常的同时,也提高了代码的可读性。
Singleton(单例)类Singleton 类用于创建值为单个元素的集合/列表/Map,其创建方式是通过 Collections.singletonXXX 方法实现的。该方法会返回一个只包含传入的单一对象或值的不可变对象。该对象生成后不能修改其内容,如果尝试添加或删除元素会导致 UnsupportedOperationException 异常。Singleton 可以代表一个单一的值或对象,并且充当一种方便提供对集合支持的方式。
(完)
关键词:
【快播报】Collections类源码初探
天天微资讯!2023油价调整窗口时间表一览
马斯克 一统海外充电江湖!
新增自动拍摄功能:尼康Z9获4.00版本固件更新
90后小伙中1000万大奖 淡定回应先去上个班:不着急领
看热讯:阵容强大!长城汽车17位高管集体入驻微博:吉利副总裁盛赞
史低价!小米米家无线洗地机2开启618预售:仅1799元-当前视点
视点:过山车行情后,建筑钢材市场行情或易涨难跌
今日精选:Koordinator 最佳实践系列:精细化 CPU 编排
天天观察:Android RIL&IMS源码分析
天天即时:5款超级好用的开发效率工具,建议收藏!
世界观点:记录--为什么推荐用svg而不用icon?
油价小幅下调 加一箱油将少花2元 全球最资讯
惠誉博华:48家银行未赎回二级资本债券,合计达364.8亿元
恒生指数收涨0.6% 恒生科技指数大涨重回4000点上方
中海达(300177)6月13日主力资金净买入525.51万元_天天通讯
PMR机械硬盘走到尽头了!西数/希捷正疯狂自救
6旬老人守株待兔式飞奔撞车碰瓷索赔 车主吓坏:监控还清白 环球精选
广东有多热?网友在广东买虾 还没到家就熟了 世界今日讯
美国再将31家中企列入“实体清单”!
2999元的国产显卡值不值得冲?实测3A大作给你答案
焦点信息:天津:“多卡合一”创新服务“城市小蜜蜂”
今日热文:线段树学习笔记
每日速看!尚医通-day10【微信扫码登录】(内附源码)
linux iptables安全技术与防火墙_快播报
收评:创业板指涨0.68%收获三连阳 半导体行业涨幅靠前
全球快报:小米卢伟冰:小米13 Ultra在意法西德及香港地区正式开售 销售超预期
首发预装鸿蒙OS 4.0!华为Mate60 Pro概念图出炉 全球热资讯
天天精选!NASA决定造访遍地黄金的“灵神星”:平均每位美国人能分300亿美元
美系硬派SUV福特探险者谍照曝光!外观内饰全面升级 预计将在年内首次亮相_今日热讯
今日热搜:8GB显卡卖到3199元 显存成本曝光:英伟达实在太赚了
视点!男生抠掉脸上痘痘流血近1小时:用了一包400张抽纸
每日报道:6月13日华鲁恒升尿素价格暂稳
焦点信息:市场监管总局:瞄准先进材料、人工智能等领域推动建立国家标准参考数据中心
烟台大学附属中学石明校区举行垃圾分类科普讲座|天天时快讯
速递!8GB内存笔记本卖到10499元起 苹果被批吃相难看:应该破发
货车高速上连续疯狂别车被撞停 官方:未造成伤亡、已找到肇事者|当前播报
天天热讯:马斯克相中的男人!14岁成SpaceX最年轻工程师、岗位年薪百万
环球即时看!小米平板6 Pro两个月使用心得:找不到短板的安卓板皇
Arm发布全新智能视觉参考设计 首次整合第三方IP核心
2023安洵杯 re复现
每天一道面试题:Spring的Bean生命周期
Axure RP教程_编程入门自学教程_菜鸟教程-免费教程分享_环球今日讯
环球今日报丨哥伦比亚4名空难获救儿童的母亲生前或遭家暴,孩子外公和父亲欲争夺抚养权
当前关注:你收益多少?余额宝上线第十年:每天为国人赚1亿零花钱 网友狂晒单
排队5小时!浙江网红面包黄牛加价上百元 网友吐槽:消协回应
【当前独家】中轴线文化遗产有了常设讲堂
三种方法让.NET轻松实现Excel转PDF
天天快看点丨docker-compose搭建wordpress
【播资讯】比亚迪执行副总裁:美国市场不在我们考虑范围内
石家庄迈入“刷脸”乘车时代:买一根火腿肠就能免费坐地铁活动结束了_环球动态
制作成本16.5亿!《封神三部曲》第一部7月20上映:角色海报公布 太强大 今日报
吹牛还是玩真的?丰田下一代电动汽车续航达1500公里
【天天报资讯】小米发布米家旅行箱:顶部嵌平设计 行走的小桌板
市场监管总局:到2035年 计量数据归集共享规模显著提升-快播
【技术积累】软件设计模式中的工厂模式【一】-独家
STM32F429 Discovery开发板应用:使用FreeRTOS队列+DMA双缓存实现串口数据接收
【寻味中华丨饮食】蔡甸藕带:白若玲珑玉 丝缕皆故乡
【天天时快讯】699元!XREAL Beam投屏盒子发布:随身携带的“可悬停AR空间屏”
AMD今晚发布新CPU Intel急了:至强性能比EPYC快7倍
【世界新视野】4-1战胜热火!掘金队夺队史首个NBA总冠军:网友发帖祝贺 约老师太强
小区门口连装8条减速带 物业回复让业主无语:为防业主逃费
贵1000元值不值?i7-13700H和i5-13500H对比实测 世界观点
我在塞尔维亚寻找约基奇-每日速递
全球微速讯:“铁榔头”郎平重返中学校园,为学弟学妹成长“支招”
世界最新:深度学习应用篇-推荐系统[11]:推荐系统的组成、场景转化指标(pv点击率,uv点击率,曝光点击率)、用户数据指标等评价指标详解
flutter 日志打印三種方法
最新:Linux根文件制作
热推荐:一对一直播源码平台搭建的关键条件,成败在此。
真刑!几行代码端了整个教务系统。。
启明星辰(002439)6月12日主力资金净卖出1310.11万元
长安欧尚Z6新能源半年降价3万多被集体投诉 车主:坑惨我们了
每日热讯!2折!115网盘618大促:10年VIP只要1000元 赠100TB空间
全脂/低脂可选:特仑苏纯牛奶2.7元/盒抄底(商超6元)
腾势N7赛道远超宝马X3 赵长江:意向客户看到展车后几乎全下单了
Fold5、Flip5换壳!三星W24系列折叠屏手机通过认证:25W快充
吴尚垠 吴尚_每日消息
JAVA非递归生成无限级菜单树的较简代码实现。(非泛用型工具包,仅总结逻辑)
每日关注!低代码开发平台为数智赋能,让开发变得更简单
奶我一口是什么意思网络用语_奶你一口是什么意思简介介绍
腾讯祭出的大招《无畏契约》 能不能成为下一个《英雄联盟》?-环球微速讯
环球观点:最大内存+最美拍照手机!小米Civi 3 1TB上市:2999元
当前消息!满级玩家有盼头了 暗黑世界V等你来
28.98万起 智己LS7都市版上市 CEO刘涛:现在买增程过几年就会焦虑 每日热点
男子洗澡被闯入的两匹“狼”吓坏 经辨认是阿拉斯加 焦点精选
C天键(301383)6月12日主力资金净买入2791.69万元 焦点快看
【当前独家】hvv面试常见框架漏洞
天天热头条丨ldquo 以至 rdquo ldquo 以致 rdquo ldquo 以至于 rdquo 与 ldquo 以致于 rdquo 的区别
蔚来降价3万!李斌:买的起2、30万车的人时间成本很高 时薪200元肯定是有的-世界播报
世界即时:仇恨拉满!日本核污水排放在即 韩国人正疯狂买盐:不敢吃海鲜了
三冠王巡游!曼城全队展示三座奖杯 哈兰德赤膊上阵 城迷疯狂庆祝
每日快报!暂停加息预期支撑多头 美债市场周初表现偏强
微资讯!英伟达市占率超83% 显卡降不降价我说了算!4060系列买到偷着乐?
希捷被重罚3亿美元后!消息称华为不缺硬盘、SSD了:西数持续供货中_每日资讯
十多年了 苹果新款Mac Pro依然不是中国制造:美泰联手组装
芬兰加入北约的军事协调工作结束 双方签署声明 速读
每日速读!读发布!设计与部署稳定的分布式系统(第2版)笔记01_生产环境的生存法则
大家超爱看黑美鱼?《小美人鱼》卖座成2023票房TOP10:国内外口碑两极分化
焦点简讯:漫威等大片国人不爱看了 不符合审美!郭帆:中国电影将弯道超车好莱坞
环球微速讯:香干怎么做比较好吃?