JDK1.8 HashMap source code parsing, pure for personal understanding records, only for reference, if there are understanding ambiguates or errors, welcome to point out the discussion. (There will be time to improve, try to list all methods)
2021-07-25
- Added Overview of Underlying Data Structures
- Added Get Logic Briefs
A brief description of the underlying data structure
/* part of code omitted */
class Node<K.V> {
final int hash;
final K key;
V value;
Node next;
}
transient Node<K,V>[] table;
class TreeNode<K.V> extends LinkedHashMap.Entry<K.V> {}
class LinkedHashMap.Entry<K.V> extends HashMap.Node<K.V> {}
Copy the codeThe underlying HashMap is stored by Node[], which uses the hash value of the key as the index to locate data. A Node stores all data of the same hash value. When the number of hash collisions on the key (that is, the Node length) reaches a certain threshold, TREEIFY_THRESHOLD, and the current Node[] length is smaller than MIN_TREEIFY_CAPACITY, resize() is performed on Node[]. If the length of the current Node[] is greater than MIN_TREEIFY_CAPACITY, the Node to which the current hash index is located is converted into a TreeNode for storage. PS: TREEIFY_THRESHOLD is a static constant with the value of 8. PS: MIN_TREEIFY_CAPACITY is a static constant and the value is 64. PS: TreeNode is a red-black tree structure
Obtaining a logical brief
Locate the index position of the data to be obtained based on the hash value of the key. For the nodeNodePerforms a traversal, comparing the incoming key withNodeFind the node with the same key and return the key of that nodevalue.
Threshold Capacity expansion threshold. If the container size is specified during instantiation, the value will be assigned. If the container size is 0 during instantiation, the value will be 1.
/** * Returns a power of two size for the given target capacity. */
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 codeWhen we new a HashMap instance, we can give two values of type int initialCapacity and type float loadFactor. InitialCapacity is the capacity of HashMap, default is 1 << 4 = 16, loadFactor is the calculation factor of HashMap when judging expansion, default is 0.75F, The default capacity expansion threshold is loadFactor * initialCapacity = (1 << 4) x 0.75F. InitialCapacity can be 0 and loadFactor cannot be 0 at instantiation time
public V put(K key, V value)The source code parsing
/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * *@param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @returnthe previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) * /
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
Copy the codefinal V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)The source code parsing
Called by PUT (K key, V value)
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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)
/* * Check whether the current HashMap has a value, if not, initialize volume * table is the actual data structure, real stored data * resize() initialize or expand the current table * the size of the table is always a power of 2 */
// Current volume
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
/* * Based on the bit operation, calculate the index position that the key should hold. If there is no value in this position, create a new node and assign * the largest index and the key hash value to calculate the index value */
tab[i] = newNode(hash, key, value, null);
else {
/* * There is already a value in the array index calculated based on the key. * either the key value is identical * or the key value has the same hash but the actual content is different */
/* * TreeNode extends LinkedHashMap.Entry extends HashMap.Node */
Node<K,V> e; K k;
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
/* * In the first case, the hash is the same and the actual value of the key is the same */
e = p;
else if (p instanceof TreeNode)
/* * If the array object gets a TreeNode, use the TreeNode method to get value */
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
/* * Recursively handles assignment */
if ((e = p.next) == null) {
/* * If the hash value is the same but the actual value is different, and the value of the next node is empty, the value is directly assigned to the next node */
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
/* Recursion depth reaches predetermined threshold TREEIFY_THRESHOLD8 when converted to tree storage */
treeifyBin(tab, hash);
break;
}
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
/* If the hash value of the next node is equal and the actual key value is equal, the loop is broken */
break; p = e; }}if(e ! =null) { // existing mapping for key
/* * Finally calculate the key value exists, determine whether to use the new value to overwrite the old value, and return the old value */
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
/* * LinkedHashMap supports methods that are implemented in LinkedHashMap */
afterNodeAccess(e);
returnoldValue; }}// The number of changes is increased by one
++modCount;
/* * threshold Next capacity expansion size * If the current capacity is greater than the next capacity expansion threshold, expand the capacity */
if (++size > threshold)
resize();
//LinkedHashMap supports methods that are implemented in LinkedHashMap
afterNodeInsertion(evict);
return null;
}
Copy the codefinal void treeifyBin(Node<K,V>[] tab, int hash)The source code parsing
This is a tree approach, and it’s useful in a lot of places.
/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */
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)
/* * MIN_TREEIFY_CAPACITY Treification threshold * If the value is smaller than the threshold, resize() * Tree only when the array length exceeds the threshold */
resize();
else if ((e = tab[index = (n - 1) & hash]) ! =null) {
/* * Convert all next objects up to key to a tree, and associate the before and after node transitions */
/* * on the first loop, hd is null, tl is null, hd=p=e, tl=p=e, hd is time-invariant in subsequent recursions, that is, hd is the root of the Tree */
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)
/* * If the insertion position of the key has a value, proceed with the following operation which is unknown. * /hd.treeify(tab); }}Copy the codefinal void treeify(Node<K,V>[] tab)Is this really tree-like? It’s a little dizzy
/** * Forms tree of the nodes linked from this node. */
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x ! =null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
inth = x.hash; Class<? > kc =null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0)? p.left : p.right) ==null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
Copy the codefinal Node<K,V>[] resize()Initialize containers or copy expanded values
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
/* * The capacity expansion threshold is adjusted here, and the size is adjusted to 2 times */
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/* * The initial volume is 1 << 4 = 16 */
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if(oldTab ! =null) {
for (int j = 0; j < oldCap; ++j) {
/* * this looks like a recursive value copy */
Node<K,V> e;
if((e = oldTab[j]) ! =null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((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;
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 code