Java集合框架

    集合框架有很多的类，他们的区别就是内部的数据存储形式（队列，set还是Map），他们有很多类是有很大的相似程度的，区别是在是否允许存在null，是否允许有重复的元素存在，是否线程安全，是否阻塞，以及在读写删的过程哪个更加方便，这将是我们需要根据实际应用来考虑的，挑选也是这么按照这个标准来。



List


ArrayList
ArrayList 是一个可变数组, 它有数组的所有优缺点, 如高效的随机访问, 低效的插入和删除. 它允许重复值, 允许null, 有序(所谓的有序指的是读取元素的顺序和插入的顺序一致).


Vector
Vector 除了提供了同步外, 它和 ArrayList 没有任何区别, 因为它是线程安全的, 所以效率比较差, Java 推荐我们尽量使用 ArrayList.


Stack
Stack 是一种后进先出的数据结构, 它继承自Vector, 所以它也是线程安全的. 由于设计上的缺陷, 现在已经不推荐使用了, 推荐使用 Deque.


CopyOnWriteArrayList
CopyOnWriteArrayList 是一个线程安全的 ArrayList, 当我们构建一个迭代器时, 它对当前数组的引用, 如果数组被修改了, 它仍然引用旧的数组. 这种设计对读线程大大多于写线程时, 非常有用.


LinkedList
LinkedList 是一个双向列表, 它的特点是高效插入和删除, 低效的随机访问, 所以千万不要使用像 get(int index) 等包含索引信息的方法. 问题是有时候我们并不知道某个List 到底是Arraylist 还是LinkedList， 为此， JDK 1.4 引入了一个接口 RandomAccess，它没有任何方法，只是用来标记某个list 是否支持高效的随机访问。 所以，我们可以使用下面的代码来判读某个list是否支持高效的随机访问。

view plaincopyprint?
if (list instanceof RandomAccess) {  
...  
} else {  
...  
}  

除此之外, 它允许重复值, 允许null, 有序.

Set

HashSet
HashSet 不允许有重复值, 允许有一个null, 它的优点是可以快速的帮我们查找对象, 缺点是我们无法控制对象的顺序.

LinkedHashSet
LinkedHashSet 继承了 HashSet, 它克服了 HashSet 的缺点, 我们可以按照对象插入的顺序来迭代对象.

TreeSet
TreeSet 不允许有重复值, 允许有一个null, 它包含的对象是经过排序的, 排序之后形成一个树状结构, 这就是叫它 TreeSet 的原因. 因为它要排序, 所以加入它的对象必须实现 Comparable 接口或在创建 TreeSet 时提供比较器(Comparator), 在迭代 TreeSet 时, 我们可以按照升序迭代, 也可以按照降序迭代.

ConcurrentSkipListSet
Skip List 是一种数据结构, 它在有序链表的基础上进行了扩展， 解决了有序链表查找特定值困难的问题。 因为链表不能像数组那样进行二分查找, 所以在最坏的情况下, 我们需要遍历整个列表才能找到我们需要的值. 但是如果每个节点存储了它后面2个节点地址的话, 遍历时我们就可以跳过中间的节点, 如: 从第1个节点直接跳到第3个节点, 在最坏的情况下, 需要遍历 n/2+1 个节点. 如果每个节点存储了它后面4个节点地址的话, 我们就可以从第1个节点直接跳到第5个节点, 在最坏的情况下, 我们需要遍历 n/4+1 个节点, 这就是跳表(Skip List)的思想, 这是一种以空间换取时间的思想.


ConcurrentSkipListSet
不允许有重复值, 不允许有null, 它包含的对象是经过排序的, 使用 Skip List 数据结构存储. 因为它要排序, 所以加入它的对象必须实现 Comparable 接口或在创建 ConcurrentSkipListSet 时提供比较器(Comparator). 除此之外, 它还是线程安全的, 我们可以按照升序迭代, 也可以按照降序迭代, 不过如果随后某个值被修改了, 迭代时仍然引用旧的值.

CopyOnWriteArraySet
CopyOnWriteArraySet 是一个线程安全的 Set, 它内部使用的是 CopyOnWriteArrayList, 所以它们都有共同的特点, 当我们构建一个迭代器时, 它对当前数组的引用, 如果数组被修改了, 它仍然引用旧的数组. 这种设计对读线程大大多于写线程时, 非常有用.

EnumSet
EnumSet 只能包含某种枚举类型的对象, 不允许有重复值, 不允许有null. 迭代顺序和它们在枚举中定义的顺序一致.

Map

HashMap
HashMap
允许null值和null键. 它的优点是可以快速的帮我们查找对象, 缺点是我们无法控制对象的顺序.

LinkedHashMap
LinkedHashMap 继承自 HashMap. 它克服了 HashMap 的缺点, 我们可以按照对象插入顺序或访问顺序来迭代对象, 这取决于你使用的构造方法. 当我们使用下面的构造方法构造一个LinkedHashMap后, 每当访问其中的元素时, 该元素就会从当前的位置移到链表的尾部, 由此我们可以知道, 离链表开头越近的元素使用的最少, 这就是传说中的“最少最近原则”， 这个特性对于实现高速缓存非常有用, 例如, 我们可能希望将最常访问的元素放到缓存中, 而将不长访问的元素放到数据库中.

view plaincopyprint?
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

 

Hashtable
Hashtable 和 HashMap 的主要区别在于 Hashtable 是线程同步的, 除此之外, Hashtable 不允许有 Null 值和 Null 键.

ConcurrentHashMap
ConcurrentHashMap 是线程安全的, 它使用了非常复杂的算法, 永远也不会锁住整个表, 而是只锁定表的某个片段, 从而提高了并发性. 它的迭代器只能反映构建时的状态, 如果创建迭代器之后数据修改了, 迭代器还是引用旧的数据. 除此之外, 它不允许有 Null 值和 Null 键.

WeakHashMap
如果 Map 中的键对象没有实现 equals 方法(也就是说 equals 方法的行为和 == 是一致的), 那么如果在 Map 外部没有这个键对象, 我们将不能查找 Map 中的这个元素了, 但是垃圾回收器并不会回收这个元素. WeakHashMap 就是为了解决这个问题而设计的, 在这种情况下, WeakHashMap 中的这个元素将被垃圾回收器回收. 除此之外, 它和 HashMap 没有任何区别.

IdentityHashMap
在 HashMap 中, 它用 equals 方法来判断两个键是否相等, 而在 IdentityHashMap 中, 它用 == 来判断两个键是否相等. 除此之外, 它和 HashMap 没有任何区别.

TreeMap
TreeMap 的键是经过排序的, 排序之后形成一个树状结构, 这就是叫它 TreeMap 的原因. 因为它要排序, 所以加入它的键必须实现 Comparable 接口或在创建 TreeMap 时提供比较器(Comparator). 除此之外, 它还提供了一些按键检索的方法.

ConcurrentSkipListMap
Skip List 是一种数据结构, 它在有序链表的基础上进行了扩展， 解决了有序链表查找特定值困难的问题。 因为链表不能像数组那样进行二分查找, 所以在最坏的情况下, 我们需要遍历整个列表才能找到我们需要的值. 但是如果每个节点存储了它后面2个节点地址的话, 遍历时我们就可以跳过中间的节点, 如: 从第1个节点直接跳到第3个节点, 在最坏的情况下, 需要遍历 n/2+1 个节点. 如果每个节点存储了它后面4个节点地址的话, 我们就可以从第1个节点直接跳到第5个节点, 在最坏的情况下, 我们需要遍历 n/4+1 个节点, 这就是跳表(Skip List)的思想, 这是一种以空间换取时间的思想.


ConcurrentSkipListMap
是线程安全的, 不允许有 null 键和 null 值, 它的键是经过排序的, 使用 Skip List 数据结构存储, 所以加入它的键必须实现 Comparable 接口或在创建 ConcurrentSkipListMap 时提供比较器(Comparator), 除此之外, 它也提供了一些按键检索的方法.

EnumMap
EnumMap 不允许null键, 允许null值. 它的键必须是某个枚举类型.


队列(Queue)
队列(Queue)是一种先进先出的数据结构, 但是 Java 中 Queue 的有些实现类并不是先进先出的, 如: PriorityQueue, PriorityBlockingQueue. Queue 不允许有 null 值, 因为 poll 方法返回 null 来指示 Queue 中没有元素了.

PriorityQueue
优先级队列(PriorityQueue)中的元素是经过排序的, 所以加入它中的元素必须实现了 Comparable 接口或构建优先级队列时指定比较器. 我们可以按照任意的顺序加入元素, 但是 poll, remove, peek 等方法返回的总是最小的那个元素. 需要注意的是当我们迭代优先级队列时, 迭代的顺序是不确定的. 其次, 它没有容量限制, 不允许有null, 它是非线程安全的. 使用优先级队列的一个典型的例子是任务调度, 每个任务都有一个优先级, 任务以任何的顺序加入优先级队列, 优先级高的总是被第一个取出.

ConcurrentLinkedQueue
ConcurrentLinkedQueue 是一种先进先出的数据结构, 它线程安全的, 没有容量限制, 它不允许 null 值. 它的迭代器只能反映构建时的状态, 如果创建迭代器之后数据修改了, 迭代器还是引用旧的数据

阻塞队列(BlockingQueue)
Java 1.5 加入了阻塞队列(BlockingQueue), 它大大简化了我们编写经典的生产者-消费者线程的工作量, 我们再也不需要使用 wait, notifyAll 等方法来同步生产者和消费者线程. 生产者线程只管往 BlockingQueue 中加入数据, 如果 BlockingQueue 的容量已满, 则 put 方法阻塞直到有容量为止. 消费者线程只管从 BlockingQueue 中读取数据, 如果 BlockingQueue 中没有数据, 则 take 方法阻塞直到有数据为止. 很明显, 生产者线程需要在所有的数据都加入 BlockingQueue 后, 加入一个特殊的数据(如:EOF), 以此来告诉消费者线程数据已读完, 否则消费者线程会一直等待不会结束.

ArrayBlockingQueue
ArrayBlockingQueue 是底层使用数组存储数据的阻塞队列.

LinkedBlockingQueue
LinkedBlockingQueue 是底层使用链表数据结构存储数据的阻塞队列.

PriorityBlockingQueue
PriorityBlockingQueue 是一种阻塞队列, 除了提供了线程安全和阻塞外, PriorityBlockingQueue 和 PriorityQueue 非常类似.

DelayQueue
DelayQueue 是一种特殊的阻塞队列, 加入它中的元素必须实现 Delayed 接口, 只有到期的元素才能被取出, 最先取出的元素是到期时间最长的元素.

SynchronousQueue
SynchronousQueue 是一种特殊的阻塞队列, 它不能容纳任何元素, 它的插入操作会被阻塞直到另一个线程读取, 反之亦然. 它被用来在多个线程之间同步传递数据.

LinkedTransferQueue
LinkedTransferQueue 是一种特殊的阻塞队列, 它既可以当做 LinkedBlockingQueue 来使用, 也可以当做 SynchronousQueue 来使用. 所以, 它可以用来在多个线程之间同步传递数据, 以用来异步传递数据.


双端队列(Deque)
双端队列(Deque) 也是一种 queue, 它是 "double ended queue" 的缩写, 读作 "deck". 顾名思义, 我们可以在 Deque 的两端进行插入和删除操作. 它既可以用作先进先出的队列, 也可用作后进先出的栈.

ArrayDeque
ArrayDeque 是一种底层采用数组存储的 Deque.

LinkedList
LinkedList 是一种底层采用链表存储的 Deque.

ConcurrentLinkedDeque
除了线程安全外, 它和 LinkedList 很相似.

LinkedBlockingDeque
LinkedBlockingDeque 是一种底层采用链表存储的阻塞双端队列.



Arrays 和 Collections
这两个类是工具类， 它们包含了很多非常实用的静态方法， 如下面的两个方法可以帮助我们实现数组与列表的相互转换。

view plaincopyprint?
Arrays.asList 
List.toArray 


如果我们的集合需要在多线程环境下使用， 我们可以使用下面的方法来包装集合。

[java] view plaincopyprint?
Collections.synchronizedCollection 
Collections.synchronizedList 
Collections.synchronizedMap 
Collections.synchronizedSet 
Collections.synchronizedSortedMap 
Collections.synchronizedSortedSet 

如果我们想创建只读集合，那么我们可以使用面的方法来包装集合。

[java] view plaincopyprint?
Collections.unmodifiableCollection 
Collections.unmodifiableList 
Collections.unmodifiableMap 
Collections.unmodifiableSet 
Collections.unmodifiableSortedMap 
Collections.unmodifiableSortedSet 


如果你想对列表进行排序，你可以使用下面的方法。

[java] view plaincopyprint?
Collections.sort 
Collections.reverseOrder 
Collections.shuffle 

总之，这两个类提供许多非常有用的方法。