Basic chapter
Key points of basic part: algorithm, data structure and basic design mode
1. Binary search
requirement
 Be able to describe the binary search algorithm in your own language
 Able to write binary search code
 Be able to answer some changed test methods
Algorithm description

Premise: there is A sorted array A (assuming it is ready)

Define the left bound L and the right bound R, determine the search range, and cycle through binary search (steps 3 and 4)

Get intermediate index M = Floor((L+R) /2)

The value A[M] of the intermediate index is compared with the value T to be searched
① A[M] == T means to find and return the intermediate index
② A [M] > T, other elements on the right side of the intermediate value are greater than T, so there is no need to compare. Look for the left side of the intermediate index, set M  1 as the right boundary, and look again
③ A [M] < T, other elements on the left side of the middle value are less than t, so there is no need to compare. Look on the right side of the middle index, set M + 1 as the left boundary, and look again

When l > R, it means that it is not found and the cycle should be ended
For a more vivid description, please refer to: binary_search.html
Algorithm implementation
public static int binarySearch(int[] a, int t) { int l = 0, r = a.length  1, m; while (l <= r) { m = (l + r) / 2; if (a[m] == t) { return m; } else if (a[m] > t) { r = m  1; } else { l = m + 1; } } return 1; }
Test code
public static void main(String[] args) { int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50}; int target = 47; int idx = binarySearch(array, target); System.out.println(idx); }
Solve integer overflow problem
When l and r are large, l + r may exceed the integer range, resulting in operation errors. There are two solutions:
int m = l + (r  l) / 2;
Another is:
int m = (l + r) >>> 1;
Other test methods

There is an ordered table of 1,5,8,11,19,22,31,35,40,45,48,49,50. When the binary search value is 48, the number of times to compare for successful search

When using dichotomy to find element 81 in sequence 1,4,6,7,15,33,39,50,64,78,75,81,89,96, it needs to be compared () times

How many times do you need to compare a number of binary searches in an array with 128 elements
For the first two questions, remember a brief judgment formula: odd dichotomy takes the middle, even dichotomy takes the middle left. For the latter topic, you need to know the formula:
n = l o g 2 N = l o g 10 N / l o g 10 2 n = log_2N = log_{10}N/log_{10}2 n=log2N=log10N/log102
Where n is the number of searches and N is the number of elements
2. Bubble sorting
requirement
 Be able to describe bubble sorting algorithm in your own language
 Able to write bubble sorting code
 Understand some optimization methods of bubble sorting
Algorithm description
 Compare the sizes of two adjacent elements in the array in turn. If a [J] > a [J + 1], exchange two elements. Comparing both elements is called a round of bubbling, and the result is that the largest element is ranked last
 Repeat the above steps until the entire array is in order
For a more vivid description, please refer to: bubble_sort.html
Algorithm implementation
public static void bubble(int[] a) { for (int j = 0; j < a.length  1; j++) { // A round of bubbling boolean swapped = false; // Has an exchange occurred for (int i = 0; i < a.length  1  j; i++) { System.out.println("Comparison times" + i); if (a[i] > a[i + 1]) { Utils.swap(a, i, i + 1); swapped = true; } } System.out.println("The first" + j + "Wheel bubbling" + Arrays.toString(a)); if (!swapped) { break; } } }
 Optimization point 1: after each round of bubbling, the inner circulation can be reduced once
 Optimization point 2: if there is no exchange in a round of bubbling, it means that all data are in order and the outer cycle can be ended
Further optimization
public static void bubble_v2(int[] a) { int n = a.length  1; while (true) { int last = 0; // Indicates the location of the last exchange index for (int i = 0; i < n; i++) { System.out.println("Comparison times" + i); if (a[i] > a[i + 1]) { Utils.swap(a, i, i + 1); last = i; } } n = last; System.out.println("Round bubbling" + Arrays.toString(a)); if (n == 0) { break; } } }
 During each round of bubbling, the last exchange index can be used as the comparison times of the next round of bubbling. If this value is zero, it means that the whole array is in order. Just exit the outer loop directly
3. Select Sorting
requirement
 Be able to describe the selection sorting algorithm in your own language
 Ability to compare selection sort with bubble sort
 Understanding unstable sorting and stable sorting
Algorithm description

The unsorted subset and the unsorted subset are divided into the smallest subset and the unsorted subset

Repeat the above steps until the entire array is in order
For a more vivid description, please refer to: selection_sort.html
Algorithm implementation
public static void selection(int[] a) { for (int i = 0; i < a.length  1; i++) { // i represents the target index to which the smallest element of each round of selection is to be exchanged int s = i; // Index representing the smallest element for (int j = s + 1; j < a.length; j++) { if (a[s] > a[j]) { // The j element is smaller than the S element. Update s s = j; } } if (s != i) { swap(a, s, i); } System.out.println(Arrays.toString(a)); } }
 Optimization point: in order to reduce the number of exchanges, the smallest index can be found in each round, and the elements can be exchanged at the end of each round
Comparison with bubble sorting

The average time complexity of both is O ( n 2 ) O(n^2) O(n2)

Selection sorting is generally faster than bubbling because it has less exchange times

However, if the set order is high, bubbling is better than selection

Bubbling belongs to stable sorting algorithm, while selection belongs to unstable sorting
 Stable sorting refers to sorting multiple times by different fields in the object without disturbing the order of elements with the same value
 Unstable sorting is the opposite
Stable sort and unstable sort
System.out.println("=================instable================"); Card[] cards = getStaticCards(); System.out.println(Arrays.toString(cards)); selection(cards, Comparator.comparingInt((Card a) > a.sharpOrder).reversed()); System.out.println(Arrays.toString(cards)); selection(cards, Comparator.comparingInt((Card a) > a.numberOrder).reversed()); System.out.println(Arrays.toString(cards)); System.out.println("=================stable================="); cards = getStaticCards(); System.out.println(Arrays.toString(cards)); bubble(cards, Comparator.comparingInt((Card a) > a.sharpOrder).reversed()); System.out.println(Arrays.toString(cards)); bubble(cards, Comparator.comparingInt((Card a) > a.numberOrder).reversed()); System.out.println(Arrays.toString(cards));
They are sorted by design and color first( ♠♥♣♦)， Then sort by number (AKQJ...)

When the unstable sorting algorithm sorts by numbers, it will disrupt the original color order of the same value
[[♠7], [♠2], [♠4], [♠5], [♥2], [♥5]] [[♠7], [♠5], [♥5], [♠4], [♥2], [♠2]]
original ♠ 2 in front ♥ After 2, according to the number, their position changed

When sorting by numbers, the stable sorting algorithm will retain the original Decor order of the same value, as shown below ♠ 2 and ♥ The relative position of 2 remains unchanged
[[♠7], [♠2], [♠4], [♠5], [♥2], [♥5]] [[♠7], [♠5], [♥5], [♠4], [♠2], [♥2]]
4. Insert sort
requirement
 Be able to describe the insertion sorting algorithm in your own language
 Ability to compare insert sort with select sort
Algorithm description

The array is divided into two areas, sorted area and unordered area. In each round, the first element is taken out of the unordered area and inserted into the sorted area (the order needs to be guaranteed)

Repeat the above steps until the entire array is in order
For a more vivid description, please refer to: insertion_sort.html
Algorithm implementation
// Modified the code to be consistent with Hill sorting public static void insert(int[] a) { // i represents the index of the element to be inserted for (int i = 1; i < a.length; i++) { int t = a[i]; // Represents the value of the element to be inserted int j = i; System.out.println(j); while (j >= 1) { if (t < a[j  1]) { // j1 is the previous element index. If > t, move back a[j] = a[j  1]; j; } else { // If j1 has been < = t, then j is the insertion position break; } } a[j] = t; System.out.println(Arrays.toString(a) + " " + j); } }
Compare with selection sort

The average time complexity of both is O ( n 2 ) O(n^2) O(n2)

In most cases, insertion is slightly better than selection

The time complexity of ordered set insertion is O ( n ) O(n) O(n)

Insertion belongs to stable sorting algorithm, while selection belongs to unstable sorting
Tips
Insertion sorting is usually despised by students. In fact, its position is very important. For sorting with small amount of data, insert sorting will be preferred
5. Hill sort
requirement
 Be able to describe Hill sorting algorithm in your own language
Algorithm description

First, select a gap sequence, such as (n/2, n/4... 1), where n is the length of the array

In each round, the elements with equal gaps are regarded as a group, and the elements in the group are inserted and sorted for two purposes
① A small number of elements are inserted and sorted quickly
② Make elements with larger values in the group move to the rear faster

When the gap decreases gradually until it is 1, the sorting can be completed
For a more vivid description, please refer to: shell_sort.html
Algorithm implementation
private static void shell(int[] a) { int n = a.length; for (int gap = n / 2; gap > 0; gap /= 2) { // i represents the index of the element to be inserted for (int i = gap; i < n; i++) { int t = a[i]; // Represents the value of the element to be inserted int j = i; while (j >= gap) { // Insert and sort with the last gap element every time if (t < a[j  gap]) { // If gapj is the last index, move it back a[j] = a[j  gap]; j = gap; } else { // If j1 has been < = t, then j is the insertion position break; } } a[j] = t; System.out.println(Arrays.toString(a) + " gap:" + gap); } } }
reference material
 https://en.wikipedia.org/wiki/Shellsort
6. Quick sort
requirement
 Be able to describe the quick sort algorithm in your own language
 Master one of the handwritten onesided loop and twosided loop codes
 Can explain the characteristics of fast exhaust
 Understand the performance comparison of lomoto and hall zoning schemes
Algorithm description
 Each round of sorting selects a pivot for zoning
 Let the elements smaller than the reference point enter one partition, and the elements larger than the reference point enter another partition
 When the partition is completed, the position of the datum element is its final position
 Repeat the above process in the sub partition until the number of elements in the sub partition is less than or equal to 1, which reflects the idea of divide and rule( divideandconquer)
 As can be seen from the above description, a key lies in the partition algorithm. Common partition schemes include lomoto partition scheme, bilateral circular partition scheme and hall partition scheme
For a more vivid description, please refer to: quick_sort.html
Unilateral circular fast exhaust (lomuto lomuto zoning scheme)

Select the rightmost element as the datum element

The j pointer is responsible for finding elements smaller than the reference point. Once found, it will be exchanged with i

The i pointer maintains a boundary smaller than the benchmark element and is also the target index for each exchange

The last datum point is exchanged with i, i is the partition position
public static void quick(int[] a, int l, int h) { if (l >= h) { return; } int p = partition(a, l, h); // p index value quick(a, l, p  1); // The range of the left partition is determined quick(a, p + 1, h); // The range of the left partition is determined } private static int partition(int[] a, int l, int h) { int pv = a[h]; // Datum element int i = l; for (int j = l; j < h; j++) { if (a[j] < pv) { if (i != j) { swap(a, i, j); } i++; } } if (i != h) { swap(a, h, i); } System.out.println(Arrays.toString(a) + " i=" + i); // The return value represents the correct index of the benchmark element, which is used to determine the boundary of the next round of partition return i; }
Bilateral circular fast exhaust (not completely equivalent to hoare hall zoning scheme)
 Select the leftmost element as the datum element
 The j pointer is responsible for finding elements smaller than the benchmark from right to left, and the i pointer is responsible for finding elements larger than the benchmark from left to right. Once the two are found, they are exchanged until i and j intersect
 Finally, the datum point is exchanged with i (at this time, i and j are equal), i is the partition position
main points

The datum point is on the left, and j first and then i

while( i < j && a[j] > pv ) j–

while ( i < j && a[i] <= pv ) i++
private static void quick(int[] a, int l, int h) { if (l >= h) { return; } int p = partition(a, l, h); quick(a, l, p  1); quick(a, p + 1, h); } private static int partition(int[] a, int l, int h) { int pv = a[l]; int i = l; int j = h; while (i < j) { // j find the small one from the right while (i < j && a[j] > pv) { j; } // i find the big one from the left while (i < j && a[i] <= pv) { i++; } swap(a, i, j); } swap(a, l, j); System.out.println(Arrays.toString(a) + " j=" + j); return j; }
Fast exhaust characteristics

The average time complexity is O ( n l o g 2 n ) O(nlog_2n ) O(nlog2 n), worst time complexity O ( n 2 ) O(n^2) O(n2)

When the amount of data is large, the advantage is very obvious

It belongs to unstable sorting
Lomoto zoning scheme vs hall zoning scheme
 On average, hall moves three times less than lomoto
 https://qastack.cn/cs/11458/quicksortpartitioninghoarevslomuto
Supplementary code description
 day01.sort.QuickSort3 demonstrates the improved doublesided fast row of hole method, with fewer comparisons
 day01.sort.QuickSortHoare demonstrates the implementation of hall partitioning
 day01. sort. Comparison of movement times of lomutovshoare for four partitions
7. ArrayList
requirement
 Master the capacity expansion rules of ArrayList
Capacity expansion rules

ArrayList() will use an array with a length of zero

ArrayList(int initialCapacity) uses an array of the specified capacity

Public ArrayList (collection <? Extensions E > c) uses the size of c as the array capacity

add(Object o) the first capacity expansion is 10, and the second capacity expansion is 1.5 times of the last capacity

When addAll(Collection c) has no elements, it is expanded to math Max (10, actual number of elements), math when there are elements Max (1.5 times the original capacity, actual number of elements)
The fourth point must be known, and the other points depend on personal circumstances
Tips
 See day01 for test code list. Testarraylist, not listed here
 It should be noted that in the example, reflection is used to more intuitively reflect the capacity expansion characteristics of ArrayList, but JDK 9 has made more restrictions on reflection due to the influence of modularity. It is necessary to add VM parameter  add opens Java. When running the test code base/java. Util = allunnamed can pass the operation. The following examples have the same problem
Code description
 day01.list.TestArrayList#arrayListGrowRule demonstrates the capacity expansion rule of the add(Object) method. The input parameter n represents the length of the array after capacity expansion
8. Iterator
requirement
 Master what is fail fast and fail safe
Fail fast and fail safe

ArrayList is a typical representative of fail fast. It cannot be modified while traversing. It will fail as soon as possible

CopyOnWriteArrayList is a typical representative of fail safe. It can be modified while traversing. The principle is readwrite separation
Tips
 See day01 for test code list. Failfastvsfailsafe, not listed here
9. LinkedList
requirement
 Be able to clarify the difference between LinkedList and ArrayList, and pay attention to correcting some wrong cognition
LinkedList
 Based on bidirectional linked list, no continuous memory is required
 Random access is slow (to traverse along the linked list)
 High performance of head and tail insertion and deletion
 Too much memory
ArrayList
 Based on array, continuous memory is required
 Random access fast (refers to access according to subscript)
 The performance of tail insertion and deletion is OK. The insertion and deletion of other parts will move data, so the performance will be low
 Can use cpu cache, locality principle
Code description
 day01.list.ArrayListVsLinkedList#randomAccess vs random access performance
 day01.list.ArrayListVsLinkedList#addMiddle compares the performance of inserting into the middle
 day01.list.ArrayListVsLinkedList#addFirst compare header insertion performance
 day01.list.ArrayListVsLinkedList#addLast compares tail insertion performance
 day01.list.ArrayListVsLinkedList#linkedListSize printing a LinkedList takes up memory
 day01.list.ArrayListVsLinkedList#arrayListSize printing an ArrayList takes up memory
10. HashMap
requirement
 Master the basic data structure of HashMap
 Master tree
 Understand the index calculation method, the meaning of secondary hash and the influence of capacity on index calculation
 Master put process, capacity expansion and capacity expansion factors
 Understand the possible problems caused by concurrent use of HashMap
 Understand key's design
1) Basic data structure
 1.7 array + linked list
 1.8 array + (linked list  red black tree)
For a more vivid demonstration, see hash demo Jar. You need the environment above jdk14 to run. Enter the jar package directory and execute the following command
java jar addexports java.base/jdk.internal.misc=ALLUNNAMED hashdemo.jar
2) Treeing and degradation
Tree meaning
 Red black tree is used to avoid DoS attack and prevent the performance degradation of linked list when it is too long. Tree should be an accident and a minimum guarantee strategy
 The time complexity of searching and updating hash table is O ( 1 ) O(1) O(1), and the time complexity of updating the red black tree is O ( l o g 2 n ) O(log_2n ) O(log2 n). TreeNode also takes up more space than ordinary nodes. If it is not necessary, try to use a linked list
 If the hash value is random enough, it will be distributed according to Poisson distribution in the hash table. When the load factor is 0.75, the probability of the linked list with a length of more than 8 is 0.00000006. The tree threshold value of 8 is selected to make the tree probability small enough
Tree rule
 When the length of the linked list exceeds the treelization threshold of 8, first try to expand the capacity to reduce the length of the linked list. If the array capacity is > = 64, the treelization will be carried out
Degradation rule
 Case 1: during capacity expansion, if the number of tree elements is < = 6 when splitting the tree, the linked list will be degraded
 Case 2: when removing a tree node, if root and root left,root.right,root.left. If one of the left is null, it will also degenerate into a linked list
3) Index calculation
Index calculation method
 First, calculate the hashCode() of the object
 Then call the hash() method of HashMap for secondary hashing
 Quadratic hash() is used to synthesize highorder data and make hash distribution more uniform
 Finally & (capacity – 1) gets the index
What is the capacity of an array to the power of n
 It is more efficient to calculate the index: if it is the nth power of 2, you can use bit and operation instead of modulus
 It is more efficient to recalculate the index during capacity expansion: the element with hash & oldCap = = 0 remains in the original position, otherwise the new position = old position + oldCap
be careful
 Quadratic hash is to meet the design premise that the capacity is the nth power of 2. If the capacity of hash table is not the nth power of 2, quadratic hash is not necessary
 The design with a capacity of 2 to the nth power has better index efficiency, but the dispersion of hash is not good. Quadratic hash is required as compensation. A typical example of not adopting this design is Hashtable
4) In put and capacity expansion
put process
 HashMap is lazy to create arrays. It is used for the first time to create arrays
 Calculation index (bucket subscript)
 If the bucket subscript is not occupied, create a Node to return
 If the bucket subscript is already occupied
 It is already the adding or updating logic of the popular black tree of TreeNode
 It is an ordinary Node. It is the adding or updating logic of the linked list. If the length of the linked list exceeds the treelization threshold, it is the treelization logic
 Check whether the capacity exceeds the threshold before returning. Once it exceeds the threshold, expand the capacity
Differences between 1.7 and 1.8

When a linked list is inserted into a node, 1.7 is the head insertion method and 1.8 is the tail insertion method

1.7 is the capacity expansion when it is greater than or equal to the threshold and there is no vacancy, while 1.8 is the capacity expansion when it is greater than the threshold

1.8 when calculating the Node index during capacity expansion, it will be optimized
Why is the expansion (loading) factor 0.75f by default
 Achieve a good tradeoff between space occupation and query time
 Greater than this value saves space, but the linked list will be relatively long and affect the performance
 Less than this value, conflicts are reduced, but capacity expansion will be more frequent and occupy more space
5) Concurrency problem
Capacity expansion dead chain (1.7 will exist)
1.7 the source code is as follows:
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
 e and next are local variables, which are used to point to the current node and the next node
 The temporary variables e and next of thread 1 (green) have just referenced these two nodes. Before the node can be moved, thread switching occurs, and thread 2 (blue) completes the capacity expansion and migration
[the external chain picture transfer fails. The source station may have an antitheft chain mechanism. It is recommended to save the picture and upload it directly (imgho5rgtRH1646378354276)(img/image20210831084325075.png)]
 The expansion of thread 2 is completed. Due to the header insertion method, the order of the linked list is reversed. However, the temporary variables e and next of thread 1 also refer to these two nodes. We need to migrate again
[the external link image transfer fails. The source station may have an antitheft chain mechanism. It is recommended to save the image and upload it directly (imgytfRrn2B1646378354277)(img/image20210831084723383.png)]
 First cycle
 The loop then runs before thread switching. Note that e points to node a and next points to node b
 Insert node a in the head of e. note that there are two copies of node a in the figure, but in fact there is only one (two copies are specially scratched in order not to let the arrow)
 When the loop ends, e will point to next, that is, node b
[the external chain picture transfer fails. The source station may have an antitheft chain mechanism. It is recommended to save the picture and upload it directly (imgQ7Nb7ZWk1646378354278)(img/image20210831084855348.png)]
 Second cycle
 next points to node a
 e head inserting node b
 When the loop ends, e points to next, that is, node a
[the external link image transfer fails. The source station may have an antitheft chain mechanism. It is recommended to save the image and upload it directly (imgG2Z50Npj1646378354278)(img/image20210831085329449.png)]
 Third cycle
 next points to null
 The e header is inserted into node a. the next of a points to b (a.next has always been null before), and the next of b points to a. the dead chain has become
 When the loop ends, e points to next, which is null, so it will exit normally in the fourth loop
[the external link image transfer fails. The source station may have an antitheft chain mechanism. It is recommended to save the image and upload it directly (imgYRZF91X41646378354278)(img/image20210831085543224.png)]
Data disorder (1.7 and 1.8 will exist)
 Code reference day01 map. Hashmapmissdata. Refer to the video for specific debugging steps
Supplementary code description
 day01.map.HashMapDistribution demonstrates that the length of the linked list in the map conforms to Poisson distribution
 day01.map.DistributionAffectedByCapacity demonstrates the influence of capacity and hashCode value on distribution
 day01.map.DistributionAffectedByCapacity#hashtableGrowRule demonstrates the expansion law of Hashtable
 day01.sort.Utils#randomArray if the hashCode is random enough, whether the capacity is the npower of 2 has little effect
 day01.sort.Utils#lowSameArray if the hashCode has the same number of lower bits, and the capacity is the nth power of 2, the distribution will be uneven
 day01.sort.Utils#evenArray if the hashCode is even and the capacity is npower of 2, the distribution will be uneven
 It is concluded that quadratic hash is very important for the design with capacity of npower of 2
 day01.map.HashMapVsHashtable demonstrates the difference in the distribution of HashMap and Hashtable for the same number of word strings
6) key design
key design requirements
 The key of HashMap can be null, but other implementations of Map are not
 As the object of key, hashCode and equals must be implemented, and the content of key cannot be modified (immutable)
 The hashCode of key should have good hashability
If the key is variable, for example, if the age is modified, the query will not be found again
public class HashMapMutableKey { public static void main(String[] args) { HashMap<Student, Object> map = new HashMap<>(); Student stu = new Student("Zhang San", 18); map.put(stu, new Object()); System.out.println(map.get(stu)); stu.age = 19; System.out.println(map.get(stu)); } static class Student { String name; int age; public Student(String name, int age) { this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null  getClass() != o.getClass()) return false; Student student = (Student) o; return age == student.age && Objects.equals(name, student.name); } @Override public int hashCode() { return Objects.hash(name, age); } } }
hashCode() design of String object
 The goal is to achieve a more uniform hash effect, and the hashCode of each string is unique enough
 Each character in a string can be represented as a number called S i S_i Si, where i ranges from 0 to N  1
 The hash formula is: S 0 ∗ 3 1 ( n − 1 ) + S 1 ∗ 3 1 ( n − 2 ) + ... S i ∗ 3 1 ( n − 1 − i ) + ... S ( n − 1 ) ∗ 3 1 0 S_0∗31^{(n1)}+ S_1∗31^{(n2)}+ ... S_i ∗ 31^{(n1i)}+ ...S_{(n1)}∗31^0 S0∗31(n−1)+S1∗31(n−2)+...Si∗31(n−1−i)+...S(n−1)∗310
 31 substitution formula has good hash characteristics, and 31 * h can be optimized as
 I.e. $32 * h h$
 Namely 2 5 ∗ h − h 2^5 ∗h h 25∗h−h
 Namely h ≪ 5 − h h≪5 h h≪5−h
11. Singleton mode
requirement
 Master the implementation methods of five singleton modes
 Understand why DCL implementation should use volatile to modify static variables
 Understand the scenario of using singleton in jdk
Hungry Han style
public class Singleton1 implements Serializable { private Singleton1() { if (INSTANCE != null) { throw new RuntimeException("A singleton object cannot be created repeatedly"); } System.out.println("private Singleton1()"); } private static final Singleton1 INSTANCE = new Singleton1(); public static Singleton1 getInstance() { return INSTANCE; } public static void otherMethod() { System.out.println("otherMethod()"); } public Object readResolve() { return INSTANCE; } }
 The exception thrown by the constructor is a singleton to prevent reflection corruption
 readResolve() is a singleton that prevents deserialization corruption
Enumeration hungry Chinese style
public enum Singleton2 { INSTANCE; private Singleton2() { System.out.println("private Singleton2()"); } @Override public String toString() { return getClass().getName() + "@" + Integer.toHexString(hashCode()); } public static Singleton2 getInstance() { return INSTANCE; } public static void otherMethod() { System.out.println("otherMethod()"); } }
 Enumerations can naturally prevent reflection and deserialization from destroying a single instance
Lazy style
public class Singleton3 implements Serializable { private Singleton3() { System.out.println("private Singleton3()"); } private static Singleton3 INSTANCE = null; // Singleton3.class public static synchronized Singleton3 getInstance() { if (INSTANCE == null) { INSTANCE = new Singleton3(); } return INSTANCE; } public static void otherMethod() { System.out.println("otherMethod()"); } }
 In fact, synchronization is only required when the singleton object is created for the first time, but the code actually synchronizes every call
 Therefore, there is the following double check lock improvement
Double check lock lazy type
public class Singleton4 implements Serializable { private Singleton4() { System.out.println("private Singleton4()"); } private static volatile Singleton4 INSTANCE = null; // Visibility, order public static Singleton4 getInstance() { if (INSTANCE == null) { synchronized (Singleton4.class) { if (INSTANCE == null) { INSTANCE = new Singleton4(); } } } return INSTANCE; } public static void otherMethod() { System.out.println("otherMethod()"); } }
Why volatile must be added:
 INSTANCE = new Singleton4() is not atomic. It is divided into three steps: creating objects, calling construction and assigning values to static variables. The latter two steps may be reordered and optimized by instructions to assign values first and then call construction
 If thread 1 executes the assignment first, and thread 2 finds that the INSTANCE is no longer null when the first INSTANCE == null, an object that is not fully constructed will be returned
Internal lazy type
public class Singleton5 implements Serializable { private Singleton5() { System.out.println("private Singleton5()"); } private static class Holder { static Singleton5 INSTANCE = new Singleton5(); } public static Singleton5 getInstance() { return Holder.INSTANCE; } public static void otherMethod() { System.out.println("otherMethod()"); } }
 The disadvantage of double check lock is avoided
Embodiment of singleton in JDK
 The Runtime embodies the hungry man style singleton
 Console embodies the double check lock lazy single example
 The inner class lazy singleton of EmptyNavigableSet in Collections
 ReverseComparator.REVERSE_ORDER internal lazy type single example
 Comparators.NaturalOrderComparator.INSTANCE enumeration
ic void otherMethod() {
System.out.println("otherMethod()");
}
}
Why do I have to add volatile: * `INSTANCE = new Singleton4()` If it is not atomic, it is divided into three steps: creating an object, calling a construct, and assigning a value to a static variable. The latter two steps may be optimized by reordering instructions into assigning a value first and then calling a construct * If thread 1 executes the assignment first, thread 2 executes to the first one `INSTANCE == null` When found INSTANCE No longer null，An incompletely constructed object is returned **Internal lazy type** ```java public class Singleton5 implements Serializable { private Singleton5() { System.out.println("private Singleton5()"); } private static class Holder { static Singleton5 INSTANCE = new Singleton5(); } public static Singleton5 getInstance() { return Holder.INSTANCE; } public static void otherMethod() { System.out.println("otherMethod()"); } }
 The disadvantage of double check lock is avoided
Embodiment of singleton in JDK
 The Runtime embodies the hungry man style singleton
 Console embodies the double check lock lazy single example
 The inner class lazy singleton of EmptyNavigableSet in Collections
 ReverseComparator.REVERSE_ORDER internal lazy type single example
 Comparators.NaturalOrderComparator.INSTANCE enumeration