## HashMap structure

Array + Linked list + Red and black trees

Linked list greater than 8 Turn the red and black tree , The number of nodes in the red and black tree is less than 6 Return list .

## Deposited key-value Of Node node

```
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
```

Tree shaped Node node

```
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
```

His inheritance structure is like this , You can see the inheritance Node node

## Understand a sentence

```
hash & tab.length-1
```

You can see this code in many places in the code , In fact, this sentence only makes a remainder （%） The action of . One & How to do the residual operation ：**HashMap The capacity of is 2^n** Its binary structure is as follows

Any number &2^n-1（01111…） The result is 0xxxx, We have done the operation of quick surplus . Later, you will see that the statement appears frequently

## Several core parameters

- Node<K,V>[] table： Deposit Node Array of
- int size： At present HashMap Number of key value pairs contained
- int threshold： At present HashMap The maximum number of key value pairs that can withstand , Once that number is exceeded HashMap It's going to expand
- final float loadFactor： Load factor , For expansion
- int DEFAULT_INITIAL_CAPACITY = 16： default table Initial capacity
- float DEFAULT_LOAD_FACTOR = 0.75f： Default load factor
- int TREEIFY_THRESHOLD = 8: If the length of linked list is greater than this parameter, it will be converted to red black tree
- int UNTREEIFY_THRESHOLD = 6: When the number of nodes in the tree is less than or equal to this parameter, it is converted into a linked list

## Initialization method

Specified specific capacity , And the initialization method of load factor .** When you know the number of elements that need to be put in, you can specify it first to avoid performance waste caused by multiple expansion .**

```
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
```

## The core approach public V get(Object key)

Parameters key, And it's time to key Of hash

First determine whether the array has been initialized , And the array length .

In judging tab[(n - 1) & hash], The sentence mentioned above , use key Of hash Take the length of the remainder array to determine whether there are elements in the position of the array .

- There is no element

There is no element in the array , There must have been no hash Conflict , Then the element must not exist - There are elements in the current position of the array

Judge key Of hsah Equal and （key The address is equal to or equals equal ）. Then you can make sure that the elements are in the array . - There are elements in the current position of the array , however key It's not equal

The next step is to determine whether the current position in the array exists next Elements （Node The node structure ）, If there is next Indicates that there is a linked list or tree structure .

Then judge Node Whether it is TreeNode, If so, the result is obtained by traversing the tree , If not, the result is obtained by traversing the linked list .

```
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab = table;
Node<K,V> first = tab[(n - 1) & hash];
Node<K,V> e = first.next;
int n = tab.length;
K k;
// Whether the array has been initialized
if (tab!= null && n > 0 && first != null) {
//table Whether there are nodes in ,key Whether it is equal or not
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
//key It's not equal , To determine if there is next, And determine whether it is the node of the tree or the node of the linked list , And then traverse in different ways to get
if (e != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
```

## The core approach public V put(K key, V value)

put The method is longer , Analyze in several cases

- for the first time put Elements , Array is not initialized yet ： call resize() Initialize array , Put it directly in table Corresponding position .(resize The expansion method is very important )
- table This position does not produce Hash Conflict ： Construct nodes into table in
- produce Hash Conflict , First judge table Middle node element key Whether it is equal or not , If equal, replace value
- produce Hash Conflict , Node is TreeNode： Insert nodes in the way of a red black tree
- produce Hash Conflict , Node is Node： Construction nodes are inserted in the form of a linked list , And check whether it reaches the threshold of turning to red black tree after inserting 8

```
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n;
int i;
// for the first time put Elements , Array is not initialized yet
if ((tab = table) == null || (n = tab.length) == 0)
// call resize() Initialize array
n = (tab = resize()).length;
//table This position does not produce Hash Conflict
if ((p = tab[i = (n - 1) & hash]) == null)
// Construct nodes into table in
tab[i] = newNode(hash, key, value, null);
else {
// produce Hash Conflict
Node<K,V> e; K k;
//table Middle node element key Whether it is equal or not
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// Record the node references , Follow up replacement E The value of the node
e = p;
else if (p instanceof TreeNode)
// Node is TreeNode： Insert nodes in the way of a red black tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// Node is Node, List situation
for (int binCount = 0; ; ++binCount) {
// Traversing to the end of the list has not found the same key, Then the construction node is inserted into the linked list
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
// Check whether the threshold value of turning to red black tree is reached after insertion 8
treeifyBin(tab, hash);
break;
}
// Check if there is the same key, Quit if you have one ,e = p.next It has been recorded E References to
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// In each of these cases , If it's not an insertion node
// There is key In the same case , Complete the replacement of a value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
return oldValue;
}
}
// Check whether expansion is needed Number of existing >hashmap Capacity * The load factor needs to be expanded
if (++size > threshold)
resize();
return null;
}
```

## The core approach Node<K,V>[] resize()

The most important part is coming , It's also the interviewer's favorite question HashMap Expansion of

- Called the first time it is initialized
- Number of key value pairs stored >hashmap Capacity * The load factor needs to be expanded

## Call... At initialization time resize

After expansion, we get a Node Array . Because of the first initialization , There must be no linked list , Red and black trees , as well as Node Node . It's just assigning values to some properties , And return an empty Node Array .**threshold**：HashMap The maximum number of key value pairs that can withstand ; If capacity and load factor are specified , be threshold = Specified capacity * Load factor ;**Node<K,V>[] table**： Deposit Node Array of , Created a capacity for 16（ When no specific capacity is specified , The default is 16） Of Node Array .

Omit parts of code that are irrelevant to the first initialization, unimportant code

```
final HashMap.Node<K,V>[] resize() {
//16*0.75=12
threshold = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
//16
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[DEFAULT_INITIAL_CAPACITY];
table = newTab;
return newTab;
}
```

## Expand call resize The key is coming.

First delete some code that has nothing to do with the expansion

```
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// The capacity and threshold are doubled
newCap = oldCap << 1;
newThr = oldThr << 1;
}
// Set threshold properties
threshold = newThr;
// The new one is twice the size of the previous one Node Array
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// Attribute assignment
table = newTab;
// Finish some preparation , Start preparing for migration before nodes
if (oldTab != null) {
// Cycle migration of each node data
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// Not every position in an array has elements
if ((e = oldTab[j]) != null) {
// Data needs to be migrated ,table The corresponding position is empty
oldTab[j] = null;
// There is no linked list
if (e.next == null)
// Fast recovery of new capacity , Put it in the right place
newTab[e.hash & (newCap - 1)] = e;
// Tree structure （ More complex, follow-up analysis ）
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// Chain table structure
else {
// Do not need to move the head and end of the list pointer
Node<K,V> loHead = null, loTail = null;
// The head and tail pointer of the linked list that needs to be moved
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// Traversing the linked list will split a list into two linked lists , Here we mainly analyze the basis of splitting
do {
next = e.next;
// The remainder after expansion is the same as before , Nodes that don't need to move .
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
// The remainder after expansion is inconsistent with the previous one , Nodes that need to be moved .
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// Put the list back in table Array
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
```

Here we mainly analyze the basis of the split .

When you want to split the data in the linked list , And assigned to different table In the subscript . What is clear is that , The expansion should not affect get Method , So according to get Method key Of hash Take the remaining capacity to get the following two pictures .** Before dismantling **

** After dismantling **

## Read a line of code in the expansion

```
(e.hash & oldCap) == 0
```

When the element of hash &oldCap（ As mentioned above, the capacity is 2^n, Its binary is 1000…）.

Take a few examples

5&16 ==0

21&16 ！=0

69&16 ==0

**Hash Values are structured around the red box ： Can be seen as On the left Y+table Capacity + On the right X,Y It's an even multiple of capacity ,X Less than the capacity value **, From the above example, we can see whether the result is 0 Depending on where the red box is 0 still 1.

- by 0 The result is always 0

Y Is an even multiple of the capacity. After expansion, the remainder remains unchanged 0, Remainder is X, The remainder is the same as before , No need to move . - by 1 The result is not 0

Y Is an even multiple of the capacity. After expansion, the remainder remains unchanged 0, The remainder is the capacity value +X, The remainder after expansion is inconsistent with the previous one , Need to move , The position after moving is the capacity +X（ The value of the previous position ）.

## Last

Welcome to the official account ： Bright future , Receive the first tier factory Java Interview question summary + Learning and thinking guidance of each knowledge point + One copy 300 page pdf Document Java Summary of core knowledge points ！