Essential cheat sheet for java beginners

In the shortest possible length, review the characteristics, implementation methods, and performance of all collections and concurrent collections. It is suitable for reading by all those who are "proficient in Java" but are not yet confident.

List

ArrayList

is implemented as an array. Save space, but arrays have capacity limits. When the limit is exceeded, the capacity will be increased by 50% and copied to a new array using System.arraycopy(), so it is best to give an estimate of the array size. By default, an array of size 10 is created the first time an element is inserted.

Access elements by array subscript – get(i)/set(i,e) has high performance, which is the basic advantage of arrays.

The performance of directly adding elements to the end of the array –add(e) is also high, but if you insert or delete elements by pressing the subscript –add(i,e), remove(i), remove(e), you need to use System. arraycopy() to move some of the affected elements, the performance becomes worse, which is a basic disadvantage.

LinkedList

is implemented as a doubly linked list. There is no capacity limit for linked lists, but the doubly linked list itself uses more space and requires additional linked list pointer operations.

Accessing elements by subscript – get(i)/set(i,e) will tragically traverse the linked list and move the pointer into place (if i > half the size of the array, it will be moved from the end).

When inserting or deleting elements, you can just modify the pointers of the previous and next nodes, but you still need to traverse part of the linked list pointers to move to the position pointed by the subscript. Only operations at both ends of the linked list – add(), addFirst(), removeLast( ) or use remove() on iterator() to avoid pointer movement.

CopyOnWriteArrayList

Concurrency optimized ArrayList. Use the CopyOnWrite strategy to first copy a snapshot to modify it, and then let the internal pointer point to the new array after the modification.

Because modifications to snapshots are invisible to read operations, there are only write locks and no read locks. In addition to the expensive cost of replication, it is typically suitable for scenarios where there is more reading and less writing. If the update frequency is high or the array is large, it is better to use Collections.synchronizedList(list) and use the same lock for all operations to ensure thread safety.

The addIfAbsent(e) method has been added, which will traverse the array to check whether the element already exists. The performance is not very good as you can imagine.

Supplement

No matter which implementation is implemented, returning subscripts by value – contains(e), indexOf(e), remove(e) requires traversing all elements for comparison, and the performance is not very good as you can imagine.

There is no SortedList sorted by element value, and there is no lock-free ConcurrentLinkedList in the thread-safe class. When you make do with the equivalent classes in Set and Queue, you will lack some List-specific methods.

Map

HashMap

Hash bucket array implemented with Entry[] array. Use the hash value of Key to modulo the size of the bucket array to get the array subscript.

When inserting elements, if two keys fall into the same bucket (for example, hash values ​​1 and 17 belong to the first hash bucket after modulo 16), Entry uses a next attribute to implement multiple Entries in a one-way linked list Storage, the Entry entered later in the bucket will point next to the current Entry in the bucket.

When looking for a key with a hash value of 17, first locate the first hash bucket, then traverse all the elements in the bucket using a linked list, and compare their key values ​​one by one.

When the number of Entries reaches 75% of the number of buckets (many articles say that the number of buckets used has reached 75%, but it is not true based on the code), the bucket array will be expanded exponentially and all the original Entries will be reallocated, so this is also the most Good to have an estimate.

It will be faster to use bitwise operation (hash & (arrayLength-1)) to take the modulus, so the size of the array is always 2 to the Nth power. If you give an initial value at will, such as 17, it will be converted to 32. The default initial value when an element is first placed is 16.

Iterator() traverses along the hash bucket array, which seems to be out of order.

In JDK8, a new threshold with a default value of 8 is added. When the Entry in a bucket exceeds the threshold, it will not be stored in a one-way linked list but in a red-black tree to speed up Key search.

LinkedHashMap

Extend HashMap to add the implementation of doubly linked list, which is known as the most memory-consuming data structure. When iterator() is supported, the entries are sorted according to the insertion order (but updates are not counted. If the accessOrder attribute is set to true, all read and write accesses are counted).

The implementation is to add attribute before/after pointers to the Entry, and add itself in front of the Header Entry when inserting. If all read and write accesses need to be sorted, the before/after of the front and rear Entries must be spliced ​​together to delete themselves in the linked list.

TreeMap

is implemented as a red-black tree. When iterator() is supported, it is sorted by Key value. It can be sorted in ascending order of Key that implements the Comparable interface, or controlled by the incoming Comparator. It is conceivable that the cost of inserting/deleting elements in the tree must be greater than that of HashMap.

Supports SortedMap interface, such as firstKey(), lastKey() to obtain the largest and smallest key, or sub(fromKey, toKey), tailMap(fromKey) to cut a certain segment of the Map.

ConcurrentHashMap

Concurrency optimized HashMap has 16 write locks by default (more can be set), which effectively disperses the probability of blocking and has no read locks.
The data structure is Segment[]. Inside the Segment is the hash bucket array, and each Segment has a lock. Key first calculates which Segment it is in, and then calculates which hash bucket it is in.

Supports ConcurrentMap interface, such as putIfAbsent(key, value) and the opposite replace(key, value) and replace(key, oldValue, newValue) that implements CAS.

There is no read lock because the put/remove action is an atomic action (for example, put is an assignment operation to an array element/Entry pointer), and the read operation will not see the intermediate state of an update action.

ConcurrentSkipListMap

JDK6’s new concurrency-optimized SortedMap is implemented with SkipList. SkipList is a simplified alternative to red-black trees and a popular ordered set algorithm. Please refer to the introductory tutorial due to space limitations. The Concurrent package uses it because it supports CAS-based lock-free algorithms, while red-black trees do not have good lock-free algorithms.

It’s very special, its size() cannot be adjusted casually, it will be traversed for statistics.

Supplement

Regarding null, HashMap and LinkedHashMap are arbitrary. When TreeMap does not set a Comparator, the key cannot be null; the value of ConcurrentHashMap cannot be null in JDK7 (why is this?), and neither the key nor the value can be null in JDK8. ;ConcurrentSkipListMap is that the key and value in all JDK cannot be null.

Set

Set is almost always implemented internally using a Map, because the KeySet in the Map is a Set, and the value is a false value, all using the same Object. Set's characteristics also inherit those of the internal Map implementation.

HashSet: Internally is a HashMap.
LinkedHashSet: Internally is LinkedHashMap.
TreeSet: Internally is the SortedSet of TreeMap.
ConcurrentSkipListSet: Internally, it is a concurrency-optimized SortedSet of ConcurrentSkipListMap.
CopyOnWriteArraySet: Internally, it is a concurrently optimized Set of CopyOnWriteArrayList. Its addIfAbsent() method is used to achieve element deduplication. As mentioned above, the performance of this method is very average.
Addition: It seems that a ConcurrentHashSet is missing. There should be a simple implementation of ConcurrentHashMap internally, but JDK does not provide it. Jetty has sealed one by itself, and Guava directly uses java.util.Collections.newSetFromMap(new ConcurrentHashMap()) to implement it.

Queue

Queue is a List that goes in and out at both ends, so it can also be implemented with an array or linked list.

–Ordinary Queue–

LinkedList

Yes, LinkedList implemented as a doubly linked list is both a List and a Queue. It is the only Queue that allows nulls to be placed.

ArrayDeque

A bidirectional Queue implemented with a circular array. Size is a multiple of 2, default is 16.

Ordinary arrays can only quickly add elements at the end. In order to support FIFO and quickly remove elements from the head of the array, you need to use a loop array: there are two subscripts at the head and tail: when an element is popped, the head subscript is incremented; join element, if the end of the array space has been reached, the element is circularly assigned to array 0, and the tail subscript points to 0. When the next element is inserted, it is assigned to array [1], and the tail subscript points to 1. If the subscript at the end of the queue catches up with the head of the queue, it means that all the space in the array has been used up, and the array will be doubled.

PriorityQueue

The priority queue implemented using a binary heap is no longer a FIFO but is dequeued based on the Comparable interface implemented by the element or the comparison result passed into the Comparator. The smaller the value, the higher the priority and the earlier it is dequeued. Team. But note that the return of iterator() will not be sorted.

– Thread-safe queue –

ConcurrentLinkedQueue/ConcurrentLinkedDeque

Unbounded concurrency optimized Queue, based on linked list, implements a lock-free algorithm that relies on CAS.

The structure of ConcurrentLinkedQueue is a one-way linked list and two pointers, head/tail. Because when joining the queue, you need to modify the next pointer of the tail element of the queue, and modify the tail to point to the newly joined element. The two CAS actions cannot be atomic, so special actions are required. For the algorithm, see the introductory tutorial due to space limitations.

PriorityBlockingQueue

Unbounded concurrency optimized PriorityQueue is also based on binary heap. Use a public read-write lock. Although the BlockingQueue interface is implemented, it does not have any blocking queue characteristics. It will automatically expand when the space is insufficient.

DelayQueue

contains a PriorityQueue internally, which is also unbounded. The element needs to implement the Delayed interface, and each time it is called, it needs to return how long it is before the trigger time. If it is less than 0, it means it is time to trigger.
When pulling(), peek() will be used to check the element at the head of the queue to check whether the trigger time has been reached. ScheduledThreadPoolExecutor uses a similar structure.

– Thread-safe blocking queue – The queue length of

BlockingQueue is limited to ensure that the speed of producers and consumers will not differ too far and avoid memory exhaustion. The queue length cannot be changed after it is set. When the queue is full when joining the queue, or the queue is empty when leaving the queue, the effects of different functions are shown in the table below:

ArrayBlockingQueue

Fixed-length concurrency optimized BlockingQueue, implemented based on circular arrays. There is a common read-write lock and two Conditions, notFull and notEmpty, to manage the blocking state when the queue is full or empty.

LinkedBlockingQueue/LinkedBlockingDeque

You can choose a long concurrency-optimized BlockingQueue, which is implemented based on a linked list, so you can set the length to Integer.MAX_VALUE. Taking advantage of the characteristics of the linked list, the two locks takeLock and putLock are separated, and notEmpty and notFull are used to continue to manage the blocking state when the queue is full or empty.

Supplement

JDK7 has a LinkedTransferQueue. The transfer(e) method ensures that the elements put in by the Producer are taken away by the Consumer and returned. It is better than SynchronousQueue. You should learn it when you have time.