What's collection
a framework/architecture(a set of classes /interface) to store and manipulation group(single unit) of objcts.
存储和操作对象集合的框架。
sorting, searching, insert, delete, iterate etc.
支持排序、查询、插入、删除、遍历等操作。
many interfaces: List, Set, Queue, Dequeue etc.
封装了很多接口。
many classes: ArrayList, Vector, LinkedList, PriorityQueue, HashSet, TreeSet etc.
封装了很多类。
The core collection interfaces
Collection
A collection represents a group of objects known as its elements.
代表对象的集合，对象是集合的元素。
Set
a collection that cannot contain duplicate elements. unordered, no duplicate, at most one null.
不能包含重复元素的集合。元素无序，不允许重复，最多一个null。
List
an ordered collection (sometimes called a sequence).
有序集合。
Queue
a collection used to hold multiple elements prior to processing. FIFO.
先进先出。
Deque
doubled ended queue.
Map
an object that maps keys to values.
SortedSet
a Set that maintains its elements in ascending order.
SortedMap
a Map that maintains its mappings in ascending key order.
The collection hierarchy
Collection Implementations
|
Collection |
Ordering |
Random Access |
Key-Value |
Duplicate Elements |
Null Element |
Thread Safety |
|
ArrayList |
Y |
Y |
N |
Y |
Y |
N |
|
LinkedList |
Y |
N |
N |
Y |
Y |
N |
|
HashSet |
N |
N |
N |
N |
Y |
N |
|
TreeSet |
Y |
N |
N |
N |
N |
N |
|
HashMap |
N |
Y |
Y |
N |
Y |
N |
|
TreeMap |
Y |
Y |
Y |
N |
N |
N |
|
Vector |
Y |
Y |
N |
Y |
Y |
Y |
|
Hashtable |
N |
Y |
Y |
N |
N |
Y |
|
Properties |
N |
Y |
Y |
N |
N |
Y |
|
Stack |
Y |
N |
N |
Y |
Y |
Y |
|
CopyOnWriteArrayList |
Y |
Y |
N |
Y |
Y |
Y |
|
ConcurrentHashMap |
N |
Y |
Y |
N |
N |
Y |
|
CopyOnWriteArraySet |
N |
N |
N |
N |
Y |
Y |
java.util.Set
A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.
java.util.HashSet
一种没有重复元素的无序集合，用 HashMap 实现。
java.util.TreeSet
底层数据结构是红黑树，TreeSet不仅保证元素的唯一性，也保证元素的顺序。
java.util.LinkedHashSet
HashSet+LinkedHashMap.
maintain insertion order, permit nulls.
底层数据结构是链表和哈希表，哈希表用来保证元素唯一，链表用来保证元素的插入顺序，即FIFO(First Input First Output 先进先出)。
java.util.concurrent.CopyOnWriteArraySet
Set 的线程安全实现。
java.util.concurrent.ConcurrentSkipListSet
类似于 TreeSet，但是线程安全。
Sorted, navigable, and concurrent.
java.util.List
java.util.ArrayList
一种可以动态增长和缩减的索引序列，数组实现。
random access, add/remove expensive(shift), not ordered.
优点是适合随机查找和遍历，缺点是不适合插入和删除。
动态扩容。
java.util.LinkedList
一种可以在任何位置进行高效地插入和删除操作的有序序列，双向链表实现。
sequence access,add/remove cheap(no shift), ordered.
优点是适合动态插入和删除元素，缺点是随机查找和遍历速度比较慢。
java.util.concurrent.CopyOnWriteArrayList
A thread-safe variant of java.util.ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.
java.util.Vector
数组实现、线程同步。
like ArrayList, but synchronized, more methods.
java.util.Stack
extends Vector, LIFO, more methods.
java.util.Queue
A collection designed for holding elements prior to processing.
|
方法/处理方式 |
抛出异常 |
返回特殊值 |
一直阻塞 |
超时退出 |
|
插入方法 |
add(e) |
offer(e) |
put(e) |
offer(e, time, unit) |
|
移除方法 |
remove() |
poll() |
take() |
poll(time, unit) |
|
检查方法 |
element() |
peek() |
不可用 |
不可用 |
java.util.PriorityQueue
基于优先级堆实现的无界优先级队列。
An unbounded priority queue based on a priority heap.
一种允许高效删除最小元素的集合。
java.util.concurrent.ArrayBlockingQueue
由数组支持的有界阻塞队列。
A bounded blocking queue backed by an array. This queue orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue.
java.util.concurrent.LinkedBlockingQueue
基于链接节点的可选有界阻塞队列。
An optionally-bounded blocking queue based on linked nodes. This queue orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue. Linked queues typically have higher throughput than array-based queues but less predictable performance in most concurrent applications.
java.util.concurrent.LinkedTransferQueue
An unbounded TransferQueue based on linked nodes. This queue orders elements FIFO (first-in-first-out) with respect to any given producer. The head of the queue is that element that has been on the queue the longest time for some producer. The tail of the queue is that element that has been on the queue the shortest time for some producer.
java.util.concurrent.ConcurrentLinkedQueue
An unbounded thread-safe queue based on linked nodes. This queue orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue.
java.util.Deque
A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck". Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.
java.util.concurrent.BlockingDeque
A Deque that additionally supports blocking operations that wait for the deque to become non-empty when retrieving an element, and wait for space to become available in the deque when storing an element.
java.util.ArrayDeque
一种用循环数组实现的双端队列。
java.util.LinkedBlockingDeque
An optionally-bounded blocking deque based on linked nodes.
java.util.concurrent.ConcurrentLinkedDeque
An unbounded concurrent deque based on linked nodes.
java.util.Map
java.util.HashMap
一种存储键/值关联的数据结构，数组+链表+红黑树。
unique key, dup values; allow null values and null keys.
动态扩容：容量大小，负载因子。
jdk8 对 HashMap 的优化。
java.util.EnumMap
一种键值属于枚举类型的映射表
java.util.TreeMap
一种键值有序排列的映射表，可排序
java.util.LinkedHashMap
一种可以记住键/值添加次序的映射表
java.util.WeakHashMap
一种其值无用武之地后可以被垃圾回收器回收的映射表
java.util.IdentityHashMap
一种用==，而不是用equals比较键值的映射表
java.util.concurrent.ConcurrentHashMap
A hash table supporting full concurrency of retrievals and high expected concurrency for updates.
java.util.concurrent.ConcurrentSkipListMap
Sorted, navigable, and concurrent.
java.util.HashTable
线程安全。
synchonized, no nulls.
Comparator vs. Comparable
Comparable 可比较的。Comparator 比较器。
Comparable 是排序接口，若一个类实现了 Comparable 接口，就意味着“该类支持排序”。而 Comparator 是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。
Comparable 相当于“内部比较器”，而 Comparator 相当于“外部比较器”。
如果对象的排序需要基于自然顺序，那么就使用 Comparable，而如果需要对不同对象的属性进行排序，那么就使用 Comparator.
Collections vs. Arrays
Arrsys 是数组的工具类。
Collections 是集合对象的工具类。
Wrapper Implementations
Synchronization Wrappers
Unmodifiable Wrappers
集合扩展
Apache Common Collections
Google Guava, com.google.common.collect
不可变集合
新集合类型
集合工具类
集合扩展工具类
Java 8 Collections API Features
Stream API
Lambda Expression and Functional interfaces
参考资料
Collections in Java - Everything You MUST Know
