hashMap之putVal()

一、hash值：

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

1.h>>>16：
无符号右移，取出h的高16位，由于在put方法中，哈希值要与（length-1）做运算，length一般情况小于2的16次方，所以始终是hashCode的低16位参与运算（hashCode一般是32位）。如果高16位也参与运算，得到的下标能更加的随机，所以hash函数中直接让hash值与其本身的高16位做运算。这样会让得到的下标更加散列。
2.为什么是异或运算：
位运算中，与运算运算结果偏向0，或运算运算结果偏向1，而异或运算的运算结果更加平均，更为散列，因此采用异或运算。
二、hash(key):

  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
         n = (tab = resize()).length;
         i = (n - 1) & hash;

经过运算后，得到的值作为key的索引，放置元素。table为数组长度。
三、默认初始长度为16，原因：
1.长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。
2.当HashMap长度不为2的幂，比如为10的时候，有些index结果的出现几率会更大，而有些index结果永远不会出现（比如0111）。这样，显然不符合Hash算法均匀分布的原则。
3.是8或者4的话很容易导致map扩容影响性能，如果分配的太大的话又会浪费资源，所以就使用16作为初始大小。
4.总结：减少hash碰撞；提高map查询效率；分配过小防止频繁扩容；分配过大浪费资源
四、链表长度为8转化成红黑树，长度为6退化成链表：
1.为什么是8？
put进去的key进行计算hashCode时只要选择计算hash值的算法足够好(hash碰撞率极低)，从而遵循泊松分布，使得桶中挂载的bin的数量等于8的概率非常小，从而转换为红黑树的概率也小，反之则概率大。
2.为什么退化的时候是6？
为了防止增删元素时底层在链表和红黑树之间频繁的切换，所以隔了一个数。
五、整体流程：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //table空时，取初始长度
        if ((tab = table) == null || (n = tab.length) == 0)
            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;
            //如果该节点与原本存在的结点的哈希值相同且key值也相同，不添加
            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);
            //其他可能：p所在的链表尚未转换成红黑树
            else {
                for (int binCount = 0; ; ++binCount) {//binCount 记录次数
                    if ((e = p.next) == null) {//如果p的下一个结点为空,将新结点放入p的下一个结点
                        p.next = newNode(hash, key, value, null);
                        //如果超出阈值（8次），转换成红黑树
                        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;
                }
            }
            //如果p的下一个结点不为空，将旧值替换为新值（onlyIfAbsent默认为false，否则不能替换）
            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;
    }

文字版：先计算索引，如果索引所在的位置为空，直接添加；如果所在的位置有值：判断值是否新结点（key）相等，如果相等，不操作；如果不相等，判断下一个元素是否相等、判断是否超过链表最大长度。

hashMap之putVal()

全站热榜