Java集合框架(Java Collections Framework)是存放大量对象的容器,被广泛使用。Java里包含这四种集合类:Vector, Stack, Hashtable, Array。
集合中存放的是对象的引用。
Java1.2开始提供集合框架,这包括:
-
接口
所有集合类都得实现java.util.Collection
。这个接口的方法(文档)包括:- 基本操作:
int size(), boolean isEmpty(), boolean contains(Object element), boolean add(E element), boolean remove(Object element), and Iterator<E> iterator() - 对整个集合类的操作:
boolean containsAll(Collection<?> c), boolean addAll(Collection<? extends E> c), boolean removeAll(Collection<?> c), boolean retainAll(Collection<?> c), and void clear() - Array操作:
Object[] toArray() and <T> T[] toArray(T[] a)
java.util.List
,java.util.Set
,java.util.Queue
和java.util.Map
接口也是集合框架的一部分。(Map没用继承自Collection接口) - 基本操作:
实现类
重要的集合类有ArrayList
,LinkedList
,HashMap
,TreeMap
,HashSet
,TreeSet
。(java.util
包)
线程安全的类有CopyOnWriteArrayList
,ConcurrentHashMap
,CopyOnWriteArraySet
。(java.util.concurrent
包)算法
如查询、排序、打乱
Iterator接口
取代了Enumeration
,可以简单地理解为遍历,提供了一个标准化遍历各类容器里面的所有对象的设计模式。方法:
- Object next():返回迭代器刚越过的元素的引用,返回值是 Object
- boolean hasNext():判断容器内是否还有可供访问的元素
- void remove():删除迭代器刚越过的元素
Iterator it = collection.iterator(); // 获得一个迭代起点
while(it.hasNext()) {
Object obj = it.next(); // 得到下一个元素
}
ListIterator是Iterator的子接口,区别在于,只能用于List及其子类型;有add方法;可以实现逆向(顺序向前)遍历;可以定位当前索引的位置;可以实现对象的修改。(参考:JAVA中ListIterator和Iterator详解与辨析)
List接口
有序,允许相同元素,有索引
除了具有Collection接口必备的iterator()方法外,List还有一个listIterator()方法,返回一个 ListIterator接口。
实现List接口的常用类有LinkedList,ArrayList,Vector和Stack。
ArrayList类
类似数组的形式进行存储,随机访问速度快。
线程不同步。
内部的元素直接通过get与set方法进行访问。
当ArrayList中的元素超过它的初始大小时,ArrayList只增加50%的大小。LinkedList类
双链表,在添加和删除元素时具有比ArrayList更好的性能,但在get与set方面弱于ArrayList。
线程不同步。Vector类
和ArrayList类似,但线程同步
当Vector中的元素超过它的初始大小时,Vector会将它的容量翻倍Stack 类
Stack继承自Vector,实现一个后进先出的堆栈。
基本的push和pop 方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
Set接口
无序
不包含重复元素
取出只能是Iterator
HashSet
一个按着Hash算法来存储集合中的元素,其元素值可以是NULL。它不能保证元素的排列顺序。LinkedHashList
HashSet的子类TreeSet
红黑树,线程不安全
提供有序的 Set 集合( 实现SortedSet
接口),储存的类需要实现需要实现Comparable接口
SortedSet<Item> sortByDescription = new TreeSet<Item>(new
Comparator<Item>()
{
public int compare(Item a, Item b)
{
String descrA = a.getDescription();
String descrB = b.getDescription();
return descrA.compareTo(descrB);
}
});
Queue接口
无null
方法:add
,addall
, remove
, clear
和element
- PriorityQueue优先队列
非线程安全
PriorityQueue是基于优先堆的一个无界队列,这个优先队列中的元素可以默认自然排序或者通过提供的Comparator比较器在队列实例化的时排序。
Map接口
没有继承Collection接口
提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个 value。
put(Object key, Object value)
将指定值与指定键相关联
entrySet()
返回 Map 中所包含映射的 Set 视图。Set 中的每个元素都是一个 Map.Entry 对象,可以使用 getKey() 和 getValue() 方法(还有一个 setValue() 方法)访问后者的键元素和值元素
keySet()
返回 Map 中所包含键的 Set 视图。删除 Set 中的元素还将删除 Map 中相应的映射(键和值)
values()
返回 map 中所包含值的 Collection 视图。删除 Collection 中的元素还将删除 Map 中相应的映射(键和值)
Hashtable类
Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空的对象都可作为key或者value。
添加数据使用put(key, value),取出数据使用get(key),这两个基本操作的时间开销为常数。
Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大,这会影响像get和put这样的操作。
由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。
Hashtable是同步的。HashMap类
HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key。
但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap 的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。TreeMap类
通关红黑树实现, 继承 自AbstractMap
(即一个key-value集合)。 非线程安全 。
实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合。
实现了Cloneable接口,意味着它能被克隆。
实现了java.io.Serializable接口,意味着它支持序列化。
基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n)
按自然顺序或自定义顺序遍历键,TreeMap比HashMap要好;在Map 中插入、删除和定位元素,HashMap 是最好的选择。
- WeakHashMap类
WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。
集合对象排序接口Comparator
实现此接口的类可以进行排序,需要实现compare方法。
基本数据类型实现了这个接口,调用Collections.sort(list)进行排序;
如果Comparator只用一次,可使用匿名类。