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

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

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

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

4. 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

5. 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

1. 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

2. 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

3. 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=log2​N=log10​N/log10​2

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

1. 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
2. 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

1. The array is divided into two subsets, sorted and unordered. In each round, the smallest element from the unordered subset is selected and placed in the sorted subset

2. 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

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

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

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

4. 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

1. 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)

2. Repeat the above steps until the entire array is in order

For a more vivid description, please refer to: insertion_sort.html

Algorithm implementation

// The sorting code is consistent with hill's
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]) { // j-1 is the previous element index. If > t, move back
                a[j] = a[j - 1];
                j--;
            } else { // If j-1 has been < = t, then j is the insertion position
                break;
            }
        }
        a[j] = t;
        System.out.println(Arrays.toString(a) + " " + j);
    }
}

Compare with selection sort

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

2. In most cases, insertion is slightly better than selection

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

4. 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

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

2. 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

3. 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]) { // j-gap is the last element index. If > t, move back
                    a[j] = a[j - gap];
                    j -= gap;
                } else { // If j-1 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 one-sided loop and two-sided loop codes
• Can explain the characteristics of fast exhaust
• Understand the performance comparison of lomoto and hall zoning schemes

Algorithm description

1. Each round of sorting selects a pivot for zoning
   1. Let the elements smaller than the reference point enter one partition, and the elements larger than the reference point enter another partition
   2. When the partition is completed, the position of the datum element is its final position
2. 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( divide-and-conquer)
3. 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

Muloto scheme

1. Select the rightmost element as the datum element

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

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

4. 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)

1. Select the leftmost element as the datum element
2. 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
3. Finally, the datum point is exchanged with i (at this time, i and j are equal), i is the partition position

main points

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

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

3. 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

1. The average time complexity is O ( n l o g 2 ⁡ n ) O(nlog_2⁡n ) O(nlog2 ⁡ n), worst time complexity O ( n 2 ) O(n^2) O(n2)

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

3. 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/quicksort-partitioning-hoare-vs-lomuto

Supplementary code description

• day01.sort.QuickSort3 demonstrates the improved double-sided 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

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

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

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

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

5. 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 = all-unnamed 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 read-write 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

1. Based on bidirectional linked list, no continuous memory is required
2. Random access is slow (to traverse along the linked list)
3. High performance insertion and deletion
4. Too much memory

ArrayList

1. Based on array, continuous memory is required
2. Random access fast (refers to access according to subscript)
3. 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
4. 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 --add-exports java.base/jdk.internal.misc=ALL-UNNAMED hash-demo.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_2⁡n ) 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 high-order data and make hash distribution more uniform
• Finally & (capacity – 1) gets the index

Why is the array capacity the n th power of 2

1. It is more efficient to calculate the index: if it is the nth power of 2, you can use bit sum instead of modulo
2. 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

1. HashMap is lazy to create arrays. It is used for the first time to create arrays
2. Calculation index (bucket subscript)
3. If the bucket subscript is not occupied, create a Node to return
4. If the bucket subscript is already occupied
   1. It is already the adding or updating logic of the popular black tree of TreeNode
   2. 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
5. Check whether the capacity exceeds the threshold before returning. Once it exceeds the threshold, expand the capacity

Differences between 1.7 and 1.8

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

2. 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

3. 1.8 when calculating the Node index during capacity expansion, it will be optimized

Why is the expansion (loading) factor 0.75f by default

1. Achieve a good trade-off between space occupation and query time
2. Greater than this value saves space, but the linked list will be relatively long and affect the performance
3. 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 link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-j3cpaco5-164524149274) (IMG / image-20210831084325075. 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 anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-oytu013y-164524149276) (IMG / image-20210831084723383. 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 transfer of external chain pictures fails. The source station may have anti-theft chain mechanism. It is recommended to save the pictures and upload them directly (img-gw49Oiqh-1645242149277)(img/image-20210831084855348.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 anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-omyiqa1u-164524149278) (IMG / image-20210831085329449. 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 transfer of external chain pictures fails. The source station may have anti-theft chain mechanism. It is recommended to save the pictures and upload them directly (img-nPQLYU1C-1645242149280)(img/image-20210831085543224.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. Demonstrates the rule of distribution capacity #
  • day01.sort.Utils#randomArray if the hashCode is random enough, whether the capacity is the n-power of 2 has little effect
  • day01.sort.Utils#lowSameArray if the hashCode has the same number of lower bits, and the capacity is the n-th power of 2, the distribution will be uneven
  • day01.sort.Utils#evenArray if the hashCode is even and the capacity is n-power of 2, the distribution will be uneven
  • It is concluded that quadratic hash is very important for the design with capacity of n-power 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

1. The key of HashMap can be null, but other implementations of Map are not
2. As the object of key, hashCode and equals must be implemented, and the content of key cannot be modified (immutable)
3. 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^{(n-1)}+ S_1∗31^{(n-2)}+ ... S_i ∗ 31^{(n-1-i)}+ ...S_{(n-1)}∗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