Java基础丨集合类

首页 / 默认分类 / 正文

前言

在 Java 中数组的长度是不可修改的。然而在实际应用的很多情况下,无法确定数据数量。这些数据不适合使用数组来保存,这时候就需要使用集合。Java 的集合就像一个容器,用来存储 Java 类的对象,这个容器里只能放对象,对于基本类型(int, long, float, double等),需要将其包装成对象类型后(Integer, Long, Float, Double等)才能放到容器里。很多时候拆包装和解包装能够自动完成。
在集合中经常会用到泛型来使集合更加安全。

Java 集合框架如下所示:
Java集合

分类

Java 集合主要是由两大接口 (Interface) 派生出来的:Collection 和 Map。
这两大接口的不同之处在于:Collection 存放单一元素;Map 存放 key-value 键值对。

Collection 接口

Collection 接口是 List、Set 和 Queue 接口的父接口,通常情况下不被直接使用。
Collection 接口定义了很多方法,这些方法也都会继承到各个子接口和实现类里。

Collection 接口中常用的方法,如下表所示:

序号方法名称说明
1boolean add(E e);传入的数据类型必须是 Object,当写入基本数据类型的时候,会做自动装箱和自动拆箱。
2boolean addAll(Collection<? extends E> c);可以把另一个集合 c 里的所有元素加到集合中。
3boolean remove(Object o);从集合中删除一个指定元素,当集合中包含了一个或多个元素 o 时,该方法只删除第一个符合条件的元素,该方法将返回 true。
4boolean removeAll(Collection<?> c);从集合中删除所有在集合 c 中出现的元素。
5boolean contains(Object o);判断集合中是否存在指定的元素。
6boolean containsAll(Collection c);判断集合中是否包含集合 c 中的所有元素。
7boolean isEmpty();判断集合是否为空。
8int size();返回集合中元素的个数。
9Object[] toArray();把集合转换为一个数组,所有的集合元素变成对应的数组元素。
10Iteratoriterator();返回一个 Iterator 对象,用于遍历集合中的元素。

List 接口

List 是一个有序可重复的集合,集合中每个元素都有其对应的顺序索引,第一个元素的索引值是 0。List 的实现类有 ArrayList、LinkedList、Vector、Stack。
List 实现了 Collection 接口,常用的实现类有:ArrayList 类和 LinkedList 类。

  • ArrayList:基于动态数组实现,支持随机访问。
  • Vector:和 ArrayList 类似,但它是线程安全的。
  • LinkedList:基于双向链表实现,只能顺序访问,但是可以快速地在链表中间插入和删除元素,还可以用作栈、队列和双向队列。
功能方法ArrayListLinkedList
add(E e)O(1)O(1)
add(int index, E e)O(n)O(n)
remove(int index)O(n)O(n)
remove(E e)O(n)O(n)
set(int index, E e)O(1)O(n)
get(int index)O(1)O(n)

小结:

  • 改查选择 ArrayList;
  • 增删在尾部的选择 ArrayList;
  • 其他情况下,如果时间复杂度一样,推荐选择 ArrayList,因为 overhead 更小,或者说内存使用更有效率。

Vector 是 JDK1.0 中给出的类,和 ArrayList 一样,也是继承自 java.util.AbstractList,底层也是用数组来实现的。但是现在已经不推荐使用了,因为线程安全造成效率低,现在大家也不在数据结构的层面加 synchronized;其次是扩容时的区别:Vector 空间满了之后,扩容是一倍,而 ArrayList 仅仅是一半,也就是说扩容后的 Vector 是原来的 2 倍,ArrayList 是原来的 1.5 倍。Vector 分配内存的时候需要连续的存储空间,如果数据太多,容易分配内存失败。

Queue 接口

Queue 接口继承自 Collection 接口,除了最基本的 Collection 的方法之外,它还支持额外的插入、获取和检查操作。
有两组格式,共 6 个方法,一组是抛出异常的实现;另外一组是返回值的实现(没有则返回 null)。

其中有一种特殊的队列叫做 PriorityQueue,即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的。这里牵涉到了大小关系,元素大小的评判可以通过元素本身的自然顺序(natural ordering),也可以通过构造时传入的比较器。

抛异常返回值说明
add(e)offer(e)都是向优先队列中插入元素,只是Queue接口规定二者对插入失败时的处理不同,前者在插入失败时抛出异常,后则则会返回false
remove()poll()都是获取并删除队首元素,区别是当方法失败时前者抛出异常,后者返回null
element()peek()都是获取但不删除队首元素,也就是队列中权值最小的那个元素,二者唯一的区别是当方法失败时前者抛出异常,后者返回null

小结:

  • 首先,要用就用同一组 API,前后要统一;
  • 其次,根据需求。如果你需要它抛异常,那就是用抛异常的;不过做算法题时基本不用,所以选那组返回特殊值的就好了。

Deque 接口

Deque 接口继承自 Queue接口,除了支持 Queue 的方法之外,还有自己的方法。由于 Deque 是双向的,所以可以对队列的头和尾都进行操作,它同时也支持两组格式,一组是抛出异常的实现;另外一组是返回值的实现(没有则返回null)。

功能抛异常返回值
插入addFirst(e) / addLast(e)offerFirst(e) / offerLast(e)
移除removeFirst() / removeLast()pollFirst() / pollLast()
检查getFirst() / getLast()peekFirst() / peekLast()

小结:

  • 前后要统一,要么全部使用前一组,要么全部使用后一组;
  • Queue 和 Deque 的这些 API 都是 O(1) 的时间复杂度,准确来说是均摊时间复杂度。
  • 如果想实现「先进先出」的普通队列,就使用 LinkedList 或者 ArrayDeque 来实现,但更推荐使用 ArrayDeque,因为效率高,而 LinkedList 还会有其他的额外开销(overhead);
  • 如果想实现「优先队列」,就使用 PriorityQueue;
  • 如果想实现「栈」,就使用 ArrayDeque。

Stack

虽然 Java 中有 Stack 这个类,但是根据官方文档,已经不推荐使用了,因为 Vector 都已经过时被弃用了,而 Stack 是继承 Vector 的。
所以,想实现「栈」,就使用 ArrayDeque。例如:Deque<Integer> stack = new ArrayDeque<Integer>();

Set 接口

与 List 恰好相反,Set 是无序不重复的集合,它最多只允许包含一个 null 元素。
它主要有三个常用的实现类:散列集 HashSet、链式散列集 LinkedHashSet 和树形集 TreeSet。

  • HashSet: 采用 HashMap 的 key 来储存元素,主要特点是无序的,基本操作都是 O(1) 的时间复杂度,很快。
  • LinkedHashSet: 继承自 HashSet,其底层是基于 LinkedHashMap 来实现的,有序,非同步。特点就是既拥有了 O(1) 的时间复杂度,又能够保留插入的顺序,也就是说,当遍历该集合时候,LinkedHashSet 将会以元素的添加顺序访问集合的元素。
  • TreeSet: 采用红黑树结构,特点是可以有序,可以用自然排序或者自定义比较器来排序,其中自然排序为默认的排序方式;缺点就是查询速度没有 HashSet 快。

那每个 Set 的底层实现其实就是对应的 Map:
数值放在 map 中的 key 上,value 上放了个 PRESENT,是一个静态的 Object,相当于 place holder,每个 key 都指向这个 object。

Map 接口

Map 是一个映射接口,即 key-value 键值对。

HashMap

HashSet 和 HashMap 二者在 Java 里有着相同的实现,前者仅仅是对后者做了一层包装,也就是说 HashSet 里面有一个HashMap(适配器模式)。
HashMap实现了 Map 接口,即允许放入 key 为 null 的元素,也允许插入 value 为 null 的元素;除该类未实现同步外,其余跟 Hashtable 大致相同;跟 TreeMap 不同,该容器不保证元素顺序。
根据对冲突的处理方式不同,哈希表有两种实现方式,一种开放地址方式,另一种是冲突链表方式。
在 Java8 中,当链表中的元素达到了 8 个时,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

LinkedHashMap

LinkedHashSet 和 LinkedHashMap 在 Java 里也有着相同的实现,前者仅仅是对后者做了一层包装,也就是说 LinkedHashSet里面有一个 LinkedHashMap (适配器模式)。
从名字上可以看出该容器是 linkedList 和 HashMap 的混合体,也就是说它同时满足 HashMap 和 linkedList 的某些特性。可将 LinkedHashMap 看作采用 linkedList 增强的 HashMap。事实上 LinkedHashMap 是 HashMap 的直接子类,二者唯一的区别是 LinkedHashMap 在 HashMap 的基础上,采用双向链表(doubly-linked list)的形式将所有 entry 连接起来,这样是为保证元素的迭代顺序跟插入顺序相同。
将对象放入到 LinkedHashMap 或 LinkedHashSet 中时,有两个方法需要特别关心: hashCode()和 equals()。hashCode()方法决定了对象会被放到哪个 bucket 里,当多个对象的哈希值冲突时,equals()方法决定了这些对象是否是“同一个对象”。所以,如果要将自定义的对象放入到 LinkedHashMap 或 LinkedHashSet中,需要 @Override hashCode()和 equals()方法。

TreeMap

TreeMap 是一个有序的 key-value 集合,非同步,基于红黑树(Red-Black tree)实现,每一个 key-value 节点作为红黑树的一个节点。
TreeMap 实现了 SortedMap 接口,也就是说会按照 key的大小顺序对Map中的元素进行排序,其中排序方式也是分为两种,一种是自然排序,一种是定制排序,具体取决于使用的构造方法。

Iterator 接口

Iterator(迭代器)是一个接口,它是集合的迭代器。Collection 和 Map 系列集合主要用于盛装其他对象,而 Iterator 则主要用于遍历(即迭代访问)Collection 集合中的元素。

方法名说明
boolean hasNext()判断集合里是否存在下一个元素。如果有,hasNext() 方法返回 true。
E next()返回集合里下一个元素,如果没有就抛出NoSuchElementException异常。
default void remove()删除集合里上一次 next 方法返回的元素。
default void forEachRemaining(Consumer<? super E> action)Java 8 为 Iterator 新增的默认方法,该方法可使用 Lambda 表达式来遍历集合元素。

ListIterator 接口

ListIterator 是一个功能更加强大的迭代器, 它继承于 Iterator 接口,只能用于对各种 List 类型的访问。

参考

CSDN
官方文档
Java 全栈知识体系
Java专栏
打赏
评论区
头像
文章目录