IT nan teacher: space.bilibili.com/384087053/c…

You’re supposed to know

Guaranteed efficiency
Search efficiency O (1)
Search efficiency of linked list O (n)
Search efficiency of red-black tree O (log(n))

A shift

1 <<< 8 has a sign shift to the left

0000 0000 0000 0000 0000 0001

0000 0000 0000 0000 0000 0000 0000 0000 0000

1 >> 8 Unsigned move right

Exclusive or operation

Equal to 0, different to 1.

HashMap constructor

The Alibaba Development Manual recommends specifying the collection initial value size when initializing a HashMap.

The source code

Initialization capacity refers to the initialization capacity of the array.

Member variables of the HashMap

Analysis of construction method

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
Copy the code

When the number of nodes exceeds this threshold, the array is expanded.

TableSizeFor method

/** * Returns a power of two size for the given target capacity. */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the code

Returns the smallest power greater than or equal to cap. If 3 is passed in, 4 is returned. Pass in 4, return 4. Pass in 30, return 32.

To test this method, pass in a different cap value:

public class HashMapStudy {
    public static void main(String[] args) {
        for (int i = 0; i < 50; i++) {
            System.out.println(i + " <====tableSizeFor===> "+tableSizeFor(i)); }}public static int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n + 1; }}Copy the code

Results:

0 <====tableSizeFor===> 0
1 <====tableSizeFor===> 1
2 <====tableSizeFor===> 2
3 <====tableSizeFor===> 4
4 <====tableSizeFor===> 4
5 <====tableSizeFor===> 8
6 <====tableSizeFor===> 8
7 <====tableSizeFor===> 8
8 <====tableSizeFor===> 8
9 <====tableSizeFor===> 16
10 <====tableSizeFor===> 16
11 <====tableSizeFor===> 16
12 <====tableSizeFor===> 16
13 <====tableSizeFor===> 16
14 <====tableSizeFor===> 16
15 <====tableSizeFor===> 16
16 <====tableSizeFor===> 16
17 <====tableSizeFor===> 32
18 <====tableSizeFor===> 32
19 <====tableSizeFor===> 32
20 <====tableSizeFor===> 32
21 <====tableSizeFor===> 32
22 <====tableSizeFor===> 32
23 <====tableSizeFor===> 32
24 <====tableSizeFor===> 32
25 <====tableSizeFor===> 32
26 <====tableSizeFor===> 32
27 <====tableSizeFor===> 32
28 <====tableSizeFor===> 32
29 <====tableSizeFor===> 32
30 <====tableSizeFor===> 32
31 <====tableSizeFor===> 32
32 <====tableSizeFor===> 32
33 <====tableSizeFor===> 64
34 <====tableSizeFor===> 64
35 <====tableSizeFor===> 64
36 <====tableSizeFor===> 64
37 <====tableSizeFor===> 64
38 <====tableSizeFor===> 64
39 <====tableSizeFor===> 64
40 <====tableSizeFor===> 64
41 <====tableSizeFor===> 64
42 <====tableSizeFor===> 64
43 <====tableSizeFor===> 64
44 <====tableSizeFor===> 64
45 <====tableSizeFor===> 64
46 <====tableSizeFor===> 64
47 <====tableSizeFor===> 64
48 <====tableSizeFor===> 64
49 <====tableSizeFor===> 64

Process finished with exit code 0
Copy the code

The results can be found to be regular:

0
1
10
100
1000
10000
100000 
1000000    
Copy the code

Returns the least quadratic power greater than cap.

Put method

The hash value of the key

static final int hash(Object key) {
    int h;
    return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code

(key == null) ? 0 indicates that the key can be null. When the key is not empty, the xOR operation is performed using the hashCode of the key and the hashCode of the key moved 16 bits to the right. The result is the hash value of the key.

Why xor with h >>> 16, can return h = key.hashcode () directly?

Int is 32 bits. >>> is unsigned right shift. H >>> 16 is used to extract the top 16 bits of H.

In the putVal method, you compute the subscript [I = (n-1) &hash] in the array. N indicates the data length. In the constructor of the HashMap, we know that the length of the array is calculated to the second power.

When you subtract the length of the array by one, all the bits become ones.

Most of the time, the length of the array is less than 2^16 or 65536. So I = (n-1) & the result is always the lower 16 bits of the hash and n-1.

Suppose length = 8. I’m going to assume a hash value. Then the result of (n-1) & hash is:

For an array length of 8, the discovery and subsequent results are the last 3 bits of the hash value. Taking other values for verification, it can be found that:

whenlength=8The result of the time subscript operation depends onThe lower three bits of the hash.
whenlength=16The result of the time subscript operation depends onThe lower four bits of the hash.
whenlength=32The result of the time subscript operation depends onThe lower 5 bits of the hash.
whenlength=2^NThe result of the subscript operation depends onThe low N bits of the hash.

The reason summary

The length of the array is almost always less than 2 to the 16th power because of the sum operation with the array length -1. So the lower 16 bits of HashCode (or even lower) are always involved. If the higher 16 bits were involved, it would make the resulting index more hashed.

The higher 16 bits are not needed, hence the hash(Object Key) method. Make the Object’s hashCode() xOR ^ with its own high 16 bits. (h >>> 16) gets the high 16 bits and then ^ with hashCode().

Why use ^ without & and |

& and | will make the results towards 0 or 1, idea is not uniform, so use ^.

Why is the capacity of a HashMap a power of two

& operation speed, at least than % modular operation block.
Ensure that the index value is in capacity and does not exceed the array length.
(n – 1) &hash, when n is to the 2nd power, the formula (n – 1) &hash = hash % n is satisfied.
Efficient access, as few collisions as possible, is to try to distribute data evenly.

PutVal method

// The underlying array
transient Node<K,V>[] table;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)   
        n = (tab = resize()).length;    // The array is empty, initialize the HashMap
    if ((p = tab[i = (n - 1) & hash]) == null)     // Calculate the insertion position: n is the length of the array,
        tab[i] = newNode(hash, key, value, null);  // Add data
    else {    // There are elements in the calculated index position, there is a collision
        Node<K,V> e; K k;
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;   // Replace the element with the same key
        else if (p instanceof TreeNode) // If a collision occurs, the insertion position is tree-like. If yes, the red-black tree insertion operation is performed
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {   Insert new data to the end of the list using tail interpolation
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // The number of linked list elements is greater than or equal to 8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
                        treeifyBin(tab, hash);
                    break;
                }
                // Same value found on linked list, existing data, no need to perform insert
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    break;
                p = e; // Update p to point to the next list node}}if(e ! =null) { // existing mapping for key
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue ==null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

Tree and capacity expansion

Initialization of HashMap

A HashMap is not initialized in the constructor, but the first time it is put.

Increase the timing

Resize () Expansion method

/ / array
transient Node<K,V>[] table;
// The next size value at which to resize (capacity * load factor)
If the initialCapacity is specified, the tableSizeFor(initialCapacity) method is called to calculate the value
int threshold;

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    // Old array capacity
    int oldCap = (oldTab == null)?0 : oldTab.length;
    // Old data threshold
    int oldThr = threshold;
    int newCap, newThr = 0;
    // If the length of the old array is greater than 0, the old array meets the capacity expansion condition
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // New array size = old array size * 2. Double the capacity.
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // Initialize specifies the initial capacity
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // Initialize does not specify the initial capacity, use the default 16
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // Specifies the initial capacity and recalculates the threshold
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // Create a new array with the expanded newCap
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // table points to the newly created array
    table = newTab;
    // The elements in the old array are stored in the new array
    if(oldTab ! =null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if((e = oldTab[j]) ! =null) {
                oldTab[j] = null;
                // The node in position j of the old bucket array has only 1 element, rehash the position of the node in the new bucket array
                if (e.next == null) 
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) // Index position is red black tree, perform tree operation
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // Index positions are linked lists
                else { // preserve order 
                    // low: loHead loTail
                    Node<K,V> loHead = null, loTail = null;
                    // High: hiHead hiTail tail chain
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
                    if(loTail ! =null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if(hiTail ! =null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
Copy the code

Conditions for treification

1. The length of the linked list is greater than or equal to 8

2. Capacity >= 64

The treification process

/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) ! =null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while((e = e.next) ! =null);
        if((tab[index] = hd) ! =null) hd.treeify(tab); }}Copy the code

1. Node is converted to TreeNode

2. Call Treeify for treification

The get method

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the code

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if((tab = table) ! =null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) ! =null) {
        // The TAB index position has only one element, and the comparison returns the result
        if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
            return first;
        if((e = first.next) ! =null) {
            if (first instanceof TreeNode) // The node of the red-black tree
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // The list looks for elements
            do {
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    return e;
            } while((e = e.next) ! =null); }}return null;
}
Copy the code

Changes in JDK1.7 and 1.8

Header interpolation (multiple threads will create a circular linked list), tail interpolation.

Data structure: added red black tree.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

HashMap source code analysis study notes

You’re supposed to know

HashMap constructor

The source code

Member variables of the HashMap

Analysis of construction method

TableSizeFor method

Put method

The hash value of the key

Why is the capacity of a HashMap a power of two

PutVal method

Tree and capacity expansion

Initialization of HashMap

Increase the timing

Conditions for treification

The treification process

The get method

Changes in JDK1.7 and 1.8

HashMap source code analysis study notes

You’re supposed to know

HashMap constructor

The source code

Member variables of the HashMap

Analysis of construction method

TableSizeFor method

Put method

The hash value of the key

Why is the capacity of a HashMap a power of two

PutVal method

Tree and capacity expansion

Initialization of HashMap

Increase the timing

Conditions for treification

The treification process

The get method

Changes in JDK1.7 and 1.8

Related Posts

GO Micro-service real-01 Project preparation/picture and SMS verification code

Summary of interprocess communication modes

Learning Python – Django- Models (Conditional query)