Java 中的集合

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

CollectionImplementations

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

底层数据结构是红黑树，Treset不仅保证了元素的独特性，也保证了元素的顺序。

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 expens­ive­(sh­ift­), not ordered.

优点是适合随机搜索和遍历，缺点是不适合插入和删除。

动态扩容。

java.util.LinkedList

一个有序的序列，可以有效地插入和删除任何位置的操作，实现双向链表。

sequence access­,ad­d/r­emove 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 ArrayL­ist, but synchr­oni­zed­, 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

参考资料

Trail: Collections

Collections in Java - Everything You MUST Know

Comparable和Comparator在Java中的区别小结

阻塞队列，有边界队列，无边界队列