catalogue
1. data structure
- 1.7 array + linked list
- 1.8 data + linked list + red black tree (the linked list is greater than 8 and the total length is greater than 64)
2. relevant interview questions
-
What optimizations have been made during the capacity expansion of JDK 1.8 HashMap?
-
Determine that the element needs to be moved through the high-order operation (e.hash & oldcap), for example:
key1 The information is as follows: - key1.hash = 10 0000 1010 - oldCap = 16 0001 0000 apply e.hash & oldCap The higher bit of the result is 0 When the result is 0, it means that the position of the element will not change during capacity expansion key2 The information is as follows: - key2.hash = 10 0001 0001 - oldCap = 16 0001 0000 apply e.hash & oldCap The higher one of the results is 1 When the result is 1, Indicates that the element is expanding, Position changes, The new subscript position is equal to the original subscript position + Original array length
-
-
Why is the load factor 0.75?
-
The initial capacity of the HashMap is 16, 16 * 0.75 (load factor) = 12. When the elements in the HashMap reach 12, the capacity will be expanded
-
The load factor of 0.75 is the result of the balance between capacity and performance
-
When the load factor setting is relatively large, the threshold for capacity expansion is raised. The frequency of capacity expansion is relatively low. Although the occupied space will be relatively small, the probability of Hash conflicts will increase. Therefore, more complex data structures are required to store elements, which will increase the operation time for elements and reduce the operation efficiency
-
When the load factor value is small, the threshold for capacity expansion will be low, so more space will be occupied. At this time, the storage of elements will be sparse, the possibility of sending Hash conflicts will be small, and the operation performance will be high
-
-
-
How does HashMap find and confirm elements when there are hash conflicts?
- In case of hash conflict, we need to judge whether the key value is equal to confirm whether this element is the element we want
-
What are the important methods in the HashMap source code?
-
query
public V get(Object key){ Node<K, V> e; // Hash key 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; // Non null judgment if((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash)] != null){ // Determine whether the first element is the element to query if(first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))){ return first; } // Next node non empty judgment if((e = first.next) != null){ // If the first node is a tree structure, use getTreeNode to directly obtain the corresponding data if(first instanceof TreeNode){ return ((TreeNode<K, V>)first).getTreeNode(hash, key); } do{ // Non tree structure, cyclic node judgment // If the hash es are equal and the key s are the same, this node is returned if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){ return e; } }while((e = e.next) != null); } } return null; } -
New
public V put(K key, V value){ // Hash key 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; // Create a table if the hash table is empty if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // Calculate the array index i to be inserted according to the hash value of the key if ((p = tab[i = (n - 1) & hash]) == null) // If table[i] equals null, insert directly tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // If the key already exists, directly overwrite value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // If the key does not exist, judge whether it is a red black tree else if (p instanceof TreeNode) // Red black tree directly inserts key value pairs e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // For the linked list structure, the loop is prepared for insertion for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // If the length of the linked list is greater than 8, it will be converted into a red black tree for processing if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // key already exists, directly overwriting value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // Exceed the maximum capacity and expand the capacity if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
-
-
Capacity expansion
final Node<K,V>[] resize() { // Array of expanders Node<K,V>[] oldTab = table; // Size and threshold of array before capacity expansion int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; // Predefine the size and threshold of the new array int newCap, newThr = 0; if (oldCap > 0) { // If the maximum value is exceeded, the capacity will not be expanded if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // Expand the capacity by twice the current capacity, but not more than maximum_ Capability else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; } // The current array has no data, use the initialized value else if (oldThr > 0) newCap = oldThr; else { // If the initialization value is 0, the default initialization capacity is used newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // If the new capacity equals 0 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]; // Start capacity expansion and assign the new capacity to table table = newTab; // The original data is not empty. Copy the metadata to the new table if (oldTab != null) { // Copy non empty elements to the new table according to the capacity cyclic array for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // If there is only one linked list, copy directly if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // Red black tree related operations ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // Linked list replication, JDK 1.8 capacity expansion and optimization Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // Original index if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // Original index + oldCap else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // Put the original index into the hash bucket if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } -
How does HashMap cause an infinite loop?
-
Reason:
- JDK1.7 linked list is inserted in reverse order
- JDK1.8 has been improved to the tail positive sequence insertion
-
case
/** * JDK1.7 * Assume that the default size of HashMap is 2 * Originally, there was an element key(5) in the HashMap * Two more threads are used: * t1 Add element key(3) * t2 Add element key(7) * After the elements key(3) and key(7) are added to the HashMap * Thread t1 executes to entry<k, v> next = e.next; Hour * Surrendered the right to use the CPU */ void transfer(Entry[] newTable, boolean rehash){ int newCapacity = newTable.length; for(Entry<K, V> e : table){ while(null != e){ // Thread 1 executes here Entry<K, V> next = e.next; if(rehash){ e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } } /** * When t1 regains the right to execute * First execute newTable[i] = e to set the next of key(3) to key(7) * The next element of key(7) found in the next cycle is key(3) * Thus, a circular reference of key(3) and key(7) is formed * This leads to the occurrence of the dead cycle */
-
3. JDK1.8 source code contains attributes
// HashMap initialization length
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap maximum length
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824
// Default load factor (expansion factor)
static final int DEFAULT_LOAD_FACTOR = 0.75f;
// The critical value for converting the red black tree. When the length of the linked list is greater than this value, the linked list structure will be converted to the red black tree structure
static final int TREEIFY_THRESHOLD = 8;
// The critical value of the conversion linked list. When the element is less than this value, the red black tree structure will be converted into a linked list structure
static final int UNTREEIFY_THRESHOLD = 6;
// Minimum tree capacity
static final int MIN_TREEIFY_CAPACITY = 64;