1. Explain the hashMap principle
2. Put method
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// TAB: the current haskmap hash table
//p: represents the element of the current hash table
//n: indicates the length of the hash table
// I: indicates the route addressing result
Node<K,V>[] tab; Node<K,V> p; int n, i;
// Lazy initialization logic that initializes the most memory-consuming hash table in the HashMap object the first time putVal is called
if ((tab = table) == null || (n = tab.length) == 0)
//resize() : expansion method of hash
n = (tab = resize()).length;
,v>
,v>
,v>
,v>
,v>
,v>
Hash (n -1) hash (n -1) hash (n -1) hash (n -1) hash (n -1) hash (n -1) hash
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//e: node temporary element. If e is not null, an element with the same key as the current
is found
,v>
//k: temporary key
Node<K,V> e; K k;
// The element representing the current position of the bucket is the same as the key of the element you want to insert, indicating that the replacement will be performed later
Key == equals == ==
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// List operations
for (int binCount = 0; ; ++binCount) {
//
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// Tree operation
treeifyBin(tab, hash);
break;
}
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// if e is not null, an element with the same key as the current
is found and replaced
,v>
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
returnoldValue; }}//modCount: The number of times the structure of the hash table has been modified, not counting the value of the node element
++modCount;
// Insert a new element, and the size increases. When the capacity expansion threshold is reached, the capacity expansion is triggered
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the code2.1 Resize () Expansion method
/** * 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 offsets in the new table. * In order to solve the problem of chained query efficiency caused by hash conflicts, expansion can alleviate this problem * * Red-black tree is so good why not use it in the first place instead of linked list? * The linked list structure is simple, the tree takes up memory, and the insertion and deletion of red-black trees need to be re-balanced, which is not as efficient as the linked list *@return the table
*/
final Node<K,V>[] resize() {
//oldTab: indicates the hash table before capacity expansion
Node<K,V>[] oldTab = table;
//oldCap: the size of the table array before expansion
int oldCap = (oldTab == null)?0 : oldTab.length;
//oldThr: hash table capacity expansion threshold before capacity expansion
int oldThr = threshold;
//newCap: the size of the expanded table array
//newCap: indicates the new capacity expansion threshold
int newCap, newThr = 0;
// If the condition is true, the hash table in the hashMap has been initialized
if (oldCap > 0) {
// The table array before the expansion has reached the maximum threshold, and will not be expanded any more.
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//oldThr is moved one bit to the left to expand by x2,
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//oldCap == o indicates that the hashmap hash table is null
//1.new HashMap(initialCapacity,loadFactor)
//2.new HashMap(initialCapacity)
//3. New HashMap(map), where map has data
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//oldCap == o ，oldThr == 0
// Enter via new HashMap()
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;/ / 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);/ / 12
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// Major: Capacity expansion begins
@SuppressWarnings({"rawtypes"."unchecked"})
// Create a new array based on the calculated table length
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// Table is not null before capacity expansion
if(oldTab ! =null) {
for (int j = 0; j < oldCap; ++j) {
//e: temporary node
Node<K,V> e;
// The current node is not empty
if((e = oldTab[j]) ! =null) {
// The current node of the old array is null for GC collection
oldTab[j] = null;
/* If e,next is empty, this node has only one value, and a hash collision has occurred, * so the index position of the current position in the new array (e.hash & (newcap-1)), * is thrown into the new array. * /
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// A tree is a tree.
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// The bucket bit has formed a linked list
// Low order list: there is the index position of the expanded array, which is the same as the index position of the current array
Node<K,V> loHead = null, loTail = null;
// high-order list: subscript position of the expanded array: subscript position of the current array + array length before the expansion
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