Put and GET methods for HashMap 1.8 source analysis

hashcode & equals

Hashcode and equals are important in the hash structure, with the former used for quick positioning and the latter for comparing replacements

The standard writing of Hashcode

    override fun hashCode(a): Int {
    // The benefits of using 31: the VM automatically converts it into bit operations (CPU supported operations), which is faster
        var result = sourceKey.hashCode()
        result += 31 * result + signature.hashCode()
        result += 31 * result + width
        result += 31* result + height appliedTransformation? .let { result +=31 * result + it.hashCode()
        }
        result += 31 * result + decodedResourceClass.hashCode()
        result += 31 * result + options.hashCode()
        return result
    }
Copy the code

Equals

override fun equals(o: Any?).: Boolean {
        if (o is ResourceCacheKey) {
            return o.let {
            // Kotlin == = Java equals
                return sourceKey == it.sourceKey &&
                        signature == it.signature &&
                        width == it.width &&
                        height == it.height &&
                        appliedTransformation == it.appliedTransformation &&
                        decodedResourceClass == it.decodedResourceClass &&
                        options == it.options
            }
        }
        return false
    }
Copy the code

Analysis of PUT method

A flowchart

1. Use hashcode to calculate the location in the hash table
2. If no node exists in this location, create a node to store the value
3. There are nodes at this location, and conflicts are handled through the equals method

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

//onlyIfAbsent =false
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 table is empty, create the table using the resize method
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            
            // Obtain index in the table by (n-1) &hash
        if ((p = tab[i = (n - 1) & hash]) == null)
          // If the current location has no value, create a new node to store the value
            tab[i] = newNode(hash, key, value, null);
        else {
          // If there is a value in the current position, conflicts are handled through equals
            Node<K,V> e; K k;
            if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
                // Hash is calculated from hashcode, so hashcode is equal and equals is equal
                // Then point e to p for later replacement of value
                e = p;
            else if (p instanceof TreeNode)
                // If hashcode is equal,equals is unequal
                // Store in the red-black tree
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // If hashcode is equal,equals is unequal
                // Iterate through the list
                for (int binCount = 0; ; ++binCount) {
                    // Iterate to the end of the list
                    if ((e = p.next) == null) {
                        // Create a Node at the end of the list to store the Node
                        p.next = newNode(hash, key, value, null);
                        //TREEIFY_THRESHOLD defaults to 8;
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // If there are more than 8 nodes, tree the nodes
                            treeifyBin(tab, hash);
                        break;
                    }
                    // if equals equals, break and replace with new value
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                        break; p = e; }}// Replace the new value
            if(e ! =null) { // existing mapping for key
                V oldValue = e.value;
                if(! onlyIfAbsent || oldValue ==null)
                //onlyIfAbsent =false, replace value with new value
                    e.value = value;
                afterNodeAccess(e);
                // Return oldValue
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
        // If the size is larger than the threshold, expand the capacity
            resize();
        afterNodeInsertion(evict);
        return null;
    }





Copy the code

Analysis of GET method

A flowchart

1. Calculate the position index in the table by hashcode
2. Iterates over a single linked list or a red-black tree, returning value if equals equals equals

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]) ! =null) {
           
           Hash = (n-1) &hash = (n-1) &hash = (n-1)
            if(first.hash == hash && ((k = first.key) == key || (key ! =null && key.equals(k))))
                // If first equals equals, first is returned
                return first;
          
          // Handle conflict situations
          if((e = first.next) ! =null) {
                // Iterates through the red and black tree to find equals elements and returns
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
               // Iterates through the list to find equals elements and returns them
               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

conclusion

• Put: Locate the conflict using Hashcode, and then handle the conflict through equals. If eqauls are equal, replace the old value with the new value, and if not, store the conflict with a linked list or red-black tree
• Get: Locate by hashcode and find the equals value