HashMap中put方法分析

put方法

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

hash方法

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

将key的哈希值异或其哈希值右移动十六位，即当传入key值是小于2^16次方时，得到的哈希值都为本身。

hashCode方法放回的是一个int类型值，也就是一个32位的一个整形值，将hash值右移动16位相当于得出的即是一个高位与地位进行异或后的结果。

这么做的目的是为了减少hash碰撞的次数。因后续就是通过hash值得出索引位置确定元素所存储的位置。若不使用上述扰动函数进行再哈希，若是只取得的低四位，造成的hash冲突较多，同时若散列本身做的不好的话，低位重复的概率极大。因此进行了高十六位与低十六位的异或运算。此前在jdk1.7之前是采用了四次扰动运算，一次只右移四位，移动四次，而效果和进行一次右移十六位相差不大，一次采用了整体右移十六位，进行一次异或运算即可。

那么，为何hashmap中的容量一定要是二的次幂呢？首先我们得知道capacity做了什么，由上述可知我们会使用capacity的大小减一（这样保证了所有位的值都是1，如十六减一，二进制值为1111）与hash只进行&运算，得出的结果即直接是hash值的后几位，同时hash值本身已经作为了散列均匀分布，每个位置出现的频率都已经尽可能相等。若capacity值非二的次幂，得出的坐标位置即会造成某些位置分布不均，从而导致该位置hash冲突尤为的严重。

put方法中调用的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//是否仅当无对应key才设值？true，不替换原值
      //false，会替换原值
     * @param evict if false, the table is in creation mode.     //用于区别通过put是新增数据还                     //是进行初始化操作
     * @return previous value, or null if none//return 返回原先key对应值，若无则返回null
     */
    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)
            //为空则，调用resize（）方法进行初始化
            n = (tab = resize()).length;
        //判断预计插入位置是否有元素
        if ((p = tab[i = (n - 1) & hash]) == null)
            //无，则将准备新增的元素插入
            tab[i] = newNode(hash, key, value, null);
        else {
            //存在元素，则应该同链表的形式（若较多则转换红黑树）在相同位置插入元素
            Node<K,V> e; K k;
            //若当前元素hash值与待插入元素hash值相同 且 （二者key地址相等或者所实现的equals方法判定为相等）
            //找到需替换节点，后续根据onlyIfAbsent值，选择是否需要替换新值
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //若p  此时已经是红黑树了， 按照红黑树方式插入
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //开始遍历链表
                for (int binCount = 0; ; ++binCount) {
                    //若p的下一节点为null，即遍历到结尾处了（即1.8之后实现的尾插法）
                    if ((e = p.next) == null) {
                        //将新增的值放到p的下一个节点
                        p.next = newNode(hash, key, value, null);
                        //TREEIFY_THRESHOLD为8 ， 表明当链表长度达到8则将链表转为红黑树存储
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //转为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
            //若当前元素hash值与待插入元素hash值相同 且 （二者key地址相等或者所实现的equals方法判定为相等）
            //找到需替换节点，后续根据onlyIfAbsent值，选择是否需要替换新值
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //继续向后遍历
                    p = e;
                }
            }
            //修改数据，
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //当onlyIfAbsent为false（即允许覆盖旧值）或者原值为null将值进行替换
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //一个空实现的函数，允许修改后进行其他操作
                afterNodeAccess(e);
                return oldValue;
            }
        }
     
        ++modCount;
        //判断是否需要扩容
        if (++size > threshold)
            //扩容
            resize();
        //一个空实现的函数，当为LinkedHashMap进行put操作则进入到该重写的方法中去
        afterNodeInsertion(evict);
        return null;
    }

程序流程图

为什么取下标使用tab[i = (n - 1) & hash]方式来获得呢?

** **n-1 即为数组最大下标值，最大小标志与key的哈希值做与运算 ， 由与运算特性可知 ，得出的结果肯定是小于两者中的最小值的。而哈希值一般是比较大的一个值，因此就相当于是取余操作。

• 那么为什么不直接用取余操作呢？
  • & 运算效率远远高于 % 运算。

关于afterNodeAccess（）、afterNodeRemoval（）、afterNodeInsertion这三个空实现的方法在put方法中起到的作用？？？

** **LinkedHashMap继承了HashMap，该三个方法是为LinkedHashMap服务的，其本身为空实现，若是LinkedHashMap进行put操作时即会进入到其重写的方法中去。分别表示用于回调移除最初是插入的值等等。

put方法在JDK1.8和1.7中区别