background

HashMap is used ridiculously often in normal work. Unfamiliar? What are you not familiar with everyday?

During the interview, interviewer: Oh, can you tell me how it works at the bottom? I: Well, I remember that it is stored into an array by hash calculation, as well as the conversion process of linked lists and red-black trees, loading factors, etc., the specific implementation is not very clear, usually have read a lot of articles on the Internet, but don’t remember.

However, in order to improve themselves in essence, we still need to settle down and learn deeply. Only with a solid foundation can we better use it in our daily work

This paper will learn from the following aspects:

• Basic principle: From the overall point of view, a brief introduction to the principle of HashMap and some concepts involved
• Operation APIS: the main details are constructors, inserts, deletes, traversals, etc
• Comparison with other Hash tables: Compare with other sets in the Map series for better understanding

First, basic principles

AbstractMap HashMap inherits the AbstractMap class and implements the Map interface.

Here’s a picture from the Internet:

Description:

1. When callingPut (key, value), the HashMap will matchkeyforhashOperation to gethashValue, and then underhashValue mod the length of the array (internally optimized by bitwise) to get the index of the array.
2. encapsulationKey, Value, hash, and nextfornodeNode, if the array subscript does not have an element, then theNodeThe node is stored in an array subscript.
3. If there is an element, check whether it is a red-black tree node. If there is a tree node, insert the new node into the red-black tree.
4. If it is not a tree node, insert the new node at the end of the list. Also, when the length of the linked list> 8, because the time complexity of linked list query isO(N), so the linked list will be turned into a red-black tree, and the time complexity will be O(logN), thus improving the query efficiency.
5. whenremoveAfter removing a node from a red-black tree, if the number of nodes in the red-black treeThe < 6In order to save memory space, the red-black tree will degenerate into a linked list.

Red black tree is a kind of balanced binary search tree. It is a special binary search tree. For any node, the value of any node in the left subtree is smaller than it, and the value of any node in the right subtree is larger than it (the left is smaller than the right is larger). In the face of frequent data operations, red-black trees can always keep the left and right subtrees in a symmetric state on the whole, so the insertion, deletion and query can be completed efficiently. The time complexity is O(logN), and N is the number of nodes, which is very stable.

1.1 Grooming storage Nodes

Storage nodes in a HashMap include Entry, Node, TreeNode, and LinkedHashMapEntry. The dependencies are as follows:

Understand the content of the node to help you understand!

1.2 Constants and member variables

Constant: // Initial length of array: 16. Static final int DEFAULT_INITIAL_CAPACITY = 1< < 4; static final int DEFAULT_INITIAL_CAPACITY = 1< < 4; Static final int MAXIMUM_CAPACITY =1 << 30; Static final float DEFAULT_LOAD_FACTOR = 0.75f; Static final int TREEIFY_THRESHOLD = 8; static final int TREEIFY_THRESHOLD = 8; Static final int UNTREEIFY_THRESHOLD = 6; static final int UNTREEIFY_THRESHOLD = 6; // The minimum tree-based capacity threshold for the array. When the length of a zipper is too long, if the array length does not reach 64, it is preferred to expand rather than tree. static final int MIN_TREEIFY_CAPACITY = 64; Member variable: // Transient int size; // Next capacity expansion threshold. Formula: Capacity * load factor int threshold; // loadFactor final float loadFactor;Copy the code

Understand the meaning of some important constants and member variables for subsequent understanding!

Second, operation API

2.1 Construction method

2.1.1 Empty parameter Construction

public HashMap() {
    
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the code

Only a load factor of 0.75 is initialized. All other values are default.

2.1.2 Parametric construction

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: "+ // The initial length of the array cannot exceed the limit initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // The threshold for initialization or expansion must be a power of 2. // Note: Since initialCapacity can be passed externally, the value may be 3. TableSizeFor ensures that threshold is always a power of 2. this.threshold = tableSizeFor(initialCapacity); }Copy the code

Let’s focus on the tableSizeFor method.

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 code

Principle: Returns the minimum value of 2^n (2 to the NTH power) based on the given cap array capacity. What is the value of n? That depends on the value of cap.

Here’s an example:

• Cap = 0, threshold = 1. Two to the zero
• Cap = 1, threshold = 1. Two to the first
• Cap = 3, threshold = 4. Two to the second, two to the third definitely doesn’t work.
• Cap = 4, threshold = 4. Since 4 is a power of 2, it doesn’t change.
• Cap = 5, threshold = 8. Two to the third

So that makes sense. The purpose of this function is to prevent an external cap that does not match 2^n, so adjust.

The member variable is defined as threshold=capacity * load factor. Why is it now equal to tableSizeFor? It is true that threshold has a value at this time, but it is useless. It will only be used during expansion. Take a look at the expansion code:

final Node<K,V>[] resize() { // ... //1, threshold=4 int oldThr = threshold; / /... Else if (oldThr > 0) // Initial capacity was placed in threshold New HashMap(3) //2, threshold=4,newCap=4 newCap= oldThr; / /... Omitted if (newThr == 0) {//3, newCap=4, newThr=3 float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //4,threshold=3 threshold = newThr; / /... omitCopy the code

Don’t panic yet! Regardless of the expansion, let’s just look at the first four steps.

1. Suppose wenew HashMap(3). thenthreshold=4.
2. After four steps, the comments are clear
3. And finally, the size of the array is 4, andthresholdIt becomes 3. So follow the formula to understand is no problem!

So, you know, you don’t have to worry about this.

2.2 Insert element put() method

The put method calls putVal, so let’s focus on the internals of putVal.

2.2.1 putVal method

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 the array is null, it is initialized. (put the first time, must be null) if ((TAB = table) = = null | | (n = TAB. Length) = = 0) / / 2, initialize the array, N = (TAB = resize()).length; If ((p = TAB [I = (n-1) &hash]) == null) //null: this is the first node. If (p = TAB [I = (n-1) &hash]) == null) Next TAB [I] = newNode(hash, key, value, null); Else {// 4; Node<K,V> e; K k; // 4.1, first compare whether the hash and key values of the head node are equal to those of the hash and key to be inserted. if (p.hash == hash && ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p; Else if (p instanceof TreeNode) // 4.2; e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); Else {// 4.3, neither a head node nor a binary tree node. For (int binCount = 0; ; ++binCount) {if ((e = p.ext) == null) {p.ext = newNode(hash, key, value, null); If (binCount >= treeify_threshold-1) // -1 for 1st treeifyBin(TAB, hash); break; } //4.4 If a node in the list matches, then break the loop and the node to be inserted already exists! if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) break; p = e; }} //4, if the node already exists, update value if (e! = null) {// existing mapping for key // update V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; AfterNodeAccess (e); afterNodeAccess(e); return oldValue; // Return the element if it already exists. }} //6, only new elements will be inserted into this logic, ++modCount; If (++size > threshold) resize(); if (++size > threshold) resize(); AfterNodeInsertion (evict); return null; // If it is a new element, return null}Copy the code

• Conclusion:

The put method does the following:

1. If the array is not initialized, expand the array to initialize it.
2. According to the insert elementkeyValue calculationhashValue,hashValues mod the array sizeThe subscript.
3. If there is no element at the subscript position, insert directly
4. If the subscript position already has elements, then there are three cases:

• 4.1 The key and hash of the element are the same as the element to be inserted (considered to be the same node), and the value of the node is directly updated.

• 4.2 If the node is inconsistent, the node is inserted into the red-black tree. Returns this object if it already exists in the red-black tree; If not, insert as a new node and return NULL;

• 4.3 If the element is inconsistent and not a red-black tree node, it can only be a linked list node. Iterate through the list, if found, prove in the list already exists, update value, at the same time the local variable refers to the node (that is, the method variable e); If the node is not found in the linked list, it is considered as a new node and is directly added to the end of the linked list. At this point, e=null. If the number of nodes >8 after the new node is added, the tree will be implemented.

5. Insert a new element,size+1. ifsize>threshold, docapacity.

The flow chart is as follows. The picture is from Meituan Technology:

But there are some problems with the picture.

When the inserted node already exists, the putVal method overrides value and does not trigger the size++ logic. Only the insertion of a new node triggers the subsequent logic.

2.2.2 Expanding resize()

Final Node<K,V>[] resize() {final Node<K,V>[] oldTab = table; Int oldCap = (oldTab == null) 0 : oldTab.length; int oldThr = threshold; // Old capacity expansion threshold, int newCap, newThr = 0; If (oldCap >0) {// If (oldCap >0) {// If (oldCap >0) {// If (oldCap >0) {// If (oldCap >0) {// If (oldCap >0) {// If (oldCap >0) {// If (oldCap >0) {// If (oldCap >0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; // Return the old hash array. Capacity expansion failed! return oldTab; } // The new capacity is twice the old capacity. Else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // If the new array is twice as long as the old one and less than 2^30 And the old array is longer than 16. // Then the new capacity threshold is twice the old one. It's essentially cap load factor. It makes no difference! newThr = oldThr << 1; // double threshold} //2. new HashMap(3) else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // Zero initial threshold using defaults (05.6 so) else {// zero initial threshold using defaults (05.6 so)  new HashMap() newCap = DEFAULT_INITIAL_CAPACITY; //16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //16*0.75=12 // newThr=12. In other words, 0.75 times of the original capacity (loading factor times), that is, fast loading is not enough, reload efficiency will decline, must be expanded. } // If the external capacity is specified by construction, the initialization logic will be followed here. Manually calculate new threashHold if (newThr == 0) {float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //4, at this point, we need to clarify two concepts cap and THR: cap: array capacity. THR: capacity expansion threshold of the total number of nodes. In the preceding initialization or normal expansion logic, the new capacity and expansion threshold are calculated based on the old capacity and expansion threshold. // Update the capacity expansion threshold. Next time the threshold is exceeded, you need to expand it again. Threshold = newThr; @ SuppressWarnings ({" rawtypes ", "unchecked"}) / / 5, NewTab 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]) ! = null) {// Empty the position corresponding to the old array. oldTab[j] = null; // This node has no successors, i.e. only one header. If (e.ext == null) // Recalculate the subscript to the element based on the original hash value. newTab[e.hash & (newCap - 1)] = e; Else if (e instanceof TreeNode) // If it is a binary tree, then split the group. // Then re-store the corresponding subscript position. Note that the number of binary trees may be less than 6 after grouping, which may trigger the binary tree to degenerate into a linked list. ((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 {// The list has multiple elements next = e.next; //e.hash & oldCap >=oldCap. //==0 indicates that the newly inserted position is the same as the previous position. In the low order, which is j. Why is it called low? J < oldCap. //else indicates that the new insert position is high, i.e. J +oldCap position. // The essence is to group the original list and insert it into the new array. If ((e.hash & oldCap) == 0) {// indicates a low value group. // Reason: Different hash values must have different mod values for array length changes. But since it's 2 to the NTH power, the remainder is also regular. 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 ! Next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }Copy the code

• conclusion

The expansion work of Resize can be divided into two parts:

1. Create a new array. Calculate the new array length and expansion threshold based on the old array length and expansion threshold.
2. Migrate old data loop old data, cut into groups, store in new arrays

The main process is as follows (see the notes for details) :

Create a new array:

• Array =null: if the null parameter constructor is called, the array length is initialized to 16, and the expansion threshold is 12; If the call has parameters, the new array length newCap is calculated according to the added CAP, and the expansion threshold is newCap*0.75.
• The array is not null: If the maximum capacity is 2^30, capacity expansion fails and the old array is returned directly. Otherwise, expand the array by twice the size. At the same time, the new capacity expansion threshold is raised according to the previous formula.
• Based on the size of the new arraynewCapCreating a new arraynewTableobject

Migrating old data:

1. Iterating through the old array, if there are only heads, then headshashValue mod the length of the new array, resulting in a new index, stored in the new array.
2. What if the head node has a successor, and the head node is a red-black tree node? The location must be a red-black tree structure. Then we cut and group the red-black tree, and we get two new red-black tree structures, the high-order tree and the low-order tree, and we insert them into the new array. This may trigger de-tree (<6 nodes, red-black tree converted to linked list)
3. What if the head node has a successor, a linked list node? It’s also going to group, get the high-order list and the low-order list, and insert it into the new array.

How to understand high and low? You’re essentially rehashing the array to mod the new length!

The process of high and low segmentation is as follows. The picture is from the reference article.

As shown above, storage structure before expansion, array length is 8.hashA value of35, 27, 19, 43It maps to the subscript theta3The location of the. When usinge.hash & oldCapAfter the operation, we can see that the blue part is divided into two groups.

After capacity expansion, the array length becomes 16. The top is called the low group, and the bottom is called the high group.

2.2.3 treeifyBin() method

When the tree is triggered: when a new element is inserted into the end of the list, the length of the list is greater than 8.

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) / / 1, if the array is empty, or the length of the array is less than 64. The minimum tree capacity was not reached. So just expand. resize(); else if ((e = tab[index = (n - 1) & hash]) ! TreeNode<K,V> hd = null, tl = null; // What is hd? What is TL? do { TreeNode<K,V> p = replacementTreeNode(e, null); //p is a TreeNode, but it is connected by a linked list. Hd is the head of the list. // The first tl must be null. So hd and TL both point to the first node. if (tl == null) hd = p; // tree header else {// p.rev = tl; tl.next = p; } //tl always points to the last node tl = p; } while ((e = e.next) ! = null); // Iterate over the original list node. // To summarize the above: change the one-way linked list with Node as a Node to the two-way linked list with TreeNode as a Node. Bidirectional linked list used to do what ？？？？ If ((TAB [index] = hd)! = null) // Actually build a red-black tree hd.treeify(TAB) from scratch; }}Copy the code

• conclusion

If the array is NULL, the expansion method is entered. If the array length is less than 64, even if the list length at a subscript is greater than 8, it will only expand, not tree.

Expansion process:

1. First, get the head node corresponding to the node insertion position and start traversing the linked list.
2. Each node(Node)Are converted to tree nodes(TreeNode).
3. Put inNodeA one-way linked list of nodes is converted toTreeNodeIs a bidirectional linked list of nodes. Store in the header. So far, we haven’t treed
4. callhd.treeify(tab)To start the transformation of a red-black tree, it’s just a fillLeft, right, parentNode.

2.2.3.1 Constructing red-black tree Treenode.treeify ()

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) {// Construct the root node of the red-black tree x.parent = null; x.red = false; root = x; } else {// The root node is not empty, prepare the node to be inserted x K K = x.key; int h = 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; // If the hash of node P is greater than the hash of node X to be inserted, dir=-1. Else if (ph < h) // If small, dir=1. Dir =1; Else if (= = null && (kc, kc = comparableClassFor (k)) = = null) | | / / by comparing compareTo method once, if dir = = 0, Dir = compareComparables(kc, k, PK) ==0) //dir==0 dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; TreeNode<K,V> p; If dir<=0, continue traversing the left subtree. If > 0, continue traversing the right subtree until the last node is found. if ((p = (dir <= 0) ? P: p light) == null) {//p is the last node to be inserted, and the parent of node X points to XP. x.parent = xp; If (dir <= 0) xp.left = x; else xp.right = x; Root = balanceInsertion(root, x); break; }}}} // Ensure that root is the root node of the tree. moveRootToFront(tab, root); }Copy the code

• conclusion

The key points to understand are two cycles:

1. Traversal of linked list dimensionsWalk through the whole according to the next successor nodeTreeNode(from the listnextCan be called a linked list).
2. Traversal of red-black tree dimensionsGet each linked list node, according to the characteristics of red-black tree (small left and large right) traversal, insertleftorrightNode.

The characteristic of a red-black tree is that it’s small on the left and big on the right. Therefore, the idea is to determine whether to insert into the left or right subtree based on the size of the hash value.

The procedure for comparing sizes based on hash values is described in the comments. At this point, a red-black tree has been built.

2.3 Get the element get() method

The get method calls the getNode method.

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // Array not null+ array length >0+hash array length mod to subscript first node not null if ((TAB = table)! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! = null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key ! = null && key.equals(k)))) // if the hash is the same and the key is the same, then it is the first node. return first; if ((e = first.next) ! = null) {// Not the first node. If (first instanceof TreeNode) //first is the root node of the red-black tree. Walk through the binary tree. // Internal traversal: Performs recursive lookup based on the size of the hash. return ((TreeNode<K,V>)first).getTreeNode(hash, key); // list structure, start traversing search, find return. do { if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) return e; } while ((e = e.next) ! = null); } } return null; }Copy the code

• The logic is simple:

1. According to thekeyTo get thehashValue, mod to get the array subscript. If no element exists at the subscript, null is returned.
2. There is an element, is it a header? Is to return.
3. It’s not a header, is it a red-black tree? Yes is to look in the red black tree (red black tree traversal ~).
4. It’s not a head node, it’s not a red-black tree node, so just go through the list, find it and return it.

2.4 Remove elements the remove() method

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) ! = null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) ! Node<K,V> Node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key ! = null &&key. equals(k))))); else if ((e = p.next) ! If (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreenode (hash, key); / / from the red-black tree node else {do {if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) {// find node = e; break; } p = e; } while ((e = e.next) ! = null); }} if (node! = null && (! matchValue || (v = node.value) == value || (value ! = null && value.equals(v)))) {// start removing logic if (node instanceof TreeNode) // start removing logic of TreeNode ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; // Delete the header from the array subscript else p.ext = node.next; // Normal node node, pointing to the next node of node. Delete node ++modCount; --size; // Update my grandparents; vivienemoval (node); return node; } } return null; }Copy the code

• conclusion

The comment is already clear ~ ~, briefly summarized as follows:

1. According to thehashThe value mod length yields the subscript
2. If it’s a head, I getnodevariable
3. If it’s not a head, is it a red-black tree? If yes, go to the red black tree and getnode
4. Linked list nodes? Then directly traverse the linked list and getnode
5. findnodeTo delete the vm.

2.5 Iterate over elements

2.5.1 Three Traversal Modes

HashMap<String, String> map = new HashMap<>(); Iterator ()// 1, from entrySet dimension map.keyset ().iterator()// 2, from key dimension map.values().iterator()// 3, from values dimensionCopy the code

Traversal of all three dimensions is accomplished through the iterator.

Ask a question: what is entrySet, keySet, values

2.5.2 map. EntrySet ()

// Return all key-value pair data. EntrySet public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; }Copy the code

Returns an abstract view of the Set of all key-value pairs in the HashMap! EntrySet does not contain duplicate data and supports whether to include, delete, and iterate.

final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator< map.entry <K,V>> Iterator() {return new EntryIterator(); } public final boolean contains(Object o) { if (! (o instanceof Map.Entry)) return false; Map.Entry<? ,? > e = (Map.Entry<? ,? >) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate ! = null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) ! = null; } return false; } public final Spliterator<Map.Entry<K,V>> spliterator() { return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0); } / /... Omit}Copy the code

2.5.3 map. KeySet ()

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}
Copy the code

Returns an abstract view of all the key sets (of type Set) in the HashMap! KeySet does not contain duplicate data, and supports whether to include, delete, and iterate.

final class KeySet extends AbstractSet<K> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<K> Iterator() {return new KeyIterator(); } public final boolean contains(Object o) { return containsKey(o); } public final Boolean remove(Object key) {return removeNode(hash(key), key, null, false, true)! = null; } public final Spliterator<K> spliterator() { return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0); } // omit... }Copy the code

2.5.4 map. The values ()

public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}
Copy the code

Returns an abstract view of the Collection type of all the values in the HashMap! Values can contain duplicate data, and support the including or not, and iteration functions.

final class Values extends AbstractCollection<V> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<V> iterator() { return new ValueIterator(); } public final boolean contains(Object o) { return containsValue(o); } public final Spliterator<V> spliterator() { return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super V> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) ! = null) { int mc = modCount; // Android-changed: Detect changes to modCount early. for (int i = 0; (i < tab.length && modCount == mc); ++i) { for (Node<K,V> e = tab[i]; e ! = null; e = e.next) action.accept(e.value); } if (modCount ! = mc) throw new ConcurrentModificationException(); }}}Copy the code

2.5.5 Iterating logic HashIterator

abstract class HashIterator { Node<K,V> next; // next entry to return Node<K,V> current; // current entry int expectedModCount; // for fast-fail int index; // current slot HashIterator() { expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; if (t ! = null && size > 0) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null); } // 1, next is the first Node in the table array with a value. } public final boolean hasNext() { return next ! = null; } final Node<K,V> nextNode() {Node<K,V>[] t; Node<K,V> e = next; if (modCount ! = expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); If ((next = (current = e).next) == null && (t = table)! = null) {// Already traversed the last node, then traversed the next position in the array. Do {} while (index < t.length && (next = t[index++]) == null); } // the next one that is not null is returned. } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount ! = expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } final class KeyIterator extends HashIterator implements Iterator<K> { public final K next() { return nextNode().key;  } } final class ValueIterator extends HashIterator implements Iterator<V> { public final V next() { return nextNode().value; } } final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); }}Copy the code

• conclusion

The succession is clear. KeyIterator, ValueIterator, and EntryIterator all inherit from HashIterator and implement the next method. They’re essentially calling the nextNode method and returning Node, key, or value.

Iteration logic:

1. In the constructor, we iterate through the array, find the first subscript in the array, and get the header.
2. whennextNodeMethod is called ifmapIs null, an exception is thrown. If it is not empty, then according tonextA node gets the next node (whether it’s a linked list or a red-black tree)nextPointer to).
3. As thenextNodeMethod is repeatedly called until the end node of the zipper isnull, indicating that the element at the current subscript position has been traversed.
4. And then I add 1 to the subscript,Retrieves the header at the next position in the array, if not empty, thenStep 3The logic of thenextNode.

3. Differences with other hash tables

And then I’ll add ~

So far, the source code of HashMap is basically learned, during the harvest is quite a lot. If there are any mistakes, please correct them and make progress together

Reference:

Understand the Java HashMap source code

HashMap (JDK1.8)

HashMap (JDK8)