概述
Java提供了几个能有效地组织和操作数据的数据结构,这些数据结构通常称为Java集合框架。
Java集合框架主要包括两种类型的容器,一种是集合(Collection),存储一个元素集合,另一种是图(Map),存储键/值对映射。
Collection接口又有3种子类型,List、Set和Queue,再下面是一些抽象类,最后是具体实现类,常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。
Collection接口
Collection接口是处理对象集合的根接口,其中定义了很多对元素进行操作的方法,AbstractCollection是提供Collection部分实现的抽象类。
List接口
List接口扩展自Collection,==它可以定义一个允许重复的有序集合==,从List接口中的方法来看,List接口主要是增加了面向位置的操作,允许在指定位置上操作元素,同时增加了一个能够双向遍历线性表的新列表迭代器ListIterator。AbstractList类提供了List接口的部分实现,AbstractSequentialList扩展自AbstractList,主要是提供对链表的支持。
ArrayList
ArrayList的源码,我们可以很清楚地看到里面的逻辑,它是用数组存储元素的,这个数组可以动态创建,如果元素个数超过了数组的容量,那么就创建一个更大的新数组,并将当前数组中的所有元素都复制到新数组中。
LinkedList
LinkedList的源文件,不难看到LinkedList是在一个链表中存储元素。所以,LinkedList的元素添加和删除其实就对应着链表节点的添加和移除。
set接口
Set接口扩展自Collection,==它与List的不同之处在于,规定Set的实例不包含重复的元素。==AbstractSet是一个实现Set接口的抽象类,Set接口有三个具体实现类,分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。
HashSet
散列集HashSet是一个用于实现Set接口的具体类,可以使用它的无参构造方法来创建空的散列集,也可以由一个现有的集合创建散列集。
查看散列集HashSet的源码实现可以看到它内部是使用一个HashMap来存放元素的,因为HashSet的元素就是其内部HashMap的键集合,所以HashSet可以做到元素不重复。
LinkedHashSet
LinkedHashSet是继承自HashSet的,支持对规则集内的元素排序。HashSet中的元素是没有被排序的,而LinkedHashSet中的元素可以按照它们插入规则集的顺序提取。
TreeSet
TreeSet扩展自AbstractSet,并实现了NavigableSet,AbstractSet扩展自AbstractCollection,树形集是一个有序的Set,其底层是一颗树,这样就能从Set里面提取一个有序序列了。在实例化TreeSet时,我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序。树形集中提供了很多便捷的方法。
Queue
队列是一种先进先出的数据结构,元素在队列末尾添加,在队列头部删除。Queue接口扩展自Collection,并提供插入、提取、检验等操作。
上图中,方法offer表示向队列添加一个元素,poll()与remove()方法都是移除队列头部的元素,两者的区别在于如果队列为空,那么poll()返回的是null,而remove()会抛出一个异常。方法element()与peek()主要是获取头部元素,不删除。
接口Deque,是一个扩展自Queue的双端队列,它支持在两端插入和删除元素,因为LinkedList类实现了Deque接口,所以通常我们可以使用LinkedList来创建一个队列。PriorityQueue类实现了一个优先队列,优先队列中元素被赋予优先级,拥有高优先级的先被删除。
Map接口
Map,图,是一种存储键值对映射的容器类,在Map中键可以是任意类型的对象,但不能有重复的键,每个键都对应一个值,真正存储在图中的是键值构成的条目。
Map接口常用的有三个具体实现类,分别是HashMap、LinkedHashMap、TreeMap。
在实际使用中,如果更新图时不需要保持图中元素的顺序,就使用HashMap,如果需要保持图中元素的插入顺序或者访问顺序,就使用LinkedHashMap,如果需要使图按照键值排序,就使用TreeMap。
HashMap
HashMap是基于哈希表的Map接口的非同步实现,继承自AbstractMap,AbstractMap是部分实现Map接口的抽象类。在平时的开发中,HashMap的使用还是比较多的。
HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当链表中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,HashMap采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。
==HashMap的实现原理:==首先有一个每个元素都是链表(可能表述不准确)的数组,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。
LinkedHashMap
LinkedHashMap继承自HashMap,它主要是用链表实现来扩展HashMap类,HashMap中条目是没有顺序的,但是在LinkedHashMap中元素既可以按照它们插入图的顺序排序,也可以按它们最后一次被访问的顺序排序。
TreeMap
TreeMap基于红黑树数据结构的实现,键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap,同时实现了接口NavigableMap,而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口,使用它可以确保图中的条目是排好序的。
其它集合类
特殊的集合类,Vector、Stack、HashTable、ConcurrentHashMap以及CopyOnWriteArrayList
Vector
用法上,Vector与ArrayList基本一致,不同之处在于Vector使用了关键字synchronized将访问和修改向量的方法都变成同步的了,所以对于不需要同步的应用程序来说,类ArrayList比类Vector更高效。
Stack
Stack,栈类,是Java2之前引入的,继承自类Vector。
Hashtable
Hashtable和前面介绍的HashMap很类似,它也是一个散列表,存储的内容是键值对映射,不同之处在于,Hashtable是继承自Dictionary的,Hashtable中的函数都是同步的,这意味着它也是线程安全的,另外,Hashtable中key和value都不可以为null。
上面的三个集合类都是在Java2之前推出的容器类,可以看到,尽管在使用中效率比较低,但是它们都是线程安全的。下面介绍两个特殊的集合类。
ConcurrentHashMap
Concurrent并发,从名字就可以看出来ConcurrentHashMap是HashMap的线程安全版。同HashMap相比,ConcurrentHashMap不仅保证了访问的线程安全性,而且在效率上与HashTable相比,也有较大的提高。
CopyOnWriteArrayList
CopyOnWriteArrayList,是一个线程安全的List接口的实现,它使用了ReentrantLock锁来保证在并发情况下提供高性能的并发读取。
总结
Java集合框架主要包括Collection和Map两种类型。其中Collection又有3种子类型,分别是List、Set、Queue。Map中存储的主要是键值对映射。
规则集Set中存储的是不重复的元素,线性表中存储可以包括重复的元素,Queue队列描述的是先进先出的数据结构,可以用LinkedList来实现队列。
效率上,规则集比线性表更高效。
ArrayList主要是用数组来存储元素,LinkedList主要是用链表来存储元素,HashMap的底层实现主要是借助数组+链表+红黑树来实现。
Vector、Hashtable等集合类效率比较低但都是线程安全的。包java.util.concurrent下包含了大量线程安全的集合类,效率上有较大提升。
参考: