The overview

variable

  • SerialVersionUID: serializes
  • DEFAULT_INITIAL_CAPACITY: the default capacity is 16
  • MAXIMUM_CAPACITY: maximum capacity 2^30(integer maximum value 2^31-1, minimum value -2^31)
  • DEFAULT_LOAD_FACTOR: the default load factor is 0.75
  • TREEIFY_THRESHOLD: 8
  • UNTREEIFY_THRESHOLD: 6(red and black tree spinner threshold)
  • MIN_TREEIFY_CAPACITY: 64(minimum enabled red-black tree capacity threshold)
  • Table: stores data
  • Holds cached entrySet()
  • Size: indicates the current map size
  • ModCount: indicates the number of changes
  • Threshold: The next size value at which to resize (capacity * load factor)
  • LoadFactor: indicates the loadFactor

The inner class

  • Iterator HashIterator KeyIterator ValueIterator EntryIterator
  • Parallel iterator HashMapSpliterator KeySpliterator ValueSpliterator EntrySpliterator

methods

Initialize the

  • HashMap(Map<? extends K, ? extends V> m)
  • HashMap()
  • HashMap(int initialCapacity)
  • HashMap(int initialCapacity, float loadFactor)
Static final int tableSizeFor(int cap) {int n = cap-1; n |= n >>> 1; / / that the former one is 1 n | = n > > > 2. / / that the former two are 1 n | = n > > > 4. / / that the first four bits are 1 n | = n > > > 8; Eight before / / that is 1 n | = n > > > 16; Return (n < 0)? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }Copy the code

insert

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
Copy the code

The hash function

static final int hash(Object key) { int h; Return (key == null)? Return (key == null) 0 : (h = key.hashCode()) ^ (h >>> 16); }Copy the code

It’s putVal

/** * 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, * @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) / / table is null or a table without initialization data table n = (TAB = the resize ()). The length; If (p = TAB [I = (n-1) &hash]) == null) // I = (n-1) &hash TAB [I] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key ! = null &&key. equals(k)))) //key exists e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { 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 treeifyBin(TAB, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key ! = null &&key. equals(k)))) //key exists break; p = e; } } if (e ! = null) { // existing mapping for key V oldValue = e.value; if (! OnlyIfAbsent | | oldValue = = null) / / onlyifavsent = true does not change the original values e.v alue = value; afterNodeAccess(e); return oldValue; } } ++modCount; If (++size > threshold) // Whether to expand resize(); afterNodeInsertion(evict); return null; }Copy the code

Key function resize()

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) {// The capacity reaches its maximum and cannot be expanded. Threshold = integer. MAX_VALUE; return oldTab; Else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // Threshold *2 newThr = oldThr << 1; // double threshold} else if (oldThr > 0) // Initial capacity was placed in threshold newCap = oldThr; // Zero initial threshold using defaults 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); } // The new threshold is assigned to the threshold variable 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) { Node<K,V> e; if ((e = oldTab[j]) ! OldTab [j] = null; oldTab[j] = null; NewTab [e.hash & (newcap-1)] = e; newTab[e.hash & (newcap-1)] = e; Else if (e instanceof TreeNode) // is a TreeNode ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); J + oldCap Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //010000 16 //100000 32 //16 =3+16, 3 //hash 10011 //hash 00011 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.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

The splitting of red-black trees

// The node is assigned to the current position j or j + oldCap, just like the list. Final void split(HashMap<K,V> map, Node<K,V>[] TAB, int index, int bit) {TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; for (TreeNode<K,V> e = b, next; e ! = null; e = next) { next = (TreeNode<K,V>)e.next; e.next = null; if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } if (loHead ! = null) { if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead ! = null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead ! = null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead ! = null) hiHead.treeify(tab); }}}Copy the code