博客

1.首先调用hash(key)计算hash值

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

2.判断 传入的key是否等于null(在HashMap中是 允许存入null的)

对key值调用原生hashCode方法后进行 右移和异或运算得到 存放的数组的下标

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

3.HashMap中存放是数组来存放Key 和 Value的 具体的 步骤在下面的代码中注释了出来

    /**
     * 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, the table is in creation mode.
     * @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;
       //判断数组是否为空，如果为空进行初始化，初始化的是数组容量必须为2的幂次方(下面有解释)
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
         //判断当前所需要存放的数组上是否已经有值    
        if ((p = tab[i = (n - 1) & hash]) == null)
        //如果没有值 创建一个链表newNode 放在这个数组中
            tab[i] = newNode(hash, key, value, null);
        else {
        //反之已经有值了 
            Node<K,V> e; K k;
            //先判断当前hash值是否相等 在判断 key不等于null 并且key是否相等 则直接赋值        
            if (p.hash == hash &&
                ((k = p.key) == 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 {
            //TREEIFY_THRESHOLD  = 8  
            //否则 去循环这个 newNode链表 并赋值  当链表长度达到8的时候去调用treeifyBin 
            //方法转成红黑树(这里注意 长度到达8以后也不一定会转成红黑树)       
            //在treeifyBin 方法中 有这样一段代码
            // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
           // resize(); 
           // MIN_TREEIFY_CAPACITY =64
           //如果当前存放Entry数组的长度小于64的时候 则 直接进行扩容操作 并没有去转成红黑树
                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))))
                        break;
                    p = e;
                }
            }
            //put方法其实是有返回值的 如果已经存在了key 他会返回一个已经覆盖了的值
            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;
    }

容量大小为什么要取2的指数倍？

1.因为2的指数倍的二进制都是只有一个1，而2的指数倍-1的二进制就都是左全0右全1。那么跟（2^n – 1）做按位与运算的话，得到的值就一定在【0,（2^n – 1）】区间内，这样的数就刚合适可以用来作为哈希表的容量大小，因为往哈希表里插入数据，就是要对其容量大小取余，从而得到下标。所以用2^n做为容量大小的话，就可以用按位与操作替代取余操作，提升计算效率。

2.便于动态扩容后的重新计算哈希位置时能均匀分布元素：因为动态扩容仍然是按照2的指数倍，所以按位与操作的值的变化就是二进制高位+1，比如16扩容到32，二进制变化就是从0000 1111（即15）到0001 1111（即31），那么这种变化就会使得需要扩容的元素的哈希值重新按位与操作之后所得的下标值要么不变，要么+16（即挪动扩容后容量的一半的位置），这样就能使得原本在同一个链表上的元素均匀（相隔扩容后的容量的一半）分布到新的哈希表中。