Article directory
- Detailed explanation of java HashMap source code
- HashMap source code
-
-
- 1 put method process
- 2 expansion
- 3 get method
-
Detailed explanation of java HashMap source code
Java HashMap is an implementation of the Map interface based on a hash table, which can store a data structure of key-value pairs. The characteristics of HashMap are:
- Allow null values and null keys
- The order of the elements is not guaranteed, nor is the order guaranteed to remain unchanged over time.
- Provides constant-time basic operations (get and put)
- There are two parameters that affect performance: initial capacity and load factor
- When the number of elements exceeds the product of the load factor and the current capacity, the capacity will be automatically expanded and elements will be reallocated.
- Supports multiple traversal methods, such as keySet, values, entrySet, etc.
- Not thread-safe, need to use Collections.synchronizedMap or ConcurrentHashMap to achieve synchronization
HashMap source code
1 put method process
public V put(K key, V value) {<!-- -->
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;
//Determine whether the array is not initialized
if ((tab = table) == null || (n = tab.length) == 0)
//If not initialized, call the resize method to initialize
n = (tab = resize()).length;
//Find the array subscript of the data (key) through the & amp; operation and determine whether there is data at the subscript position
if ((p = tab[i = (n - 1) & amp; hash]) == null)
//If not, place the data directly at the subscript position
tab[i] = newNode(hash, key, value, null);
//The array subscript contains data
else {<!-- -->
Node<K,V> e; K k;
//Determine whether the key of the location data is the same as the new data
if (p.hash == hash & amp; & amp;
((k = p.key) == key || (key != null & amp; & amp; key.equals(k))))
//If the same, it proves that it is a modification operation, and the data of the node is assigned to e, which will be used later.
e = p;
//Determine whether it is a red-black tree
else if (p instanceof TreeNode)
//If it is a red-black tree, perform the operation of the red-black tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//The new data is neither the same as the current array, nor is it a red-black tree node, proving that it is a linked list
else {<!-- -->
//Traverse the linked list
for (int binCount = 0; ; + + binCount) {<!-- -->
//Judge the next node. If it is empty, it proves that the end of the linked list has been traversed.
if ((e = p.next) == null) {<!-- -->
//Put the new value at the end of the linked list
p.next = newNode(hash, key, value, null);
//Because a new piece of data has been inserted, determine whether the length of the linked list is greater than or equal to 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//If yes, perform conversion operation to red-black tree
treeifyBin(tab, hash);
break;
}
//Judge whether there are values with the same data in the linked list. If they are the same, it proves to be a modification operation.
if (e.hash == hash & amp; & amp;
((k = e.key) == key || (key != null & amp; & amp; key.equals(k))))
break;
//Assign the next node to the current node
p = e;
}
}
//Determine whether e is empty (e value is the variable used to store the original data during the modification operation)
if (e != null) {<!-- --> // existing mapping for key
//If it is not empty, it proves that it is a modification operation and takes out the old value.
V oldValue = e.value;
//Will definitely be executed onlyIfAbsent passes in false
if (!onlyIfAbsent || oldValue == null)
//Assign the new value to the current node
e.value = value;
afterNodeAccess(e);
//return old value
return oldValue;
}
}
//Counter, calculate the number of modifications of the current node
+ + modCount;
//If the number of data in the current array is greater than the expansion threshold
if ( + + size > threshold)
//Perform expansion operation
resize();
//Empty method
afterNodeInsertion(evict);
//Return null value when adding operation
return null;
}
2 Capacity expansion
//Expand and initialize array
final Node<K,V>[] resize() {<!-- -->
Node<K,V>[] oldTab = table;
//If the current array is null, set the oldCap old array capacity to 0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//Old expansion threshold
int oldThr = threshold;
int newCap, newThr = 0;
//Determine whether the array capacity is greater than 0. If it is greater than 0, it means that the array has been initialized.
if (oldCap > 0) {<!-- -->
//Determine whether the current array length is greater than the maximum array length
if (oldCap >= MAXIMUM_CAPACITY) {<!-- -->
//If yes, set the expansion threshold directly to the maximum value of the int type and return it directly
threshold = Integer.MAX_VALUE;
return oldTab;
}
//If it is within the maximum length range, it needs to be expanded. OldCap << 1 is equivalent to oldCap*2
//After the operation, determine whether it is the maximum value and oldCap needs to be greater than 16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY & amp; & amp;
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold is equivalent to oldThr*2
}
//If oldCap<0, but it has been initialized, such as after deleting the element, then its critical value must still exist. If it is initialized for the first time, its critical value will be 0.
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//If the array is not initialized, set the threshold and expansion factor to the default values.
else {<!-- --> // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//When the initial capacity is less than 16, the expansion threshold is not assigned a value.
if (newThr == 0) {<!-- -->
//Create threshold
float ft = (float)newCap * loadFactor;
//Determine whether the new capacity and new threshold are greater than the maximum capacity
newThr = (newCap < MAXIMUM_CAPACITY & amp; & amp; ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//Calculated threshold assignment
threshold = newThr;
@SuppressWarnings({<!-- -->"rawtypes","unchecked"})
//Create a new array based on the capacity calculated above
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//assignment
table = newTab;
//Expansion operation, judging whether it is not empty proves that it is not an initialized array
if (oldTab != null) {<!-- -->
//Iterate through the array
for (int j = 0; j < oldCap; + + j) {<!-- -->
Node<K,V> e;
//Determine if the current array with subscript j is not empty, assign a value e, and proceed to the next step.
if ((e = oldTab[j]) != null) {<!-- -->
//Make the array position empty
oldTab[j] = null;
//Determine whether there is a next node
if (e.next == null)
//If not, recalculate the subscript in the new array and put it in
newTab[e.hash & amp; (newCap - 1)] = e;
//There is the next node, and determine whether it has been treed
else if (e instanceof TreeNode)
//Perform red-black tree operations
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//There is a next node, and there is no tree (linked list form)
else {<!-- -->
//For example, the old array capacity is 16, then the subscript is 0-15
//Expansion operation*2, the capacity becomes 32, and the subscript is 0-31
//Low bit: 0-15, high bit 16-31
//Four variables are defined
// Low bit header, low bit tail
Node<K,V> loHead = null, loTail = null;
// High bit header High bit tail
Node<K,V> hiHead = null, hiTail = null;
//next node
Node<K,V> next;
//Loop through
do {<!-- -->
//Remove next node
next = e.next;
//Calculated through AND operation, the result is 0
if ((e.hash & amp; oldCap) == 0) {<!-- -->
//If the low-order tail is null, it proves that the current array position is empty and there is no data.
if (loTail == null)
//Put the e value into the low bit header
loHead = e;
//The low-order tail is not null, which proves that there is already data
else
//Put the data into the next node
loTail.next = e;
//Record low-order tail data
loTail = e;
}
//Calculated through AND operation, the result is not 0
else {<!-- -->
//If the high-order tail is null, it proves that the current array position is empty and there is no data.
if (hiTail == null)
//Put the e value into the high bit header
hiHead = e;
//The high-order tail is not null, which proves that there is already data
else
//Put the data into the next node
hiTail.next = e;
//Record high-order tail data
hiTail = e;
}
}
//If e is not empty, it proves that the end of the linked list has not been reached and the loop continues.
while ((e = next) != null);
//If there is data recorded at the low end, it is a linked list
if (loTail != null) {<!-- -->
//Make the next element empty
loTail.next = null;
//Put the low-bit header into the original subscript position of the new array
newTab[j] = loHead;
}
//If there is data recorded at the high end, it is a linked list
if (hiTail != null) {<!-- -->
//Make the next element empty
hiTail.next = null;
//Put the high-bit header into the (original subscript + original array capacity) position of the new array
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//return new array object
return newTab;
}
3 get method
public V get(Object key) {<!-- -->
Node<K,V> e;
//hash(key), get the hash value of key
//Call the getNode method, see the method below
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {<!-- -->
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//Find the bucket subscript corresponding to the key and assign it to the first node
if ((tab = table) != null & amp; & amp; (n = tab.length) > 0 & amp; & amp;
(first = tab[(n - 1) & amp; hash]) != null) {<!-- -->
//Determine whether the hash value and key are equal. If so, return directly. There is only one data in the bucket (in most cases)
if (first.hash == hash & amp; & amp; // always check first node
((k = first.key) == key || (key != null & amp; & amp; key.equals(k))))
return first;
if ((e = first.next) != null) {<!-- -->
//This node is a red-black tree, so you need to find data through the red-black tree.
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//In the case of a linked list, you need to traverse the linked list to find data
do {<!-- -->
if (e.hash == hash & amp; & amp;
((k = e.key) == key || (key != null & amp; & amp; key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}