HashMap underlying principle and jdk1 8 source code interpretation [spitting blood and sorting out 1.3w long text]

1, Foreword

Write in front: it took a day to sort out the data collected by small codewords. It's helpful for you. One key three times in a row. Ha, thank you!!

HashMap is often encountered in our daily development. The source code and underlying principle of HashMap must be asked in the interview. Therefore, we should master it, which is also a necessary knowledge point as two years of development experience! HashMap is implemented based on the Map interface. Elements are stored in the form of < key, value >, and null keys and null values are allowed. Because keys are not allowed to be repeated, only one key can be null. In addition, HashMap is disordered and thread unsafe.

HashMap inherits class diagram shortcut key Ctrl+alt+U

2, Introduction to storage structure

Jdk7. Array + linked list before 0
Jdk8.0 start array + linked list + binary tree
The number of elements in the linked list is more than 8, and the linked list is transformed into a binary tree
The number of elements in the linked list is less than 6, and the binary tree is transformed into a linked list
Red black tree is a self balanced binary search tree, so the time complexity of query can be reduced to O(logn)
When the length of the linked list is very long, the query efficiency will decline sharply, and the time complexity of the query is O(n)
Jdk1.7. Add the new elements of the linked list to the head node of the linked list, first add them to the head node of the linked list, and then move them to the subscript position of the array. Short for header insertion (dead loop may occur during concurrency)
Jdk1.8. Add new elements of the linked list to the tail node of the linked list. Tail insertion method for short (solves the dead cycle of head insertion method)

Bottom structure example diagram

3, Interpretation of common variables in source code analysis

 * Default initial capacity - must be a power of 2.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

 * Maximum capacity, if a higher value is implicitly specified by any constructor with parameters. Must be a power of 2 < = 1 < < 30.
 * It is simply understood as: the maximum capacity is the 30th power of 2, and if it is carried, it will also be converted to the power of 2
static final int MAXIMUM_CAPACITY = 1 << 30;

 * The load factor to use when not specified in the constructor. The best value to reduce hash collision is measured by official test
static final float DEFAULT_LOAD_FACTOR = 0.75f;

 * Use the counting threshold of red black tree. If it exceeds 8, it will be transformed into red black tree
static final int TREEIFY_THRESHOLD = 8;

 * Use the counting threshold of red black tree. If it is lower than 6, it will be converted into linked list
static final int UNTREEIFY_THRESHOLD = 6;

 * In addition to the threshold limit, there is another limit for the conversion of linked list into red black tree. The array capacity needs to reach at least 64 before it can be converted into red black tree.
 * This is to avoid the conflict between array expansion and treelization threshold.
static final int MIN_TREEIFY_CAPACITY = 64;

 * Initialize on first use and resize as needed. When allocating, the length is always a power of 2.
 * (We also allow zero length in some operations to allow boot mechanisms that are not currently needed)
transient Node<K,V>[] table;

 * Save the cached entrySet(), that is, the stored key value pairs
transient Set<Map.Entry<K,V>> entrySet;

 * The number of key value mappings contained in this mapping is the size of the array
transient int size;

 * Record the structural changes of the collection and the number of operations (for example, modCount + + for removal).
 * This field is used to make the iterator on the collection views of HashMap fail quickly. Failure is our common CME
 * (ConcurrentModificationException)abnormal
transient int modCount;

 * Size of array expansion
 * Calculation method capacity * load factor capacity * load factor
 * @serial
int threshold;

 * Load factor of hash table.
 * @serial
final float loadFactor;

4, Interpretation of the construction method of source code analysis

 * Construct a construction method with specified initial capacity and load factor
 * This construction method is not recommended. The loading factor is the most efficient after official testing, so it should be kept default for efficiency
public HashMap(int initialCapacity, float loadFactor) {
	// If the parameter is negative, an IllegalArgumentException exception will be thrown
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
    // If the value passed exceeds the maximum value, the default maximum value will be used                                     
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
    // Load factor of hash table.                                      
    this.loadFactor = loadFactor;
    // If the initialization parameter is not the power of 2 by default, it will be directly converted to the power of 2
    // The passed parameter is 11, which will be automatically converted to the value of the nearest power of 2 larger than the parameter, that is, 16.
    // We will explain in detail how this method is transformed later
    this.threshold = tableSizeFor(initialCapacity);

 * Construct a method that only specifies the initial capacity
public HashMap(int initialCapacity) {
    // We will find that we still call the construction method of the above two parameters to automatically set the loading factor for us
    this(initialCapacity, DEFAULT_LOAD_FACTOR);

 * Construct a construction method with default initial capacity (16) and default load factor (0.75)
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

 * Specify the map collection and convert it to the construction method of HashMap
public HashMap(Map<? extends K, ? extends V> m) {
	// Use default load factor
    this.loadFactor = DEFAULT_LOAD_FACTOR;
	//Call PutMapEntries() to complete the initialization and assignment process of HashMap
    putMapEntries(m, false);
 * Add all the elements in the incoming sub Map to the HashMap one by one
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
	// Get the size of the parameter Map and assign it to s
    int s = m.size();
    // Determine whether the size is greater than 0
    if (s > 0) {
    	// Prove that there are elements to insert into the HashMap
    	// Judge whether the table has been initialized. If table=null, it is generally the putMapEntries called by the constructor, or no elements have been left after construction
        if (table == null) { // pre-size
        	// If not initialized, calculate the minimum required capacity of HashMap (that is, the capacity is no greater than the expansion threshold). Here, the size s of the Map is regarded as the capacity expansion threshold of the HashMap, and then the capacity of the corresponding HashMap can be obtained by dividing the size of the incoming Map by the load factor (current m size / load factor = HashMap capacity)
            // ((float)s / loadFactor) but this will calculate the decimal, but as the capacity, it must be rounded up, so 1 should be added here. At this time, ft can be regarded as the capacity of HashMap temporarily
            float ft = ((float)s / loadFactor) + 1.0F;
            // Judge whether ft exceeds the maximum capacity. If it is less than, use ft; if it is greater than, take the maximum capacity
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // Temporarily expand the size of the array to the power of 2, and recalculate the size of fort to the threshold of fort
            if (t > threshold)
                threshold = tableSizeFor(t);
        // If the current map has been initialized and the number of elements in the map is greater than the expansion threshold, it must be expanded
        // This is the case of expanding capacity in advance and then put ting elements
        else if (s > threshold)
        	// Expand later
        // Traverse the map and add the key and value in the map to the HashMap
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // Call the specific implementation method putVal of the put method of HashMap to store the data. The specific details of this method will be explained later
            // putVal may also trigger resize
            putVal(hash(key), key, value, false, evict);

5, Interpretation of common methods of source code analysis

1. Interpretation of tableSizeFor method

 * Returns the power of the given target capacity.
static final int tableSizeFor(int cap) {
	// cap = 10
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // Less than 0 is 1. If it is greater than 0, judge whether it exceeds the maximum capacity, that is, n=15+1 = 16. If it exceeds the maximum capacity
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

Take cap 10 as an example: (shift right rule: shift unsigned bit right)

10 binary: 0000 0000 0000 1010

Execute int n = cap - 1;

Binary result: 0000 0000 0000 1001

Execute n | = n > > > 1; (shift to the right first, and the result is or calculated with the original number [= = if there is 1, then 1 = = =)

0000 0000 0000 0000 0000 0000 0000 1001
0000 0000 0100 n > > 1 Result
0000 1101 n | = n > > 1 Result

Binary result: 0000 0000 0000 1101

Execute n | = n > > > 2;

0000 0000 0000 0000 0000 0000 0000 1101

0000 0000 0011 n > > 2 Result

0000 1111 n | = n > > 2 Result

Binary result: 0000 0000 0000 0000 1111

Execute n | = n > > > 4;

0000 0000 0000 0000 0000 0000 0000 1111

0000 0000 0000 0000 0000 0000 n > > 4 Results

0000 1111 n | = n > > 4 Result

Binary result: 0000 0000 0000 0000 1111

Execute n | = n > > > 8;

0000 0000 0000 0000 0000 0000 0000 1111

0000 0000 0000 0000 0000 0000 n > > 8 results

0000 1111 n | = n > > 8 result

Binary result: 0000 0000 0000 0000 1111

Execute n | = n > > > 16;

0000 0000 0000 0000 0000 0000 0000 1111

0000 0000 0000 0000 0000 n > > 16 result

0000 1111 n | = n > > 16 result

Binary result: 0000 0000 0000 0000 1111

We will find that when the number is small, it will not change when it reaches 4. The value we get is 15, that is, enter 10. After this method, we get 15. When you encounter a large number, it will be obvious. You can find a large number to try, that is, move it to the right first for or operation. Finally, conduct three door operation and + 1 operation. The final result is 16 = 2 ^ 4

2. Interpretation of hash method

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

First judge whether the key is empty. If it is empty, 0 will be returned. As mentioned above, HashMap only supports one key that is null. If it is not empty, first calculate the hashCode value of the key, assign it to h, then shift h to the right by 16 bits, and XOR with the original H (the same is 1, the difference is 0).
Google Translate notes:
Calculate key Hashcode() and propagate (XOR) higher order hash reduction. Because the table uses a quadratic power mask, hash sets that change only above the current mask will always conflict. (a known example is the Float key set that holds consecutive integers in a small table.) Therefore, we apply a transformation to propagate the influence of high bits downward. There is a tradeoff between the speed, practicality and quality of in place expansion. Because many common hash sets have been reasonably distributed (so don't benefit from propagation), and because we use trees to deal with a large number of conflicts in bin, we just XOR some shifted bits in the simplest way to reduce system loss and merge the influence of the highest bit. Otherwise, due to table boundaries, These highest bits will never be used for index calculations.

Conclusion: the simplest way is used to reduce the system loss and hash collision.

3. Interpretation of put method

* Associates the specified value with the specified key in this mapping. That is, where the current key should be stored in the array
* If the mapping previously contained a key, replace the old value.
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
* This is the real way to save
* @param hash   			key after hash operation
* @param key    			key you want to add
* @param value  			value you want to add
* @param onlyIfAbsent 		If it is true, do not change the existing value. This time it is FALSE and you can replace the change
* @param evict 				If false, the table is in create mode. We are true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
              boolean evict) {
   Node<K,V>[] tab; Node<K,V> p; int n, i;
   // Judge whether the table is empty
   if ((tab = table) == null || (n = tab.length) == 0)
   	   // If it is empty, it will call resize to expand the capacity first. Resize will be explained later
       n = (tab = resize()).length;
   // The value obtained through the hash and the array size - 1 are combined, and this operation can realize the modular operation, and the bit operation has another advantage, that is, the speed is relatively fast.
   // Get the node of the array corresponding to the key, then assign the array node to p, and then judge whether there is an element at this position
   if ((p = tab[i = (n - 1) & hash]) == null)
   	   // key and value are wrapped as newNode nodes and directly added to this location.
       tab[i] = newNode(hash, key, value, null);
   // If there are already elements in the index position of the current array, there are three cases.
   else {
       Node<K,V> e; K k;
       // The hash value of the current location element is equal to the passed hash, and their key values are also equal
       if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
           // Assign p to e, and then replace the old value with a new value
           e = p;
       // Come here to explain that the key of this node is different from the original key. It depends on whether the node is a red black tree or a linked list
       else if (p instanceof TreeNode)
       	   // If it is a red black tree, save the key value into the red black tree through the red black tree. This method will be explained later
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
       else {
       	   // Come here to explain that the structure is a linked list. Insert the key value at the end of the linked list using the tail interpolation method.
           // jdk1.7 linked list is a header insertion method, which will cause dead loop during concurrent capacity expansion
           // jdk1. The head insertion method is replaced by the tail insertion method. Although the efficiency is slightly reduced, there will be no dead cycle
           for (int binCount = 0; ; ++binCount) {
           	   // Traverse the linked list and know that the next node is null.
               if ((e = p.next) == null) {
               	   // Explain to the tail of the linked list, and then point the next of the tail to the newly generated object
                   p.next = newNode(hash, key, value, null);
                   // If the length of the linked list is greater than or equal to 8
                   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                   	   // Then the linked list is transformed into a red black tree and supplemented later
                       treeifyBin(tab, hash);
               // If the same key is found in the linked list, exit the loop directly
               if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
               p = e;
       // It indicates that there is a collision. e represents the old value and needs to be replaced with a new value
       if (e != null) { // existing mapping for key
           V oldValue = e.value;
           // Judge whether the old value is allowed to be overwritten and whether the old value is empty
           if (!onlyIfAbsent || oldValue == null)
           		// Replace old value
               e.value = value;
           // hashmap has no implementation, so we won't consider it first
           // Return new value
           return oldValue;
   // The fail fast mechanism changes the structure by + 1 every time
   // Judge the size of the stored data in the HashMap. If it is greater than the array length * 0.75, expand the capacity
   if (++size > threshold)
   // It is also an empty implementation
   return null;

4. Interpretation of resize method

Can't check the original link: HD map link

 * Initialize by table, or allocate space by table, if it is empty,
 * Otherwise, after doubling, the elements in each container either stay at the original index or have a displacement to the power of 2 in the new table
final Node<K,V>[] resize() {
	// Original data
    Node<K,V>[] oldTab = table;
    // Get the original array size
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // The capacity expansion threshold of the old array. Note that the threshold value of the current object is taken here. The second case below will be used.
    int oldThr = threshold;
    // Initialize the capacity and threshold of the new array
    int newCap, newThr = 0;
    // 1. When the capacity of the old array is greater than 0, it means that resize must have been called to expand the capacity once before, which will lead to the old capacity not being 0.
    if (oldCap > 0) {
    	// Maximum capacity
        if (oldCap >= MAXIMUM_CAPACITY) {
        	// Set the expansion size to the upper limit
            threshold = Integer.MAX_VALUE;
            // Directly return to the default original, can not be expanded
            return oldTab;
        // If the old capacity is between 16 and the upper limit
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // The capacity and threshold of the new array are doubled
            newThr = oldThr << 1; // double threshold
    // 2. Here, oldcap < = 0, oldthr (threshold) > 0. This is when the map is initialized,
    // The first call to resize
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 3. Here, it shows that both oldCap and oldThr are less than or equal to 0. It also shows that our map is created by default parameterless construction
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;// 16
    // Only after 2 Will enter
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        // If the calculated ft conforms to the size, assign a value of newThr 
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    // Finally, get the size to be expanded
    threshold = newThr;
    // Used to suppress the compiler from generating warning messages
    	// In the constructor, the array is not created. The array will be created only when the put method is called for the first time, resulting in resize.
    	// This is to delay loading and improve efficiency.
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // Judge whether the original array has a value. If not, return the array just created
    if (oldTab != null) {
    	// Convenience old array
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // Judge whether the current element is empty
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // If the next element of the first element is null, there is only one in the linked list
                if (e.next == null)
                	// Then directly use its hash value and the capacity of the new array to take the module (so that the operation efficiency is high) to get the new subscript position
                    newTab[e.hash & (newCap - 1)] = e;
                // If it's a red black tree
                else if (e instanceof TreeNode)
                	// Then split the red and black trees. This small series doesn't need to study further. If you are interested, you can click in and have a look
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // Description is a linked list and the length is greater than 1
                else { // preserve order
                	// The head and tail nodes in the old position of the linked list
                    Node<K,V> loHead = null, loTail = null;
                    // The head and tail nodes of the new position of the linked list
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // I don't quite understand it here. I can only refer to the explanation of the boss. I'm still a little confused. I'll sort it out again when I have time to understand it
                    do {
                        next = e.next;
                        // If the hash value and oldCap sum operation of the current element are 0, the original position remains unchanged
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                                loTail.next = e;
                            loTail = e;
                        // If it is not 0, move the data to a new location
                        else {
                            if (hiTail == null)
                                hiHead = e;
                                hiTail.next = e;
                            hiTail = e;
                    } while ((e = next) != null);
                    // A linked list whose original position remains unchanged, and the subscript of the array remains unchanged
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    // A linked list moved to a new location. The array subscript is the original subscript plus the capacity of the old array
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
    return newTab;

5. Interpretation of get and containsKey methods

* Get the corresponding value according to the key
public V get(Object key) {
    Node<K,V> e;
    // After calling, get the value of the element and return
    return (e = getNode(hash(key), key)) == null ? null : e.value;
* Determine whether the key exists in the map
public boolean containsKey(Object key) {
	// The calling method exists and is not null
    return getNode(hash(key), key) != null;
* We found that getNode works at the bottom
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // Judge that the array cannot be empty, and then get the first element of the subscript position calculated by the current hash value
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // If the hash value and key are equal and not null, then we are looking for the first element
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // Returns the first element
            return first;
        // If it's not the first one, keep looking
        if ((e = first.next) != null) {
        	// If it's a red black tree
            if (first instanceof TreeNode)
                // Then we use the search method of red black tree to obtain the value corresponding to the key we want
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // This description is an ordinary linked list. We can look down in turn
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
    // The value corresponding to the key cannot be found. null is returned
    return null;

6. Interpretation of remove method

 * If the key exists, delete the element
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;

 * Specific implementation of deletion method
* @param hash   			key after hash operation
* @param key    			key you want to remove
* @param value  			value you want to remove
 * @param matchValue 		If it is true, it will be deleted only when the values are equal. We are FALSE. If the key s are the same, it will be deleted
 * @param movable 			If it is false, do not move other nodes during deletion. If it is TRUE, delete and move other nodes
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // Judge whether the table and linked list are not empty
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // The first node in the array is the node we want to delete
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // node to delete
            node = p;
        // The first one is not, and there are nodes behind it
        else if ((e = p.next) != null) {
            // If it's a red black tree
            if (p instanceof TreeNode)
            	// Return found in red black tree
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
            	// Traversal linked list
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        // Find the node to delete
                        node = e;
                    p = e;
                } while ((e = e.next) != null);
        // The node we want to delete has been found
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // If it is a red black tree, delete it according to the red black tree
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //What we want to delete is the head node
            else if (node == p)
                 tab[index] = node.next;// Since the first node is deleted, you can directly point the corresponding position of the node array to the second node
            //Not the head node, point the current node to the next node of the deleted node
                p.next = node.next;// The next node of p points to the next node of node to delete node from the linked list
            // Operation + 1
            // map size - 1
            // Empty implementation
            // Returns the deleted node
            return node;
    return null;

6, Summary

There are still a lot of bottom layers of Has and Map, and some logic and algorithms used in them are very cowhide and thought-provoking. The talents in oracle are still powerful. If you can't understand it, people can design it and realize it. Really, you and I are all mole ants, just people who move bricks and tools. Ha ha, a self mockery of yourself, ha, encourage!! See here, point a praise, small code words are not easy!! Thank you!!

Some notes are understood from: Reference blog

It's time to promote your website!!!

Click to visit! Welcome to visit, there are many good articles in it!

Keywords: Java Interview HashMap

Added by vweston on Thu, 17 Feb 2022 16:03:07 +0200