写点什么

Java 集合看这一篇就够了

  • 2022 年 5 月 15 日
  • 本文字数:2082 字

    阅读完需:约 7 分钟

就是单身狗放 Collection 里面,couple 就放 Map 里。(所以你属于哪里?


学习这些集合框架,我认为有 4 个目标:


明确每个接口和类的对应关系;


对每个接口和类,熟悉常用的 API;


对不同的场景,能够选择合适的数据结构并分析优缺点;


学习源码的设计,面试要会答啊。


[](()Collection




先来看最上层的 Collection.



Collection 里还定义了很多方法,这些方法也都会继承到各个子接口和实现类里,而这些 API 的使用也是日常工作和面试常见常考的,所以我们先来看下这些方法。


操作集合,无非就是「增删改查」四大类,也叫 CRUD:


Create, Read, Update, and Delete.


那我也把这些 API 分为这四大类:



下面具体来看:


增:


boolean add(E e);


add() 方法传入的数据类型必须是 Object,所以当写入基本数据类型的时候,会做自动装箱 auto-boxing 和自动拆箱 unboxing。


还有另外一个方法 addAll(),可以把另一个集合里的元素加到此集合中。


boolean addAll(Collection<? extends E> c);


删:


boolean remove(Object o);


remove()是删除的指定元素。


那和 addAll() 对应的,


自然就有 removeAll(),就是把集合 B 中的所有元素都删掉。


boolean removeAll(Collection<?> c);


改:


Collection Interface 里并没有直接改元素的操作,反正删和增就可以完成改了嘛!


查:


查下集合中有没有某个特定的元素:


boolean contains(Object o);


查集合 A 是否包含了集合 B:


boolean containsAll(Collection<?> c);


还有一些对集合整体的操作:


判断集合是否为空:


boolean isEmpty();


集合的大小:


int size();


把集合转成数组:


Object[] toArray();


以上就是 Collection 中常用的 API 了。


在接口里都定义好了,子类不要也得要。


当然子类也会做一些自己的实现,这样就有了不同的数据结构。


那我们一个个来看。


[](()List





List 最大的特点就是:有序,可重复。


看官网说的:


An ordered collection (also known as a sequence).


Unlike sets, lists typically allow duplicate elements.


这一下把 Set 的特点也说出来了,和 List 完全相反,Set 是 无序,不重复的。


List 的实现方式有 LinkedList 和 ArrayList 两种,那面试时最常问的就是这两个数据结构如何选择。


对于这类选择问题:


一是考虑数据结构是否能完成需要的功能;


如果都能完成,二是考虑哪种更高效。


(万事都是如此啊。)


那具体来看这两个 classes 的 API 和它们的时间复杂度:



稍微解释几个:


add(E e) 是在尾巴上加元素,虽然 ArrayList 可能会有扩容的情况出现,但是均摊复杂度(amortized time complexity)还是 O(1) 的。


add(int index, E e)是在特定的位置上加元素,LinkedList 需要先找到这个位置,再加上这个元素,虽然单纯的「加」这个动作是 O(1) 的,但是要找到这个位置还是 O(n) 的。(这个有的人就认为是 O(1),和面试官解释清楚就行了,拒绝扛精。


remove(int index)是 remove 这个 index 上的元素,所以


  • ArrayList 找到这个元素的过程是 O(1),但是 remove 之后,后续元素都要往前移动一位,所以均摊复杂度是 O(n);

  • LinkedList 也是要先找到这个 index,这个过程是 O(n) 的,所以整体也是 O(n)。


remove(E e)是 remove 见到的第一个这个元素,那么


  • ArrayList 要先找到这个元素,这个过程是 O(n),然后移除后还要往前移一位,这个更是 O(n),总的还是 O(n);

  • LinkedList 也是要先找,这个过程是 O(n),然后移走,这个过程是 O(1),总的是 O(n).


那造成时间复杂度的区别的原因是什么呢?


答:


  • 因为 ArrayList 是用数组来实现的。

  • 而数组和链表的最大区别就是数组是可以随机访问的(random access)


这个特点造成了在数组里可以通过下标用 O(1) 的时间拿到任何位置的数 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 ,而链表则做不到,只能从头开始逐个遍历。


也就是说在「改查」这两个功能上,因为数组能够随机访问,所以 ArrayList 的效率高。


那「增删」呢?


如果不考虑找到这个元素的时间,


数组因为物理上的连续性,当要增删元素时,在尾部还好,但是其他地方就会导致后续元素都要移动,所以效率较低;而链表则可以轻松的断开和下一个元素的连接,直接插入新元素或者移除旧元素。


但是呢,实际上你不能不考虑找到元素的时间啊。。。而且如果是在尾部操作,数据量大时 ArrayList 会更快的。


所以说:


1.改查选择 ArrayList;


2.增删在尾部的选择 ArrayList;


3.其他情况下,如果时间复杂度一样,推荐选择 ArrayList,因为 overhead 更小,或者说内存使用更有效率。


[](()Vector




那作为 List 的最后一个知识点,我们来聊一下 Vector。这也是一个年龄暴露帖,用过的都是大佬。


那 Vector 和 ArrayList 一样,也是继承自 java.util.AbstractList,底层也是用数组来实现的。


但是现在已经被弃用了,因为…它加了太多的 synchronized!


任何好处都是有代价的,线程安全的成本就是效率低,在某些系统里很容易成为瓶颈,所以现在大家不再在数据结构的层面加 synchronized,而是把这个任务转移给我们程序员==


那么面试常问题:Vector 和 ArrayList 的区别是什么,只答出来这个还还不太全面。


来看 stack overflow 上的高票回答:

用户头像

还未添加个人签名 2022.04.13 加入

还未添加个人简介

评论

发布
暂无评论
Java 集合看这一篇就够了_程序员_爱好编程进阶_InfoQ写作社区