Java的集合类均都位于java.util包下,主要分为两大类:一类是Collection,代表一组对象; 一类是Map,代表映射
Collection类代表一组对象,不关心对象是否重复、是否有序,提供的是基本的操作。根据是否允许重复衍生出Set、List接口,其中Set不允许元素重复,List中的元素可以重复。Queue接口代表了一种FIFO结构。 Set接口又根据是否有序衍生出SortedSet接口和其他实现类,其中TreeSet实现了SortedTree,内部元素保持有序。 List接口的实现类有ArrayList和LinkedList,Vector和Stack。
AbstractCollection类是一个抽象类,实现了Collection接口,并将能实现的方法实现了,比如isEmpty()、contains(Object o)、remove()等方法;而将iterator()方法、size()方法实现成抽象方法,子类需要实现这两个方法。AbstractCollection的子类有AbstractList、AbstractSet、AbstractQueue,分别是List、Set和Queue接口的实现类的顶层类。
List接口提供了从某一索引得到对象、将对象插入到指定索引位置。List允许重复的元素存在以及null元素存在。List接口提供了一个特殊的迭代器,ListIterator。
AbstractList是List接口的一个实现类,同时该类继承自AbstractCollection类。提供了List部分接口的基本操作,但同时依然是一个抽象类,抽象方法有get(int index)用于根据索引得到对象,实现类的底层结构不同,这个方法自然不同。
ArrayList是平常使用的很多的一个集合类,继承自AbstractList类,也就意味着实现了get(int index)抽象方法。至于是如何ArrayList的内部结构,后面介绍源码的文章会介绍到,这儿就不介绍了。ArrayList是一个动态扩展的List,不需要担心索引溢出的问题;当操作查询操作时,效率很高;当操作添加、删除元素的操作时,效率较低。
Vector类与ArrayList类类似,只不过Vector是一个线程安全的类,而ArrayList则不是。
LinkedList类继承自AbstractSequentialList类,AbstractSequentailList是一个继承了AbstractList的抽象类,其抽象方法是listIterator()方法用于返回一个正确迭代元素的迭代器。LinkedList在频繁地添加、删除元素时效率很高;在查询元素时效率较低。
Set是不包含重复元素的集合。
AbstractSet是Set接口的一个实现类,同时该类继承自AbstractCollection类。该类实现了equals、hashcode、removeAll方法,Set接口中其余方法均为抽象方法。
TreeSet是一个排序的Set,其add、remove、contain方法的时间复杂度为log(n)。因为有序,提供了相关方法,比如lower()、floor()、ceiling()等方法。
HashSet继承自AbstractSet,内部维持了一张Hash表。将插入的值进行hash后放入表中,删除时,先查找hash值,再删除对象。
Queue代表了FIFO结构,接口中定义的是在队头取数据,在队尾添加数据的方法。其中插入、删除、检索都有抛出异常的方法和不抛出异常的方法,如下:
操作抛出异常返回特定的值插入add(e)offer(e)删除remove(e)poll()检索element()peek()AbstractQueue类继承自AbstractCollection类,实现了Queue接口。并将Queue接口中抛出异常的方法实现了,而没有返回特定的值的方法实现,所以AbstractQueue类是一个抽象类,其子类需要实现那些返回特定值的方法。
BlockingQueue接口继承自Queue接口,并在其上增加了阻塞的操作,可以实现该类简单快速地实现生产者-消费者模式。其主要方法如下:
操作抛出异常特定值阻塞定时插入add(e)offer(e)put(e)offer(e,time,unit)删除remove()poll()take()poll(time,unit)检索element()peek()没有没有Deque是一个双端队列,即既可以在队列头部执行插入和删除操作,也可以在队列尾部进行插入和删除操作。其方法也分为返回异常和返回特定值。 - 插入操作 - 头部:addFirst(e)(抛出异常)、offerFirst(e)(返回特定值) - 尾部:addLast(e)(抛出异常)、offerLast(e)(返回特定值) - 删除操作 - 头部:removeFirst()(抛出异常)、pollFirst(返回特定值) - 尾部:removeLast()(抛出异常)、pollLast(返回特定值) - 检索操作 - 头部:getFirst()(抛出异常)、peekFirst()(返回特定值) - 尾部:getLast()(抛出异常)、peekLast()(返回特定值)
Map接口根据是否键值是否有序分为SortedMap接口和其他实现类,SortedMap接口的实现类是TreeMap。 Map结构的层次结构与Collection类似,其实现类AbstractMap是一个抽象类,Map的具体实现都继承自AbstractMap这个类。 Map常用的类有HashMap、TreeMap
Collections类和Arrays类类似,都是Java提供的工具类,Arrays类用于处理数据,Collections用于处理集合。Collections提供了排序、二分查找、反转等方法。