This article is participating in the Java Theme Month – Java Debug Notes EventActive link
preface
HashMap is a must-ask question in an interview, and is often used in daily development, so reading source code is necessary. This article will introduce it from all aspects.
The body of the
JDK versions 1.8.0_181 and 1.7 are used for this article
Version 1.8
A constructor
// no argument constructor
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// Specify the container to initialize the array capacity
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// Specifies the capacity of the container's initialization array
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;
// Assign the value passed in tableSizeFor to threshold;
this.threshold = tableSizeFor(initialCapacity);
}
Copy the codeNote:
- Instead of initializing the array in the container, we simply assign the number passed to threshold;
- You also need to note that tableSizeFor is a method that automatically changes the value passed in to an integer to the power of 2;
Add methods
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
Copy the codeNote:
- Note that the hash method returns 0 if the key is null.
The second method:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// Check whether the current container array is initialized
if ((tab = table) == null || (n = tab.length) == 0)
// Initialize the container array
n = (tab = resize()).length;
// Check whether there is any data in the index position of the array. If there is no data in the index position of the array, put the number directly into the array as a header
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// Determine whether the stored object matches the head node of the list at that location
if(p.hash == hash &&((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// Determine whether the data structure where the object is stored is a red-black tree
else if (p instanceof TreeNode)
// Save to red black tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// A list of loop seats
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// Add the node to the end of the list
p.next = newNode(hash, key, value, null);
// Determine whether to convert the list to a red-black tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// Convert the list to a red-black tree
treeifyBin(tab, hash);
break;
}
// Check whether the object exists in the linked list and replace it
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// Check if there are any stored objects in the linked list
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
// Return the original value
return oldValue;
}
}
++modCount;
// Determine whether the storage object meets the capacity expansion standard
if (++size > threshold)
// Here is the capacity expansion
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeNote:
- Note the resize method, which actually initializes and expands the container
- The red-black tree in the container is implemented using TreeNode
- The list insert here is the end of the insert
- Deciding whether to turn the list into a red-black tree is based on the TREEIFY_THRESHOLD property, and the transformation calls the treeifyBin method
- AfterNodeAccess and afterNodeInsertion are implemented in LinkedHashMap, so you need to understand the LinkedHashMap. Because the stored object exists in the container, the afterNodeAccess method is called, and the node corresponding to the stored object is ranked last, indicating that it has just been used. Because in the objects in the container does not exist, so is joined to a node, so call afterNodeInsertion method, will remove the head the LinkedHashMap node;
The resize method
This method is mainly for initialization or 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;
// Determine whether to expand the capacity
if (oldCap > 0) {
// Determine whether the array reaches its maximum value
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// Make it twice as big as before
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// Determine if capacity is specified during construction
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// DEFAULT_INITIAL_CAPACITY16 is used if the array is not specified
newCap = DEFAULT_INITIAL_CAPACITY;
// Set container expansion criteria to default values (initial length * load factor; That's 3/4 of the length of the array.
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// If the capacity is specified when constructing the container, the capacity criterion is set to 3/4 of the specified value
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"})
// Construct a new array after expansion
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// Check if there is data in the original array
if(oldTab ! =null) {
// Loop through each node in the original array
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
/ / empty
if((e = oldTab[j]) ! =null) {
oldTab[j] = null;
// If this node has only one object, it goes directly to the corresponding location in the new array
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// Check whether the node is a red-black tree
else if (e instanceof TreeNode)
// Split the red-black tree and put it into a new array
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// Split the list of nodes into two nodes in the new array
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 codeNote:
- The data from the original array will be stored in the new array in only two nodes;
- The size of the array is doubled
TreeifyBin method
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// Check whether the array length reaches the treeization standard MIN_TREEIFY_CAPACITY=64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// Walk through the list and convert it to a tree, not a red-black tree
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)
// Convert the red-black treehd.treeify(tab); }}Copy the codeNote:
- To turn a list into a red-black tree does not require a list length of 8, but an array length of 64 or more
The get method
public V get(Object key) {
Node<K,V> e;
// Check whether the node exists in the container, return value if, return null if not
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the codeGetNode method
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// Determine the length of the array and whether the bucket corresponding to the index is also empty
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
// Check whether it is the first node in the bucket
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
// Determine if there is a next node
if((e = first.next) ! =null) {
// Check whether it is a tree
if (first instanceof TreeNode)
// Look up the tree structure
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {// walk through the list to find
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
Copy the codeThe flow chart of the put
The flow chart of the get
1.7 is compared with 1.8
- The data structure
1.7 Use array and linked list data structures 1.8 use array, linked list and red-black tree data structures
- Initialization and capacity expansion
1.7 the use of
- Data insertion mode
1.7 Insert data into the head node using the head insertion method. 1.8 Add data to the end of the linked list using tail interpolation, even for expansion
- Hash method
1.8 uses a bit operation plus an XOR operation; 1.7 Four bit operations plus five xOR operations are performed;