- HashMap source code analysis_jdk1.8 (2)
-
- Constructor
- put method
- resize expansion method
HashMap source code analysis_jdk1.8 (2)
Constructor
HashMap provides the following constructors:
/**
* Construct an empty HashMap with the specified initial capacity and load factor.
*
* @param initialCapacity initial capacity
* @param loadFactor load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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;
// If the user specifies a number as the capacity through the constructor, Hash will select the first power of 2 greater than the number as the capacity. (1->1, 7->8, 9->16)
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Construct an empty HashMap with the specified initial capacity and default load factor (0.75).
*
* @param initialCapacity initial capacity
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {<!-- -->
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Construct an empty HashMap with default initial capacity (16) and default load factor (0.75).
*/
public HashMap() {<!-- -->
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial sufficient capacity to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {<!-- -->
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
If the user specifies a number as the capacity through the constructor, Hash will select the first power of 2 greater than the number as the capacity. (1->1, 7->8, 9->16)
/**
* 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;
}
From the constructor, we can see that in the regular constructor, no memory space is allocated for the array table (there is an exception for the constructor whose input parameter is a specified Map), but the table array is actually constructed when the put operation is performed.
put method
/**
* Associate the specified value with the specified key in the map.
* If the map already contains the specified key, the value corresponding to the key will be overwritten by the new value.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the 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) {<!-- -->
// Calculate hash value based on key
return putVal(hash(key), key, value, false, true);
}
/**
* 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 table is null or has a length of 0, allocate memory space for the array table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Determine whether the inserted position conflicts. If there is no conflict, just use newNode and insert it into the array.
if ((p = tab[i = (n - 1) & amp; hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {<!-- --> // If the inserted hash value conflicts
Node<K,V> e; K k;
// Determine whether the elements in table[i] are the same as the inserted key. If they are the same, directly use the inserted value p to replace the old value e.
if (p.hash == hash & amp; & amp;
((k = p.key) == key || (key != null & amp; & amp; key.equals(k))))
e = p;
// Determine whether the inserted data structure is a red-black tree or a linked list. Here it means that if it is a red-black tree, then directly putTreeVal into the red-black tree
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//The data structure is a linked list
else {<!-- -->
// Traverse whether the table array exists
for (int binCount = 0; ; + + binCount) {<!-- -->
// There is no direct newNode(hash, key, value, null)
if ((e = p.next) == null) {<!-- -->
p.next = newNode(hash, key, value, null);
// Determine whether the length of the current linked list is greater than the threshold 8. If it is greater, the current linked list will be converted into a red-black tree.
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// If there is a loop, break out of the loop
if (e.hash == hash & amp; & amp;
((k = e.key) == key || (key != null & amp; & amp; key.equals(k))))
break;
p = e;
}
}
// If it exists, directly replace the old value with the new value
if (e != null) {<!-- --> // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
+ + modCount;
// Insertion is successful, determine whether expansion is needed
if ( + + size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
resize expansion method
/**
* table array initialization or length doubled. 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;
// Length of table array before expansion
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 & amp; & amp;
oldCap >= DEFAULT_INITIAL_CAPACITY)
// Expand the threshold to 2 times
newThr = oldThr << 1; // double threshold
}
// The threshold has been initialized, use it directly
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {<!-- --> // zero initial threshold signifies using defaults
// If there is no initialization threshold, initialize a default capacity and threshold.
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {<!-- -->
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY & amp; & amp; ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({<!-- -->"rawtypes","unchecked"})
//Create a new array with twice the original array length
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//The old data is saved in the new array
if (oldTab != null) {<!-- -->
for (int j = 0; j < oldCap; + + j) {<!-- -->
Node<K,V> e;
if ((e = oldTab[j]) != null) {<!-- -->
oldTab[j] = null;
// Only one node, directly mapped through the index position
if (e.next == null)
newTab[e.hash & amp; (newCap - 1)] = e;
// If it is a red-black tree, the tree needs to be split and then mapped
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {<!-- --> // preserve order
// If it is a linked list with multiple nodes, split the original linked list into two linked lists
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {<!-- -->
next = e.next;
// After expansion, if the new bit of the hash value that participates in the operation = 0, then the position of the element after expansion = the original position
if ((e.hash & amp; oldCap) == 0) {<!-- -->
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// After expansion, if the hash value adds a new bit that participates in the operation = 1, then the position of the element after expansion = original position + oldCap
else {<!-- -->
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// Linked list 1 is stored in the original index
if (loTail != null) {<!-- -->
loTail.next = null;
newTab[j] = loHead;
}
// Linked list 2 is stored in the original index plus the offset of the original hash bucket length.
if (hiTail != null) {<!-- -->
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
refer to:
https://zhuanlan.zhihu.com/p/79219960
https://www.cnblogs.com/theRhyme/p/9404082.html#_lab2_1_1