This figure doesn’t show all inheritance information, such as, LinkedList also extends Deque interface;
The primary purpose is to choose a right data structure when do Java programming.
ENV
Java 8
HashMap
Base on bucket + list/red-black tree, if the list size of a bucket is greater than 8, the list will be converted to a red-black tree;
Don’t set a too high capacity if iteration performance is important, figure out a sufficiently large capacity will allow key-value pairs to be stored more efficiently than resizing the hash table;
Unordered, not thread-safe, fail-fast iterator(no guarantees);
Permits null keys and values;
LinkedHashMap
Like HashMap, but maintains a doubly-linked list to make the map entries are in insertion order;
A special constructor is provided to support LRU(Least recently used), calling the get and put methods will make the key appear in the tail of the doubly-linked list;
ConcurrentHashMap
Same functional specification as Hashtable;
Base on bucket + list/red-black tree, like HashMap, CAS algo, no read lock, don’t lock the entire table;
Iterators are designed to be used by only one thread at a time, the results of aggregate status methods including size, isEmpty, and containsValue are typically useful only when a map is not undergoing concurrent updates in other threads;
Resizing may be a relatively slow operation, estimate a appropriate hash table size;
Unordered, no null keys or values, thread-safe, fail-safe iterator;
ConcurrentSkipListMap
Base on SkipLists, space-time tradeoff, appropriate for massive data access;
It is sorted, natural order or defined by a Comparator, ascending key ordered views and their iterators are faster than descending ones;
The size method is inaccurate, the bulk operations putAll, equals, toArray, containsValue, and clear are not guaranteed to be performed atomically;
O(log(n)), thread-safe, no null keys or values;
TreeMap
Base on red-black tree, O(log(n)), ordered, not thread-safe, fail-fast iterator;
Natural order or defined by a Comparator;
WeakHashMap
Hash table based implementation of the Map interface;
An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use. The value objects in a WeakHashMap are held by ordinary strong references;
Permits null keys and values;
Not thread-safe, fail-fast iterator;
EnumMap
An array accessed with enum’s ordinal value as an index. There is no need to calculate hash codes or resolve collisions;
Enum maps are maintained in the natural order of their keys (the order in which the enum constants are declared);
Iterators returned by the collection views are weakly consistent: they will never throw ConcurrentModificationException and they may or may not show the effects of any modifications to the map that occur while the iteration is in progress;
No null keys, permits null values;
Not thread-safe, O(1);
LinkedList
A doubly-linked list, insertion and deletion are fast;
Not thread-safe, fail-fast iterator, permits null elements;
Also implements Deque interface, slower than ArrayDeque and need more memory for small objects. It can use an index to get an element, remove the current element during iteration and supports null elements, but ArrayDeque can’t;
ArrayList
Base on an array, has List interface
Access its elements in constant time by their index, inserting or removing an element may be slow if the array is huge and the inserted or removed element is close to the beginning of the list;
In most cases, however, ArrayList outperforms LinkedList. Even elements shifting in ArrayList, while being an O(n) operation, is implemented as a very fast System.arraycopy() call. It can even appear faster than the LinkedList‘s O(1) insertion which requires instantiating a Node object and updating multiple references under the hood. LinkedList also can have a large memory overhead due to a creation of multiple small Node objects;
Not thread-safe, fail-fast iterator;
CopyOnWriteArrayList
A variant of ArrayList, thread-safe;
Iterator provides a snapshot of the state of the list when the iterator was constructed. No synchronization is needed while traversing the iterator, this array never changes during the lifetime of the iterator. Element-changing operations on iterators themselves (remove, set, and add) are not supported;
Perfer reading. Element-changing operations are costly. Don’t block read, but read old value when writing. Be best suited for small size, read-only operations;
Permits null keys and values;
Stack
Use Deque’s implementations instead of it, such as ArrayDeque, ConcurrentLinkedDeque;
Vector
Use ArrayList or CopyOnWriteArrayList instead of it;
TreeSet
Based on TreeMap;
O(log(n)) time for the basic operations (add, remove and contains);
Natural order or defined by a Comparator, not thread-safe, fail-fast iterator;
HashSet
Based on HashMap;
Iterating over this set requires time proportional to the sum of the HashSet instance’s size (the number of elements) plus the “capacity” of the backing HashMap instance (the number of buckets). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important;
Permits null elements, unordered, not thread-safe, fail-fast iterator;
LinkedHashSet
HashSet + doubly-linked list;
It provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list, with one exception: Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity;
Has two parameters that affect its performance: initial capacity and load factor. They are defined precisely as for HashSet. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashSet, as iteration times for this class are unaffected by capacity;
Permits null elements, insertion-order, not thread-safe, fail-fast iterator;
CopyOnWriteArraySet
Set + CopyOnWriteArrayList;
ConcurrentSkipListSet
Based on ConcurrentSkipListMap, O(log(n));
EnumSet
Are represented internally as bit vectors;
The iterator returned by the iterator method traverses the elements in their natural order (the order in which the enum constants are declared);
The returned iterator is weakly consistent: it will never throw ConcurrentModificationException and it may or may not show the effects of any modifications to the set that occur while the iteration is in progress;
No null elements, not thread-safe, O(1);
BlockingQueue
Insert/Remove/Examine operations come in four forms: wait, throw an exception, return a special value(null or false), timeout;
Support the Collection interface;
Primarily for producer-consumer queues;
No null elements;
Thread-safe;
The bulk Collection operations addAll, containsAll, retainAll and removeAll are not necessarily performed atomically unless specified otherwise in an implementation. May fail after adding only some of the elements;
remove()/clear()/contains() functions are O(n);
ArrayBlockingQueue
A bounded BlockingQueue backed by an array, FIFO, thread-safe(ReentrantLock), producer-consumer model, optional fairness policy;
Enqueue and dequeue operations are O(1);
PriorityBlockingQueue
A unbounded BlockingQueue, array + priority heap, natural order or defined by a Comparator, thread-safe(ReentrantLock);
It is unbounded, doesn’t block put()/offer(e, time, unit), might cause OutOfMemoryError;
A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so results in ClassCastException);
iterator() is not guaranteed to traverse the elements in any particular order;
Enqueue and dequeue operations are O(log(n));
LinkedBlockingQueue
An optionally-bounded blocking queue based on linked nodes, FIFO, thread-safe(ReentrantLock);
Linked queues typically have higher throughput than array-based queues but less predictable performance in most concurrent applications;
Enqueue and dequeue operations are O(1);
DelayQueue
An unbounded blocking queue;
An element can only be taken when its delay has expired;
SynchronousQueue
A blocking queue in which each insert operation must wait for a corresponding remove operation by another thread, and vice versa;
Not have any internal capacity, acts as an empty collection, nothing to iterate;
Optional fairness policy to guarantee FIFO order;
LinkedTransferQueue
An unbounded TransferQueue(a BlockingQueue) based on linked nodes, producers may wait for consumers to receive elements;
FIFO, thread-safe, CAS algo;
size() is inaccurate;
Has a special function, transfer(), which transfers the specified element immediately if there exists a consumer already waiting to receive it (in take() or timed poll), else inserts the specified element at the tail of this queue and waits until the element is received by a consumer. In other worlds, if already have elements in the queue, transfer() will wait all of them to be received first;
LinkedBlockingQueue(unbounded) + SynchronousQueue(fairness) + ConcurrentLinkedQueue;
PriorityQueue
An unbounded priority queue based on a priority heap, but has an internal capacity governing the size of an array used to store the elements on the queue;
No null elements, not thread-safe;
Natural order or defined by a Comparator. The head of this queue is the least element with respect to the specified ordering. Natural ordering also does not permit insertion of non-comparable objects (doing so results in ClassCastException). if use a Comparator, the least element is depend on this Comparator, it may be the minimum or maximum if these elements are numbers;
iterator() is not guaranteed to traverse the elements in any particular order;
Enqueuing and dequeuing methods are O(log(n)), remove() and contains() are O(n), peek(), element() and size() are O(1);
ConcurrentLinkedQueue
An unbounded thread-safe queue based on linked nodes;
FIFO, no null elements, thread-safe, lock-free, CAS algo. The thread-safe is relative:
if( !queue.isEmpty() ) {
queue.poll(obj);
}No! need a lock
synchronized( queue ) {
if( !queue.isEmpty() ) {
queue.poll(obj);
}
}Iterators are weakly consistent;
The size method is inaccurate, the bulk operations addAll, removeAll, retainAll, containsAll, equals, and toArray are not guaranteed to be performed atomically;
LinkedBlockingDeque
An optionally-bounded blocking deque based on linked nodes, BlockingDeque extends BlockingQueue interface;
FIFO, LIFO, thread-safe(ReentrantLock), no null elements;
remove(), removeFirstOccurrence(), removeLastOccurrence(), contains(), iterator.remove(), and the bulk operations: O(n), others: O(1);
ArrayDeque
Resizable-array implementation of the Deque interface, has a circular array, the array length is powers of two;
FIFO, LIFO, no capacity restrictions, not thread-safe, fail-fast iterator, no null elements;
Faster than LinkedList when used as a queue. But allocate enough capacity before use it, otherwise need to enlarge the array and copy data;
As a stack instead of Stack;
ConcurrentLinkedDeque
An unbounded concurrent deque based on linked nodes;
FIFO, LIFO, no null elements, thread-safe, lock-free;
The size method is inaccurate, the bulk operations addAll, removeAll, retainAll, containsAll, equals, and toArray are not guaranteed to be performed atomically;
As a stack instead of Stack;