重新认识Java——容器体系(Collection)

Java中的容器在开发过程必然会接触到的,也是作为一名合格的Java程序员必须要掌握的内容。各种面试、笔试中十有八九都会在容器上面做“文章”。由于每一类容器涉及的知识点都比较多,基于单一职责原则,本文并不会对特定容器做特别深入地介绍。文章在宏观层面上来研究一下Java中的容器体系,并比较各种容器之前的联系与区别,主要内容如下:

  1. Java容器的体系结构
  2. Collection体系
  3. Map体系

容器的体系结构

Java中的容器主要有Collection和Map,它们都是顶层接口,都位于java.util包下,实际使用地容器都是基于这两个接口延伸出来的。下面来看看在实际开发过程中使用的主要类的类图(基于JDK1.8),并简单地介绍它们的功能。

下面是Collection接口的类图:

Collection Structure

  1. List:是一种已知顺序的有序数据集,可容纳重复的元素。
  2. Set:是一种数学意义上的集合,最大的特点是不可容纳重复元素。
  3. Queue:即队列,与经典数据结构的队列一致。

下面是Map接口的类图:

Map Structure

  1. HashMap:即哈希表,与经典数据结构中哈希表一致,主要用于快速查找。
  2. HashTable:与HashMap功能基本一致,不过是线程安全的。
  3. SortedMap:经过排序的Map。
  4. ConcurrentMap:并发Map,主要用于多线程并发环境下。

Collection

Collection实现了Iterable(迭代器)接口,意味着其子类都可以利用迭代器模式来访问其中的元素。所以,我们可以用for…each…方式要顺序读取Collection中的元素,类似下面的代码:

1
2
3
4
5
6
7
public static void main(String[] args) {
Collection<String> c = new ArrayList<String>();
c.add("1");
for (String s : c) {
System.out.println(s);
}
}

这种写法实际上不属于Java的原生语法,而是一种语法糖。它最终编译后的字节码主体部分为:

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
public static void main(java.lang.String[]);
descriptor: ([Ljava/lang/String;)V
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=4, args_size=1
0: new #16 // class java/util/ArrayList
3: dup
4: invokespecial #18 // Method java/util/ArrayList."<init>":()V
7: astore_1
8: aload_1
9: ldc #19 // String 1
11: invokeinterface #21, 2 // InterfaceMethod java/util/Collection.add:(Ljava/lang/Object;)Z
16: pop
17: aload_1
18: invokeinterface #27, 1 // InterfaceMethod java/util/Collection.iterator:()Ljava/util/Iterator;
23: astore_3
24: goto 44
27: aload_3
28: invokeinterface #31, 1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
33: checkcast #37 // class java/lang/String
36: astore_2
37: getstatic #39 // Field java/lang/System.out:Ljava/io/PrintStream;
40: aload_2
41: invokevirtual #45 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
44: aload_3
45: invokeinterface #51, 1 // InterfaceMethod java/util/Iterator.hasNext:()Z
50: ifne 27
53: return

看上面字节码中的第15行,它调用了Iterator接口中定义的iterator()方法来获取一个Iterator的实例。然后分别用next()hasNext()来进行循环来读取Collection中保存的元素,这是Java中迭代器的典型用法。

所有实现Collection接口的类都必须提供两个标准的 构造函数:

  1. 无参数的构造函数用于创建一个空的Collection。
  2. 有一个Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。

List

List是一类顺序已知的数据集,元素存放的逻辑顺序完全由调用者控制,并且可以存放重复元素(equals比较后返回true的元素)和null元素。调用者能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。

List除了可以利用iterator()返回一个Iterator示例外,还定义了listIterator()方法来返回一个ListIterator实例。ListIterator接口继承了Iterator接口,它定义删除、添加和向前索引元素等方法。

List接口的主要子(孙)类有:ArryListLinkedListVector,他们主要的区别如下表:

List 线程安全性 扩容时是否需要复制 是否可以指定初始容量
ArrayList 非线程安全
LinkedList 非线程安全
Vector 线程安全

Vector已经很少被用到了,下面仅比较ArryListLinkedList的各种操作效率,然后介绍其使用场景。

List add get remove 占用空间 内存空间是否连续
ArrayList 时间复杂度:O(n) 时间复杂度:O(1) 时间复杂度:O(n) 元素占用空间和 连续
LinkedList 时间复杂度:O(1) 时间复杂度:O(n) 时间复杂度:O(n) 元素占用空间和+指针空间 可以不连续

从上面可以看出,ArryListLinkedList各自有其优势和劣势,他们的使用场景可以总结为:

  • 如果待容纳的元素总量确定,则优先使用ArryList
  • 如果读操作大于写操作,则使用ArryList;反之,则使用LinkedList

Set

Set表示数学意义上的集合,它不允许重复的元素,即任意的两个元素e1和e2都有e1.equals(e2)falseSet最多允许一个null元素,Set的构造函数有一个约束条件,传入的Collection实例不能包含重复的元素。实际使用较多的子类有:HashSetTreeSet

Set的实现类基本上都是基于Map来实现的,它巧妙地利用了Map中的key不会重复的特性。HashSet是基于HashMap实现的,而TreeSet默认是基于TreeSet实现的。它们的区别如下:

Set 元素有序性 是否支持排序
HashSet 无序 不支持排序
TreeSet 有序 支持排序

如果无需保证取出的元素序列与插入的元素序列顺序完全一致,则使用HashSet;反之,则应该使用TreeSet

Queue

队列是一种先进先出的数据结构.它有两个基本操作:在队列尾部加人一个元素,从队列头部移除一个元素。由于笔者在实际开发过程极少会用到这种数据结构,或者会使用额外的消息队列来替代,所以暂时将这部分内容先放一放。LinkedBlockingQueueArrayBlockingQueue等阻塞式队列广泛用于Java并发库中,在学习j.u.c包时再深入地研究。

Map体系

Map是一种把键和值进行映射的集合,其中的每个元素都是Map.Entry实例。Map的主要功能是通过键(key)快速查找出值(value)。主要有两种方法对Map进行遍历:

第一种,先获取entrySet,然后利用迭代器遍历这个对象。

1
2
3
4
5
6
7
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}

第二种,先获取Map的迭代器,每次取出一个key,然后查找每个key所对应的value。

1
2
3
4
5
6
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}

很显然,第一种遍历方式效率更高,推荐使用。

Map的子类非常多,使用频率较高的是下面4个:

  • HashMap:最接近数据结构中的哈希表的实现,采用拉链法解决key冲突。前面的HashSet即使基于这个类来实现的。
  • HashTable:线程安全版的HashMap。
  • LinkedHashMap:HashMap的子类,利用链表解决HashMap中遍历时,输出的元素顺序与插入顺序不一致的问题。
  • TreeMap:与TreeSet的特点类似,可以对key进行排序。

Map是Java中的非常重要的数据结构,上面的几种实现各有侧重,通过下面的表格来看看它们各自的特点:

Map 线程安全 达到容量上限时内存拷贝 是否允许null key 遍历顺序 是否可排序
HashMap 需要 无序
HashTable 需要 无序
LinkedHashMap 需要 与输入顺序一致
TreeMap 不需要 与输入顺序一致

在这4个类中,HashMapTreeMap2中场景,下面介绍不同场景下该使用哪种Map。

  • HashMap:插入、删除和定位元素的平均时间复杂度为O(N),是一个常数时间。如果没有排序需求,则应该优先使用HashMap
  • Treemap:插入、删除和定位元素的平均时间复杂度为O(log(n))适用于按自然顺序或自定义顺序遍历键(key)。

总结

本文简单地介绍了Java中的主要容器体系,内容非常浅。深入了解Java各个容器的内部原理和实现方式是Java程序员进阶的必经之路。在今后的学习中,笔者会研读这些容器类的源代码,并将学习笔记发布上来。


本文由xialei原创,转载请说明出处http://hinylover.space/2016/07/23/relearn-java-collection/