preface

Friendly reminder, the length of this article involves more knowledge points, the consumption of mental power is relatively large. If you are afraid to find this article later, suggest collecting first


If you don’t have to review, you can skip to — the interview begins


The following code is from JDK8

Let’s review before the interview

HashMap’s put method 

Public V put(K key, V value) {return putVal(hash(key), key, value, false, true); } static final int hash(Object key) {int h;} static final int hash(Object key) {int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; // Node<K,V> p; // Node int n, I; / / if the table is empty, that is not initialized, or has been initialized, but the length of the array is 0, that is not a power of 2 to the power if (= = null (TAB = table) | | (n = TAB. Length) = = 0) / / to increase the resources TAB, allocate space, Initial value n=16 n= (TAB = resize()).length; If ((p = TAB [I = (n-1) & hash]) == null) // TAB [I] = newNode(hash, key, value, null); Else {Node<K,V> e; else {Node<K,V> e; K k; // If the hashes are equal, and the memory address of the key or the value of the key are equal. Then the if (p.h ash = = hash && ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) e = p; Else if (p instanceof TreeNode) // if p is a node on a red-black tree, E = ((TreeNode<K,V>)p).putTreEval (this, TAB, hash, key, value); Else {// for (int binCount = 0; ; ++binCount) {if ((e = p.ext) == null) {// place the newNode on the next node of p = newNode(hash, key, value, null); If (binCount >= =8) // -1 for 1st treeifyBin(TAB, hash); break; } // If the hash of the node, the key is equal to the node to be added. In the back will be replace operation if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) break; p = e; }} // If (e! = null) { // existing mapping for key V oldValue = e.value; // If onlyIfAbsent is true, do not change the value if (! OnlyIfAbsent | | oldValue = = null) / / change the value value e.v alue = value; // The empty method afterNodeAccess(e) is left for LinkedHashMap; // return oldValue return oldValue; } } ++modCount; // If (++ Size Threshold >) resize(); afterNodeInsertion(evict); return null; }

To summarize, the general flow of the PUT method is as follows:

  1. Hash the key to get the hash value
  2. The value of the hash value mod the length of the array is the index of the key
  3. If the index position of the array is NULL, it is inserted directly

  4. If the index position of the array has a value, there are three conditions:

    • Case 1: If the Key of the node is equal to the Key to be inserted, then simply replace the value value
    • Scenario 2: If the node belongs to a red-black tree, just do it as a red-black tree update or insert
    • Situation 3: If the node belongs to the linked list node, we will traverse the linked list and replace the value if we can find the corresponding node. If the corresponding node cannot be found, a new node is inserted at the tail of the list.

This is just a general description, specific implementation details, directly see the source code is good.

The get method of the HashMap 

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; Static final int hash(Object key) {int h;} static final int hash(Object key) {int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // If the array is not empty, and the length of the array is greater than 0, and the header is not empty; Null if (TAB = table)! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! = null) {// If the hash value of the header is equal to the hash value of the key, and the address of the key or the contents of the key are equal; Is returned directly if head nodes (first hash = = hash && / / always check first node ((k = first. Key) = = key | | (key! = null && key.equals(k)))) return first; // If the header node is not equal, if there is a next node, traverse it; Return null if ((e = first.next)! = null) {// If the node is a red-black tree, then the node is retrieved as a red-black tree, If (first instanceof treeNode) return ((treeNode <K,V>)first).getTreeNode(hash, key); Do {// If it is a linked list, iterate over the hash, address of the key, or contents of the key, and return it immediately if it meets the criteria. If not, iterate over the next node. If after traverse all the nodes, all didn't, then return null if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) return e; } while ((e = e.next) ! = null); } } return null; }

To summarize, the get method of HashMap flows as follows:

  1. Get the hash value based on the key
  2. The index value is obtained by taking the remainder of the hash value and the array length
  3. According to the index value, the corresponding node is obtained, and then the key and hash of the node are compared
  4. If they are equal, the corresponding node is returned; Not equal, continue traversal; If the traversal fails at the end, null is returned

This is just a general description, specific implementation details, directly see the source code is good.

Put method of ConcurrentHashMap 

public V put(K key, V value) { return putVal(key, value, false); } final V putVal(K key, V value, Boolean onlyIfAbsent) {// Final V putVal(K key, V value, Boolean onlyIfAbsent) {// Final V putVal: The key and the value cannot be null if (key = = null | | value = = null) throw new NullPointerException (); Int hash = spread(key.hashCode()); int hash = spread(key.hashCode()); int binCount = 0; // for (Node<K,V>[] TAB = table; { Node<K,V> f; int n, i, fh; / / table is null, the initialization if (TAB = = null | | (n = TAB. Length) = = 0) TAB = initTable (); // If there is no node in the I position, insert it directly, Else if ((f = tabAt(TAB, I = (n-1) & hash)) == null) {//CAS if (tababat (TAB, I, null, new Node<K,V>(hash, hash)) == null) key, value, null))) break; // No lock when adding to empty bin} // If a thread is adding to empty bin}, Else if ((fh = fh) == MOVED) TAB = helpTransfer(fh, f); else { V oldVal = null; // Locking the node (the head node of a linked list with the same hash value) will affect performance slightly. Synchronized (f) {if (tabAt(TAB, I) == f) {if (tabAt(TAB, I) == f) {if (fh >= 0) {binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; / / hash and the key is the same, to replace the value the if (e.h ash = = hash && (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek)))) { oldVal = e.val; //putIfAbsent() if (! onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; If ((e = e.ext) == null) {pred.next = new Node<K,V>(hash, key, value, null); break; }}} else if (f instanceof TreeBin) {Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! = null) { oldVal = p.val; if (! onlyIfAbsent) p.val = value; } } } } if (binCount ! If (binCount >= TREEIFY_THRESHOLD) treeifyBin(TAB, I); if (binCount >= TREEIFY_THRESHOLD); if (oldVal ! = null) return oldVal; break; } } } //size + 1 addCount(1L, binCount); return null; }

To summarize, the general flow of ConcurrentHashMap’s put method is as follows:

  1. First of all, it is null. Key and value are not allowed to be NULL. (See Supplementary Knowledge 1)
  2. And then calculate the hash. (See Supplement 4) Just a few words:

  3. Then traverse the table to insert the node. The specific process is as follows:

    • If the table is empty, then the ConcurrentHashMap has not been initialized, then initialization is performed: initTable()
    • Returns the node position I based on the hash value. If the node position is empty, it is inserted directly. This process does not require locking. Calculate f position: I =(n-1) & hash. (See Supplementary Knowledge 2)
    • If it detects fh = f.ash == -1, then f is a ForwardingNode node, indicating that other threads are doing capacity expansion, and helping threads to do capacity expansion together. (See Supplementary Knowledge 3)
    • If f.ash >= 0 indicates a linked list structure, the list is traversed. If the current key node exists, the value is replaced. Otherwise, it is inserted into the tail of the list. If f is a TreeBin type node, the node is updated or added according to the red-black tree method
    • If the length of the list is > TREEIFY_THRESHOLD(the default is 8), the list is converted to a red-black tree structure

The get method of ConcurrentHashMap 

public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // hash int h = spread(key.hashCode()); // if ((TAB = table)) if ((TAB = table)); = null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) ! = null) {/ / search to the key nodes of the same as the incoming key and not null, return directly if the node (eh = e.h (ash) = = h) {if (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek))) return e.val; } else if (eh < 0) return (p = e.find(h, key))! = null ? p.val : null; // while ((e = e.ext)! = null) { if (e.hash == h && ((ek = e.key) == key || (ek ! = null && key.equals(ek)))) return e.val; } } return null; }

To summarize, the general flow of ConcurrentHashMap’s get method is as follows:

  1. So let’s calculate the hash
  2. Get the index value by (n-1) & h
  3. If the match is a header node, the corresponding value is returned directly
  4. If it is a tree, return value based on the read operation of the red-black tree
  5. If it’s a linked list, match it, traverse it, get the corresponding value

## Supplement knowledge

  • HashMap allows NULL key and value values.
  • 2. CAS is used in this process, which can be understood as a lock or spin lock. It can also be understood as lockless, since CAS is a hardware instruction, unlike OS level locks such as Synchronized. Therefore, whether there is a lock or not is a matter of opinion. You understand for yourself.
  • ForwardingNode: A special Node with a hash value of -1 that stores a reference to the nextTable. ForwardingNode is used only when the table is expanded, and is placed in the table as a placeholder to indicate that the current node is null or has been moved.
  • 4. Compared to the hash function of HashMap, both have a shift operation, which is only slightly different, but the purpose is to reduce hash collisions.

Well, you’re pretty tired after looking at the get and put methods of HashMap and ConcurrentHashMap. Because I also write very tired, harm. Now you can hit a like first, to comfort my hard work; Had better collect first, convenient you review later look again. If you’re tired, click on one so you can have a drink of water and watch it after dinner. If you think it’s good, share it and pass it on to your friends.

The AD is over!! I went on!! The interview officially begins!!

The interview began

Interviewer: Can you talk about the process of putting the HashMap method?

  • Bala Bala a pile, their reference to write above the general process can, I do not repeat.

Interviewer: When does a linked list in a HashMap become a tree?

  • In order for the list to become a tree, two conditions must be met: the length of the list >=8 and the capacity of the HashMap >=64. If the length of the list is >=8, but the capacity of the HashMap is <64, then capacity expansion is performed. After the capacity expansion operation, the length of the linked list will be shortened accordingly. (The relevant source code is as follows 🙂
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(); . Omit a bunch of code

Interviewer: Why does a linked list variable tree have 8 nodes in a HashMap?

  • You just tell the interviewer that it’s a statistical problem. Officials have tested that when there are more than 8 nodes, the probability of a collision is less than 1 in 10 million. (To be sure, I’ll take a comment from the source code.)
* 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million // less than one in ten million

Interviewer: What’s the difference between JDK7 and JDK8 for HashMap?

  • When JDK7 hash conflicts occur, the linked list becomes longer and longer, and the time complexity becomes O(N). JDK 8, on the other hand, has hash conflicts. Under certain conditions, the linked list becomes a red-black tree and the time complexity becomes O(LogN).
  • JDK7 in high concurrency environment, because of thread insecurity, put method operation, due to the expansion of the resize method and the header interpolation method, the linked list will be ring, resulting in the GET method, CPU100% security problem. JDK 8 is not thread-safe, but the header method is changed to the tail method, which no longer loops the linked list when resizing.
  • So, to summarize, one of the important differences is the introduction of red-black trees, and the interviewer will probably ask you why the introduction of red-black trees and not other trees, like search binary trees. In fact, the main inspection of your understanding of the data structure, before the interview, it is best to balance the tree, red-black tree, search binary tree these trees read and write time complexity, as well as the advantages and disadvantages of understanding.

Interviewer: What’s the difference between a synchronizedMap and a ConcurrentHashMap?

  • SynchronizedMap

The entire table is locked at a time for thread-safety, so only one thread can visit the map at a time.

  • ConcurrentHashMap

Use CAS+Synchronized to ensure thread safety. Relative to synchronizedMap. ConcurrentHashMap locks a node, synchronizedMap locks the entire table. The analogy is to MySQL row locks and table locks. ConcurrentHashMap locks are more granular. In addition, ConcurrentHashMap uses a different iteration approach. In this kind of iteration method, when the iterator is created after the collection and change is no longer throw ConcurrentModificationException, instead of changing the new new data which does not affect the original data, After the iterator completes, the header pointer is replaced with the new data, so that the iterator thread can use the old data and the writer thread can make the changes concurrently.

Interviewer: Why doesn’t ConcurrentHashMap read with a lock?

  • For this point, you actually need to compare the JDK7 and JDK 8 ConcurrentHashMap.

  • In JDK7 and before

    • The key, hash, and next in HashEntry are all final and can only be inserted or deleted in the header.
    • The value in a HashEntry is volatile.
    • NULL is not allowed as a key or value. When the reader reads a hashEntry’s value field with a NULL value, it knows there is a conflict — a reorder has occurred (put sets the bytecode instruction reorder for the new value object). You need to re-read the value after locking it.
    • The volatile variable count coordinates the memory visibility between reading and writing threads. Count is changed after a write, and count is read before a read. The change reads of a write can be seen according to the occur-before transitivity principle.

  • In JDK8

    • Node’s val and next are volatile.
    • The Unsafe operation corresponding to the tabAt() and casTabAt() methods implements volatile semantics, so you can disable reordering without worrying about reading Null values.
    static class Node<K,V> implements Map.Entry<K,V> {
      final int hash;
      final K key;
      volatile V val; 
      volatile Node<K,V> next;

      Node(int hash, K key, V val, Node<K,V> next) {
          this.hash = hash;
          this.key = key;
          this.val = val;
          this.next = next;
      }

    Interviewer: The interview is over. Congratulations to the next round of interview

conclusion

In fact, there are many more interview questions about Java collections – HashMap and ConcurrentHashMap – and I won’t go through them here

  • Is the iterator of ConcurrentHashMap strongly or weakly consistent? A HashMap?
  • When will HashMap start to expand? How to expand capacity?
  • What’s the difference between ConcurrentHashMap 7 and 8?

omg

Thank you very much for reading here. If you think the article is well written, please pay attention to it and share it with thumb up. If you think the article needs improvement, I am looking forward to your suggestion, please leave a comment. If there’s anything you’d like to see, I’d love to hear from you. Everyone’s support and support, is my creation of the biggest power!

The resources

  • Taro, source
  • Mingo — Java Concurrent Container from J.U.C