实际开发中,经常用到 java 的集合框架,比如 ArrayList 、 LinkedList 、 HashMap 、 LinkedHashMap,几乎经常接触到,虽然用的多,但是对集合的整体框架,基础知识还是不够系统,今天想和大家一起来梳理一下!
01、集合类简介
Java 集合就像一种容器,可以把多个对象(实际上是对象的引用,但习惯上都称对象)“丢进”该容器中。从 Java 5 增加了泛型以后,Java 集合可以记住容器中对象的数据类型,使得编码更加简洁、健壮。
Java 集合大致可以分为两大体系,一个是 Collection,另一个是 Map;
- Collection :主要由List、Set、Queue接口组成,List代表有序、重复的集合;其中Set代表无序、不可重复的集合;Java 5 又增加了Queue体系集合,代表一种队列集合实现。
- Map:则代表具有映射关系的键值对集合。
java.util.Collection 下的接口和继承类关系简易结构图:
java.util.Map 下的接口和继承类关系简易结构图:
其中,Java 集合框架中主要封装的是典型的数据结构和算法,如动态数组、双向链表、队列、栈、Set、Map 等。
将集合框架挖掘处理,可以分为以下几个部分
1) 数据结构
List
列表、Queue
队列、Deque
双端队列、Set
集合、Map
映射
2) 比较器
Comparator
比较器、Comparable
排序接口
3) 算法
Collections
常用算法类、Arrays
静态数组的排序、查找算法
4) 迭代器
Iterator
通用迭代器、ListIterator
针对 List
特化的迭代器
02、有序列表(List)
List集合的特点就是存取有序,可以存储重复的元素,可以用下标进行元素的操作
List主要实现类:ArrayList、LinkedList、Vector、Stack。
2.1、ArrayList
ArrayList 是一个动态数组结构,支持随机存取,尾部插入删除方便,内部插入删除效率低(因为要移动数组元素);如果内部数组容量不足则自动扩容,因此当数组很大时,效率较低。
2.2、LinkedList
LinkedList 是一个双向链表结构,在任意位置插入删除都很方便,但是不支持随机取值,每次都只能从一端开始遍历,直到找到查询的对象,然后返回;不过,它不像 ArrayList 那样需要进行内存拷贝,因此相对来说效率较高,但是因为存在额外的前驱和后继节点指针,因此占用的内存比 ArrayList 多一些。
2.3、Vector
Vector 也是一个动态数组结构,一个元老级别的类,早在 jdk1.1 就引入进来类,之后在 jdk1.2 里引进 ArrayList,ArrayList 大部分的方法和 Vector 比较相似,两者是不同的,Vector 是允许同步访问的,Vector 中的操作是线程安全的,但是效率低,而 ArrayList 所有的操作都是异步的,执行效率高,但不安全!
关于Vector
,现在用的很少了,因为里面的get
、set
、add
等方法都加了synchronized
,所以,执行效率会比较低,如果需要在多线程中使用,可以采用下面语句创建 ArrayList 对象
1 |
|
也可以考虑使用复制容器 java.util.concurrent.CopyOnWriteArrayList
进行操作,例如:
1 |
|
2.4、Stack
Stack 是 Vector 的一个子类,本质也是一个动态数组结构,不同的是,它的数据结构是先进后出,取名叫栈!
关于Stack
,现在用的也很少,因为有个ArrayDeque
双端队列,可以替代Stack
所有的功能,并且执行效率比它高!
03、集(Set)
Set集合的特点:元素不重复,存取无序,无下标;
Set主要实现类:HashSet、LinkedHashSet 和 TreeSet。
3.1、HashSet
HashSet底层是基于 HashMap 的k
实现的,元素不可重复,特性同 HashMap。
3.2、LinkedHashSet
LinkedHashSet底层也是基于 LinkedHashMap 的k
实现的,一样元素不可重复,特性同 LinkedHashMap。
3.3、TreeSet
同样的,TreeSet 也是基于 TreeMap 的k
实现的,同样元素不可重复,特性同 TreeMap;
Set 集合的实现,基本都是基于 Map 中的键做文章,使用 Map 中键不能重复、无序的特性;所以,我们只需要重点关注 Map 的实现即可!
04、队列(Queue)
Queue是一个队列集合,队列通常是指“先进先出”(FIFO)的容器。新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。通常,队列不允许随机访问队列中的元素。
Queue主要实现类:ArrayDeque、LinkedList、PriorityQueue。
4.1、ArrayDeque
ArrayQueue是一个基于数组实现的双端队列,可以想象,在队列中存在两个指针,一个指向头部,一个指向尾部,因此它具有“FIFO队列”及“栈”的方法特性。
既然是双端队列,那么既可以先进先出,也可以先进后出,以下是测试例子!
先进先出
1 |
|
输出结果:
1 |
|
先进后出
1 |
|
输出结果:
1 |
|
4.2、LinkedList
LinkedList是List接口的实现类,也是Deque的实现类,底层是一种双向链表的数据结构,在上面咱们也有所介绍,LinkedList可以根据索引来获取元素,增加或删除元素的效率较高,如果查找的话需要遍历整合集合,效率较低,LinkedList同时实现了stack、Queue、PriorityQueue的所有功能。
例子
1 |
|
输出结果:
1 |
|
4.3、PriorityQueue
PriorityQueue也是一个队列的实现类,此实现类中存储的元素排列并不是按照元素添加的顺序进行排列,而是内部会按元素的大小顺序进行排列,是一种能够自动排序的队列。
例子
1 |
|
输出结果:
1 |
|
05、映射表(Map)
Map是一个双列集合,其中保存的是键值对,键要求保持唯一性,值可以重复。
Map 主要实现类:HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties。
5.1、HashMap
关于HashMap,相信大家都不陌生,继承自AbstractMap,key 不可重复,因为使用的是哈希表存储元素,所以输入的数据与输出的数据,顺序基本不一致,另外,HashMap最多只允许一条记录的 key 为 null。
5.2、LinkedHashMap
HashMap 的子类,内部使用链表数据结构来记录插入的顺序,使得输入的记录顺序和输出的记录顺序是相同的。LinkedHashMap与HashMap最大的不同处在于,LinkedHashMap输入的记录和输出的记录顺序是相同的!
5.3、TreeMap
能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用 Iterator 遍历时,得到的记录是排过序的;如需使用排序的映射,建议使用 TreeMap。TreeMap实际使用的比较少!
5.4、IdentityHashMap
继承自AbstractMap,与HashMap有些不同,在获取元素的时候,通过==
代替equals ()
来进行判断,比较的是内存地址。
get方法源码部分
1 |
|
5.5、WeakHashMap
WeakHashMap继承自AbstractMap,被称为缓存Map,向WeakHashMap中添加元素,再次通过键调用方法获取元素方法时,不一定获取到元素值,因为WeakHashMap 中的 Entry 可能随时被 GC 回收。
5.6、Hashtable
Hashtable,一个元老级的类,键值不能为空,与HashMap不同的是,方法都加了synchronized
同步锁,是线程安全的,但是效率上,没有HashMap快!
同时,HashMap 是 HashTable 的轻量级实现,他们都完成了Map 接口,区别在于 HashMap 允许K和V为空,而HashTable不允许K和V为空,由于非线程安全,效率上可能高于 Hashtable。
如果需要在多线程环境下使用HashMap,可以使用如下的同步器来实现或者使用并发工具包中的ConcurrentHashMap
类
1 |
|
5.7、Properties
Properties继承自HashTable,Properties新增了load()和和store()方法,可以直接导入或者将映射写入文件,另外,Properties的键和值都是String类型。
06、比较器
Comparable和Comparator接口都是用来比较大小的,一般在TreeSet、TreeMap接口中使用的比较多,主要用于解决排序问题。
6.1、Comparable
Comparable:对实现它的每个类的对象进行整体排序
1 |
|
若一个类实现了Comparable 接口,实现 Comparable 接口的类的对象的 List 列表 ( 或数组)可以通过 Collections.sort(或 Arrays.sort)进行排序。
此外,实现 Comparable 接口的类的对象 可以用作 “有序映射 ( 如 TreeMap)” 中的键或 “有序集合 (TreeSet)” 中的元素,而不需要指定比较器。
使用例子:
1 |
|
测试
1 |
|
输出:
1 |
|
6.2、Comparator
Comparator:也是对实现它的每个类的对象进行排序
1 |
|
如果我们的这个类Person
无法修改或者没有继承Comparable
接口,我们又要对其进行排序,Comparator就可以派上用场了。
将类Person
实现的Comparable
接口去掉
1 |
|
测试类:
1 |
|
输出:
1 |
|
07、常用工具类
7.1、Collections类
java.util.Collections工具类为集合框架提供了很多有用的方法,这些方法都是静态的,在编程中可以直接调用。整个Collections工具类源码差不多有4000行,这里只针对一些典型的方法进行阐述。
7.1.1、addAll
addAll:向指定的集合c中加入特定的一些元素elements
1 |
|
7.1.2、binarySearch
binarySearch:利用二分法在指定的集合中查找元素
1 |
|
7.1.3、sort
1 |
|
7.1.4、shuffle
shuffle:混排,随机打乱原来的顺序,它打乱在一个List中可能有的任何排列的踪迹。
1 |
|
7.1.5、reverse
reverse:集合排列反转
1 |
|
7.1.6、synchronized系列
synchronized系列:确保所封装的集合线程安全(强同步)
1 |
|
7.2、Arrays类
java.util.Arrays工具类也为集合框架提供了很多有用的方法,这些方法都是静态的,在编程中可以直接调用。整个Arrays工具类源码有3000多行,这里只针对一些典型的方法进行阐述。
7.2.1、asList
asList:将一个数组转变成一个List,准确来说是ArrayList
1 |
|
注意:这个List是定长的,企图添加或者删除数据都会报错java.lang.UnsupportedOperationException
7.2.2、sort
sort:对数组进行排序,适合byte,char,double,float,int,long,short等基本类型,还有Object类型
1 |
|
7.2.3、binarySearch
binarySearch:通过二分查找法对已排序的数组进行查找。如果数组没有经过Arrays.sort排序,那么检索结果未知。
适合byte,char,double,float,int,long,short等基本类型,还有Object类型和泛型。
1 |
|
7.2.4、copyOf
copyOf:数组拷贝,底层采用System.arrayCopy(native方法)实现。
适合byte,char,double,float,int,long,short等基本类型,还有泛型数组。
1 |
|
7.2.5、copyOfRange
copyOfRange:数组拷贝,指定一定的范围,底层采用System.arrayCopy(native方法)实现。
适合byte,char,double,float,int,long,short等基本类型,还有泛型数组。
1 |
|
7.2.6、equals和deepEquals
equals:判断两个数组的每一个对应的元素是否相等(equals, 对于两个数组的元素a和a2有a==null ? a2==null : a.equals(a2)
)
1 |
|
deepEquals:主要针对一个数组中的元素还是数组的情况(多维数组比较)
1 |
|
7.2.7、toString和deepToString
toString:将数组转换成字符串,中间用逗号隔开
1 |
|
deepToString:当数组中又包含数组,就不能单纯的利用Arrays.toString()了,使用此方法将数组转换成字符串
1 |
|
08、迭代器
JCF的迭代器(Iterator)为我们提供了遍历容器中元素的方法。只有容器本身清楚容器里元素的组织方式,因此迭代器只能通过容器本身得到。每个容器都会通过内部类的形式实现自己的迭代器。
1 |
|
JDK 1.5 引入了增强的for循环,简化了迭代容器时的写法
1 |
|
09、总结
以上,主要是对java集合的整体架构进行简单的介绍,如果有理解不当之处,欢迎指正。
10、参考
1、JDK1.7&JDK1.8 源码