How to implement HashMap

HashMap is a common container in Java and Android, which uses an array and a linked list structure to store data. The following is a detailed analysis of the implementation of HashMap.

1 Why do we use linked lists

The hash function is used to calculate the index of the array corresponding to the key, and the value is stored directly in the array. Why do you use linked lists?

The key of the problem lies in the hash function, because so far there has not been a function (including MD5, SHA and other algorithms) that has different hash values for different keys. If the array index of a and B obtained by the hash function is 1, and a has been saved into the array with the index 1, How do I store b? Delete the value corresponding to A and replace it with the value corresponding to B? Such an approach is clearly undesirable. So was introduced to the HashMap linked list, or a, b two key, a storage, we first determine the location of the array subscript 1 if there is a data, if not directly inserted into the array, then a corresponding value inserted into the array, we to store b, we found the location of the subscript 1 has saved data, We use a.next to point to B to form a linked list. And so on.

2 Code implementation

1 put method

Return putVal(hash(key), key, value, false, true); public V put(K key, V value) {// Hash () 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; If ((TAB = table) = = null | | (n = TAB. Length) = = 0) / / expansion data move n = (TAB = the resize ()). The length; If (p = TAB [I = (n-1) & hash]) == null) TAB [I] = newNode(hash, key, value, null); else { Node<K,V> e; K k; / / key is equal to the if (p.h ash = = hash && ((k = p.k ey) = = 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 { for (int binCount = 0; ; ++binCount) {if ((e = p.ext) == null) {if (e = p.ext) == null) {if (e = p.ext) == null) {if (e = p.ext) == null) {if (e = p.ext) == null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } / / key if equal (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) break; p = e; }} // reassign if (e! = null) { // existing mapping for key V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }Copy the code

2 the get method

public V get(Object key) { Node<K,V> e; 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; if ((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! If (first.hash == hash && // always check first node ((k =)) {if (first.hash == hash && // always check first node ((k =) first.key) == key || (key ! = null && key.equals(k)))) return first; if ((e = first.next) ! = null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); Do find key {/ / to iterate over the same objects if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) return e; } while ((e = e.next) ! = null); } } return null; }Copy the code

3 summary

By adding array and linked list, HashMap realizes O(1) fast insertion, query and other operations. In ordinary use, we can further speed up its performance by specifying array size. The article just wrote the general idea, have wrong return please forgive!