HashMap interviews, read this article

In Java 7, the implementation of HashMap was over 1000 lines, but in Java 8 it grew to over 2000 lines. Although the number of lines of code was small, there were a lot of bit operations and other details in the code that made it look complicated and difficult to understand. But if we step out of the way, the HashMap data structure is very basic, and we start with a picture in our head like this:

This diagram captures the most basic points of a HashMap:

1. JavaIn theHashMapThe basic data structure of the implementation of thekey->valueIs composed of key value pairsEntityClasses are stored in this array as a bidirectional linked list
2. The position of the element in the array is determined bykey.hashCode()The value of is determined if twokeyThe hash values of are equal, that is, a hash collision occurs, then these twokeyThe correspondingEntityWill be stored in an array as a linked list
3. callHashMap.get()Will be calculated firstkeyIs then found in the arraykeyAnd then walk through the linked list at that position to find the corresponding value.

Of course there are two things that are missing from this picture:

1. In order to elevate the entireHashMapThe read efficiency whenHashMapIs equal to the size of the bucket array times the load factorHashMapWe’re going to have to expand to reduce hash collisions, which we’ll talk about later in the code
2. inJava 8If the number of linked lists in the same position of the bucket array exceeds a fixed value, the whole linked list has a certain probability to turn into a red-black tree.

On the whole, there are four most important points in the whole HashMap: initialization, data address-hash method, data storage-PUT method, and expansion -resize method. As long as you understand the principle and call timing of these four points, you will understand the design of the whole HashMap.

In JDK 8, when new HashMap() is called, no array heap memory is allocated, just some parameter verification and some constants are initialized

`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); ` `}` `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

TableSizeFor is used to find the smallest integer power of 2 greater than cap, and we assume that n is 000001xxxxxx, where x is 0 or 1.

n |= n >>> 1; The value of n after execution is:

You can see that the top two bits of n are now 1 (1 and 0 or 1 or both), and then execute the second line:

Visible n binary four has become the highest 1, until the execution of the code n | = n > > > 16; After that, the lowest binary value of n is all 1, that is, n = 2^x – 1 where x depends on the value of n, and if not MAXIMUM_CAPACITY is exceeded, a positive integer power of 2 is returned. So tableSizeFor ensures that a minimum positive integer power of 2 greater than the input parameter is returned.

The code initialized in JDK 7 is similar to the inflateTable inflateTable inflateTable inflateTable inflateTable inflateTable inflateTable inflateTable inflateTable inflateTable inflateTable inflateTable inflateTable

'// For the first time put, Private void inflateTable(int toSize) {' // Find an power of 2 >= toSize 'int capacity = roundUpToPowerOf2(toSize); ` `threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); ` `table = new Entry(capacity); ` `initHashSeedAsNeeded(capacity); ` ` `}Copy the code

Here we also answer the question posed at the beginning:

When does a HashMap open a bucket array to occupy memory? The answer is that when HashMap is first put, this is how it is implemented in both Java 8 and Java 7. Here we can see that the size of the bucket array is a positive integer power of 2 in both versions of the implementation. You will see why this is the case later.

The idea behind the put method in Java 8 is as follows:

1. callkeythehashCodeMethod computes the hash value from which the array index is calculated
2. If the current bucket array is found asnullThe callresize()Method to initialize
3. If no hash collision occurs, it is placed directly into the corresponding bucket
4. If a hash collision occurs and the node already exists, replace the correspondingvalue
5. If a hash collision occurs and a tree structure is stored in the bucket, mount it to the tree
6. If it is a linked list after collision, add it to the end of the linked list, if the linked list overpassesTREEIFY_THRESHOLDThe default is 8, which converts the list to a tree structure
7. dataputAfter that, ifHashMapMore thanthresholdWill beresize

The specific code and comments are as follows:

'public V put(K key, V value) {' // Call hash method' 'return putVal(hash(key), key, value, false, 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; ` ` if ((TAB = table) = = null | | (n = TAB. Length) = = 0) ` ` / / put for the first time, will be called the resize for bucket array initialization ` ` n = (TAB = the resize ()). The length; If ((p = TAB [I = (n-1) &hash]) == null) // If (p = TAB [I = (n-1) &hash]) ' 'TAB [I] = newNode(hash, key, value, null); ` `else {` `Node<K,V> e; K k; ` `if (p.hash == hash &&` `((k = p.key) == key || (key ! = null && key.equals(k)))) ' '// hash collision, and node already exists, directly replace' 'e = p; Else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).puttreeval (this, TAB, hash, key, value); For (int binCount = 0; ; ++binCount) {` `if ((e = p.next) == null) {` `p.next = newNode(hash, key, value, null); If (binCount >= treeify_threshold-1) // -1 for 1st treeifyBin(TAB, hash); ` `break; ` `}` `if (e.hash == hash &&` `((k = e.key) == key || (key ! = null && key.equals(k)))) ' '// If the node already exists, break the loop; // Otherwise, the pointer moves back, continuing the loop ' 'p = e; ` `}` `}` `if (e ! = null) {// existing mapping for key ' '// branch' ' 'V oldValue = e.value; ` `if (! onlyIfAbsent || oldValue == null)` `e.value = value; ` `afterNodeAccess(e); ` `return oldValue; ` `}` `}` `++modCount; 'if (++size > threshold)' // If the threshold is exceeded, resize() needs to be expanded; ` `afterNodeInsertion(evict); ` `return null; ` ` `}Copy the code

The PUT method in Java 7 is much simpler by comparison

'public V put(K key, V value) {' // If key is null, Call putForNullKey if (key == null) return putForNullKey(value); ` `int hash = hash(key.hashCode()); ` `int i = indexFor(hash, table.length); ` `for (Entry<K, V> e = table[i]; e ! = null; e = e.next) {` `Object k; ` `if (e.hash == hash && ((k = e.key) == key` `|| key.equals(k))) {` `V oldValue = e.value; ` `e.value = value; ` `e.recordAccess(this); ` `return oldValue; ` `}` `}` `modCount++; ` `addEntry(hash, key, value, i); ` `return null; ` `}` `void addEntry(int hash, K key, V value, int bucketIndex) {` `Entry<K, V> e = table[bucketIndex]; // ① 'table[bucketIndex] = new Entry<K, V>(hash, key, value, e); ` `if (size++ >= threshold)` `resize(2 * table.length); / / (2) ` ` `}Copy the code

There is a small detail here. HashMap allows key-value pairs with putKey null, but such key-value pairs are placed in the 0th bucket of the bucket array.

After looking at the implementation of HashMap in Java 8 and Java 7, let’s answer some of the questions raised above:

1. Why is the bucket array length inside the HashMap always an integer power of 2

   A: This has two advantages. First, it can be quickly addressed with bits such as (table.length-1) & key.hash(). Second, when HashMap is expanded, it can ensure that elements in the same bucket are evenly hashed into new buckets. To be specific, elements in the same bucket are generally kept in the original bucket after expansion, and are generally put into a new bucket.

2. The default size of the bucket array for the HashMap

   A: The default is 16, and even if the specified size is not an integer power of 2, the HashMap will find the nearest integer power of 2 to initialize the bucket array.

3. When does a HashMap open a bucket array to occupy memory

   Answer: Call the resize method on the first put

4. When will HashMap be expanded?

   A: When element proficiency in a HashMap exceeds the threshold, the threshold is calculated as capacity * loadFactor, which in a HashMap is 0.75

5. When does the list of elements in a bucket become a red-black tree, when does it go back to the list, and why?

   A: When the number of elements in the same bucket is greater than or equal to 8, the linked list of elements in the bucket is converted to a red-black tree. Conversely, when the number of elements in the bucket is less than or equal to 6, the linked list is converted to a red-black tree. The reason for this is to avoid frequent conversion between the red-black tree and the linked list, resulting in performance loss

6. Why were red-black trees introduced in Java 8, and what scenarios were they designed to solve?

   A: The red-black tree is introduced to avoid scenarios in which the hash performance deteriorates dramatically and the read and write performance of the HashMap deteriorates dramatically. Under normal circumstances, the red-black tree is generally not used. In some extreme scenarios, if the client implements a hashCode method with poor performance, The read/write complexity of a HashMap is guaranteed to be no less than O(lgN)

   `public int hashCode() {` `return 1; ` ` `}Copy the code

7. How does HashMap handle key-value pairs with null keys?

   A: Placed in a bucket with subscript 0 in the bucket array
   
   

8. From: blog.csdn.net/DD_Dddd/article/details/115427040