In as short a space as possible, go through the characteristics, implementation methods, and performance of all collections and concurrent collections. Suitable for anyone who claims to be "proficient in Java" but is not quite confident yet.
ListArrayList
Implemented with an array. Saves space, but arrays have capacity limits. When the limit is exceeded, capacity is increased by 50%, and System.arraycopy() is used to copy to a new array, so it is best to provide an estimated array size. By default, an array of size 10 is created when the first element is inserted.
Accessing elements by array index – get(i)/set(i,e) has high performance; this is the basic advantage of arrays.
Adding an element directly at the end of the array – add(e) also has high performance. But if you insert or delete by index – add(i,e), remove(i), remove(e) – you need to use System.arraycopy() to move the affected elements, so performance degrades; this is the basic disadvantage.
LinkedList
Implemented as a doubly linked list. The linked list has no capacity limit, but the doubly linked list itself uses more space and also requires extra linked list pointer operations.
Accessing elements by index – get(i)/set(i,e) unfortunately requires traversing the linked list to move the pointer into position (if i > half the list size, it starts moving from the tail).
When inserting or deleting elements, you only need to modify the pointers of the preceding and following nodes, but you still have to traverse part of the linked list to move to the position indicated by the index. Only operations at the two ends of the list – add(), addFirst(), removeLast(), or remove() on iterator() – can avoid pointer movement.
CopyOnWriteArrayList
Concurrency-optimized ArrayList. Uses the CopyOnWrite strategy: when modifying, first copy a snapshot to modify, and after the modification, let the internal pointer point to the new array.
Because modifications to the snapshot are invisible to read operations, there is only a write lock and no read lock. Coupled with the expensive cost of copying, it is typically suitable for read-heavy, write-light scenarios. If the update frequency is high or the array is large, Collections.synchronizedList(list) is better, using the same lock for all operations to ensure thread safety.
Adds an addIfAbsent(e) method, which traverses the array to check whether the element already exists; as can be imagined, the performance is not very good.
Supplement
Regardless of the implementation, finding the index by value – contains(e), indexOf(e), remove(e) – requires traversing all elements for comparison; as can be imagined, the performance is not very good.
There is no SortedList sorted by element value, and there is no ConcurrentLinkedList with a lock-free algorithm among the thread-safe classes. When you make do with the equivalent classes in Set and Queue, you will miss some List-specific methods.
Map
HashMap
A hash bucket array implemented as an Entry[] array. Use the Key's hash value modulo the bucket array size to get the array index.
When inserting an element, if two Keys fall into the same bucket (for example, hash values 1 and 17 both belong to the first hash bucket after modulo 16), Entry uses a next property to store multiple Entries in a singly linked list. The Entry that enters the bucket later points its next to the bucket's current Entry.
When looking up a Key with hash value 17, first locate the first hash bucket, then traverse all elements in the bucket via the linked list, comparing their key values one by one.
When the number of Entries reaches 75% of the number of buckets (many articles say the number of used buckets reaches 75%, but looking at the code it is not), the bucket array is expanded exponentially, and all original Entries are rehashed. So it is also best to have an estimated value here.
Using the bitwise operation (hash & (arrayLength-1)) for modulo is faster, so the array size is always a power of 2. If you casually give an initial value such as 17, it will be converted to 32. By default, the initial value when the first element is put in is 16.
When iterating with iterator(), it traverses along the hash bucket array, which looks unordered.
In JDK 8, a new threshold defaults to 8. When the Entries in a bucket exceed the threshold, they are stored in a red-black tree instead of a singly linked list to speed up Key lookup.
LinkedHashMap
Extends HashMap by adding a doubly linked list implementation; it is said to be the most memory-consuming data structure. It supports sorting by Entry insertion order when iterating with iterator() (but updates don't count; if the accessOrder property is set to true, then all read and write accesses count).
In the implementation, before/after pointers are added to Entry. When inserting, you add yourself before the Header Entry. If all read and write accesses need to be ordered, you also need to splice the before/after pointers of the preceding and following Entries to remove yourself from the linked list.
TreeMap
Implemented with a red-black tree. Due to space limitations, seeIntroductory TutorialSupports sorting by Key value when iterating with iterator(); it can sort in ascending order by Keys that implement the Comparable interface, or be controlled by a passed-in Comparator. As can be imagined, the cost of inserting/deleting elements on the tree is definitely greater than that of HashMap.
Supports the SortedMap interface, such as firstKey(), lastKey() to get the smallest and largest keys, or sub(fromKey, toKey), tailMap(fromKey) to slice a segment of the Map.
ConcurrentHashMap
Concurrency-optimized HashMap. By default, it has 16 write locks (more can be set), effectively distributing the probability of blocking, and there is no read lock.
The data structure is Segment[]. Inside Segment is the hash bucket array. Each Segment has one lock. The Key first calculates which Segment it is in, then calculates which hash bucket it is in.
Supports the ConcurrentMap interface, such as putIfAbsent(key, value), the opposite replace(key, value), and replace(key, oldValue, newValue) which implements CAS.
There is no read lock because put/remove actions are atomic actions (for example, put is an assignment operation on an array element/Entry pointer); read operations will not see an intermediate state of an update action.
ConcurrentSkipListMap
Concurrency-optimized SortedMap added in JDK 6, implemented with SkipList. SkipList is a simplified alternative to red-black trees and a popular ordered-collection algorithm. Due to space limitations, seeIntroductory TutorialThe Concurrent package chose it because it supports CAS-based lock-free algorithms, while red-black trees do not have good lock-free algorithms.
Quite special: its size() cannot be casually called; it traverses to count.
Supplement
Regarding null: HashMap and LinkedHashMap are lenient. TreeMap cannot have null keys when no Comparator is set. In ConcurrentHashMap in JDK 7, value cannot be null (why is that?); in JDK 8, neither key nor value can be null. For ConcurrentSkipListMap, in all JDK versions, neither key nor value can be null.
Set
Almost all Sets are implemented internally with a Map, because the KeySet in a Map is a Set, and the value is a dummy value, all using the same Object. Set characteristics also inherit those of the internal Map implementations.
- HashSet: internally is a HashMap.
- LinkedHashSet: internally is a LinkedHashMap.
- TreeSet: internally is a SortedSet implemented with TreeMap.
- ConcurrentSkipListSet: internally is a concurrency-optimized SortedSet implemented with ConcurrentSkipListMap.
- CopyOnWriteArraySet: internally is a concurrency-optimized Set implemented with CopyOnWriteArrayList, using its addIfAbsent() method to deduplicate elements. As mentioned earlier, this method's performance is mediocre.
Supplement: It seems a ConcurrentHashSet is missing. There should have been a simple implementation using ConcurrentHashMap internally, but the JDK just didn't provide one. Jetty wrapped one itself, while Guava directly uses java.util.Collections.newSetFromMap(new ConcurrentHashMap()) to implement it.
Queue
Queue is a List where elements enter and exit at the two ends, so it can also be implemented using an array or a linked list.
– Ordinary Queue –
LinkedList
Yes, LinkedList implemented with a doubly linked list is both a List and a Queue. It is the only Queue that allows null.
ArrayDeque
A bidirectional Queue implemented with a circular array. The size is a multiple of 2, and the default is 16.
An ordinary array can only quickly add elements at the end. To support FIFO and quickly take elements from the head, a circular array is needed: there are two indices, head and tail. When popping an element, the head index increments. When adding an element, if the end of the array space has been reached, the element is cyclically assigned to array
PriorityQueue
Priority queue implemented with a binary heap; seeIntroductory TutorialIt is no longer FIFO; instead, elements dequeue according to the comparison result of the Comparable interface implemented by the element or the passed-in Comparator. The smaller the value, the higher the priority, and the earlier it dequeues. But note that its iterator() return does not sort.
–Thread-safe queues–
ConcurrentLinkedQueue/ConcurrentLinkedDeque
Unbounded concurrent-optimized Queue, based on a linked list, implementing a lock-free algorithm relying on CAS.
The structure of ConcurrentLinkedQueue is a singly linked list with head/tail pointers. Because enqueuing requires two CAS operations—modifying the next pointer of the tail element and updating tail to point to the new element—which cannot be atomic, a special algorithm is needed. Due to space limitations, seeGetting Started Tutorial。
PriorityBlockingQueue
Unbounded concurrent-optimized PriorityQueue, also based on a binary heap. It uses a common read-write lock. Although it implements the BlockingQueue interface, it actually has no blocking queue characteristics; it automatically expands when space is insufficient.
DelayQueue
Internally contains a PriorityQueue, also unbounded. Elements must implement the Delayed interface. Each call must return how long remains until the trigger time; less than 0 means it should be triggered.
When calling pull(), it uses peek() to inspect the head element and check whether the trigger time has been reached. ScheduledThreadPoolExecutor uses a similar structure.
–Thread-safe blocking queues–
The length of a BlockingQueue is limited to ensure that the producer and consumer speeds do not differ too much, avoiding memory exhaustion. Once set, the queue length cannot be changed. When the queue is full during enqueue, or empty during dequeue, the effects of different methods are shown in the table below:
ArrayBlockingQueue
Fixed-length concurrent-optimized BlockingQueue, implemented based on a circular array. It has a common read-write lock and two Conditions, notFull and notEmpty, managing the blocking states when the queue is full or empty.
LinkedBlockingQueue/LinkedBlockingDeque
Optionally bounded concurrent-optimized BlockingQueue, implemented based on a linked list, so the length can be set to Integer.MAX_VALUE. Taking advantage of the characteristics of a linked list, it separates the takeLock and putLock locks, and continues to use notEmpty and notFull to manage the blocking states when the queue is full or empty.
Supplement
JDK7 has oneLinkedTransferQueueThe transfer(e) method guarantees that the element put by Producer is returned after Consumer takes it away. It is better than SynchronousQueue; I should study it when I have time.
Source: http://www.topthink.com/topic/11679.html