Java集合(一) 概述

Java集合(一) 概述

第一节 前文

集合是Java开发中比较重要的一部分,相对应的就是大学时计算机专业最重要的课程之一——数据结构,我已经在前几篇博客中《算法复习 (一) 排序》等整理了其中一部分(数据结构和算法的整理比较耗时,我当前只能抽出比较碎片的时间来打理博客,所以无奈先停下了这个部分,希望可以尽快抽时间把这部分补上)。

相较于数据结构相关博客,这几篇博客仅专注于回顾和介绍怎么使用Java中的集合类,以及其特点和使用场景,实现原理等。

Java集合类都是接口与实现分离的设计


第二节 集合框架的层次接口

集合框架的接口

集合的两个基本接口是:Collection和Map

List 是一个有序集合,数组支持的有序集合可以快速的随机访问,链表实现的有序集合的随机访问很慢,最好使用迭代器,所以只为他们提供一个接口不是一个好的设计。

可以通过两种方式来访问元素:

  • 迭代器访问/整数索引访问
  • 随机访问

ListIterator 定义了 add() 方法用来在迭代器的位置前面插入一个元素

Set 接口等同于有更严格限制的Collection,两个接口具有相同的方法签名,比如add()方法要求不能增加已有的元素,其equals方法只要判断两集包含同样的元素就可,对顺序则没有要求。hashcode方法要求保证包含相同元素的两集会得到相同的散列码。

Queue 队列接口

RandomAccess接口用来标记集合是否支持高效的随机访问,可以避免对链表进行随机访问操作。

如ArrayList和LinkedList。

1
2
3
4
5
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

SortedSetSortedMap提供了用来排序的比较器对象

NavigableSetNavigableMap提供了用于搜索和遍历有序集和映射的方法,TreeSet和TreeMap类实现了这些接口。


第三节 接口源码

3.1 Collection

集合类的基本接口是 Collection 接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public interface Collection<E> extends Iterable<E> {
// Query Operations
int size();//集合元素个数

boolean isEmpty();//集合是否为空

boolean contains(Object o);//是否包含和元素相等的对象

Iterator<E> iterator();//迭代器

Object[] toArray();//转换为Object数组

<T> T[] toArray(T[] a);//转换为泛型数组

// Modification Operations

boolean add(E e);//添加元素

boolean remove(Object o);//移除元素


// Bulk Operations

boolean containsAll(Collection<?> c);//判断集合是否

boolean addAll(Collection<? extends E> c);//从集合添加所有元素

boolean removeAll(Collection<?> c);//删除集合所包含所有元素

default boolean removeIf(Predicate<? super E> filter) {//根据过滤条件移除
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}

boolean retainAll(Collection<?> c);//从集合钟删除所有和参数集合元素不同的元素,也就是求差集,若有操作执行成功返回true

void clear();//清除所有元素


// Comparison and hashing

boolean equals(Object o);//等值判断

int hashCode();//哈希值

@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}

default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}

default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}

3.2 Iterable

集合类都实现了 Iterable 接口,所以所有集合类都是可迭代的,都可以通过 foreach 遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public interface Iterable<T> {
Iterator<T> iterator();

default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}

default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}

3.3 Iterator

迭代器 Iterator 如下,可以像游标一样通过反复调用 next() 逐个访问集合中的每个元素,若到达末尾继续调用会抛出 NoSuchElementException 异常,所以在使用时都会调用 hasNext() 判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Iterator<E> {
boolean hasNext();

E next();

default void remove() {//迭代器删除元素前需要调用next()
throw new UnsupportedOperationException("remove");
}

default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}

简单示例:

1
2
3
4
5
6
7
8
9
10
11
12
//使用举例
Collection<String> c = ...;
Iterator<String> i = c.iterator();
while(i.hasNext()){
String s = i.next();
...
}

//foreach遍历
for(String s : c){
...
}

迭代器相关内容可以参考这篇博客《迭代器

foreach相关内容可以参考这篇博客《foreach循环和for循环

在了解了Lambda表达式后甚至可以更简洁的遍历,可以参考《Lambda表达式

1
iterator.forEachRemaining(element -> ...);

迭代器访问元素的顺序取决于集合的类型,如ArrayList进行迭代时,从索引0开始,每次索引值加1;若访问HashSet则按随机的次序访问元素。

相比于C++对于迭代器的设计,Java的迭代器可以理解为游标一直指向两个元素之间,调用 next() 就越过下个元素并返回其引用,Java的迭代器无法获取指定元素的引用。迭代器要求在每次调用 remove() 前一定要先调用 next() 检查此元素,否则会抛出 IllegalStateException 异常。

Collection接口声明了很多有用的方法,所以集合类都必须实现这些方法,为了更方便实现者来实现Collection接口,Java类库提供了AbstractCollection,抽象化了size和iterator等,但实现了一些基础方法,集合类可以继承AbstractCollection,由集合类实现iterator,由AbstractCollection实现contains()等基础方法,当然也可以都由集合类来实现,这些都可以灵活使用(JDK8之后在Collection接口添加了很多默认方法)。

迭代器为了保证数据安全,当一个迭代器运行中发现此集合被另一个迭代器或集合本身修改了,就抛出ConcurrentModificationException异常。所以为了避免异常发生可以考虑只给一个迭代器修改数据的权限,其它则只能读取。或者参考并发设计的CAS,为迭代器维护一个计数值,每次改写后比较自己的计数值和集合的计数值是否一致,不一致则抛出异常。

更多ListIterator相关可以看Java集合(三) List

3.4 RandomAccess

RandomAccessList 实现所使用的标记接口,用来表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。

标记接口(Marker):这就说明了 RandomAccess 为空的原因,这个接口的功能仅仅起到标记的作用。

类似的还有序列化接口 Serializable 和可克隆接口 Cloneable

  • Serializable 接口: 类通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。
  • Cloneable 接口 :实现了 Cloneable 接口,以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制。 如果在没有实现 Cloneable 接口的实例上调用 Objectclone 方法,则会导致抛出 CloneNotSupportedException 异常。

接口代码如下:

1
2
public interface RandomAccess {
}

如果 List 子类实现了 RandomAccess 接口,那表示它能快速随机访问存储的元素, 这时候你想到的可能是数组, 通过下标 index 访问, 实现了该接口的 ArrayList 底层实现就是数组, 同样是通过下标访问, 只是我们需要用 get() 方法的形式 , ArrayList 底层仍然是数组的访问形式。

同时你应该想到链表, LinkedList 底层实现是链表, LinkedList 没有实现 RandomAccess 接口,发现这一点就是突破问题的关键点。

数组支持随机访问, 查询速度快, 增删元素慢; 链表支持顺序访问, 查询速度慢, 增删元素快。所以对应的 ArrayList 查询速度快,LinkedList 查询速度慢, RandomAccess 这个标记接口就是标记能够随机访问元素的集合, 简单来说就是底层是数组实现的集合。

为了提升性能,在遍历集合前,我们便可以通过 instanceof 做判断, 选择合适的集合遍历方式,当数据量很大时, 就能大大提升性能。随机访问列表使用循环遍历,顺序访问列表使用迭代器遍历


第四节 集合框架的集合类

集合框架的集合类

集合类型 描述 博客地址
ArrayList 可以动态增长和缩减的索引序列 Java集合(三) List
LinkedList 可以在任何位置进行高效的插入和删除操作的有序序列 Java集合(三) List
ArrayQueue 用循环数组实现的双端队列 Java集合(二) Queue和Deque
PriorityQueue 允许高效删除最小元素的集合 Java集合(二) Queue和Deque
HashSet 没有重复元素的无序集合 Java集合(四) Set
TreeSet 有序集 Java集合(四) Set
EnumSet 包含枚举类型的集 Java集合(四) Set
LinkedHashSet 可以记住元素插入次序的集合 Java集合(四) Set
HashMap 存储键/值关联的数据结构 Java集合(五) Map
TreeMap 键值有序排列的映射表 Java集合(五) Map
EnumMap 键值属于枚举类型的映射表 Java集合(五) Map
LinkedHashMap 可以记住键/值项添加次序的映射表 Java集合(五) Map
WeakHashMap 当值没有用处时可以被垃圾回收期回收的映射表 Java集合(五) Map
IdentityHashMap 用==而不是equals比较键值的映射表 Java集合(五) Map

参考博客和文章书籍等:

《Java核心技术 卷Ⅰ》

RandomAccess 这个空架子有何用?

因博客主等未标明不可引用,若部分内容涉及侵权请及时告知,我会尽快修改和删除相关内容