解读HashMap中put方法的源码

解析hashMap的put方法是如何存储一个键值。

一、 put方法

代码1-1 V put(K key, V value)方法

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

调用put方法存储键值，实际上是调用了HashMap的putVal方法，putVal方法的调用过程中 执行了hash(key) 获取了一个int类型的值

代码1-2 int hash(Object key)方法

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

首先该hash方法声明了一个 int类型的值 h ，int类型占4个字节 共32位，然后调用key的hashCode方法获取一个key的散列码 并将该散列码赋值给h，最后执行h^(h>>>16)并返回结果。

解析h^(h>>>16)，首先将h无符号右移16位，右移的结果是 32位h的低16位变为高16位的值，而高16位则全部变为0 例如：

0010 1100 1010 0000 0001 0100 1010 0001  将h无符号右移16位--》

0000 0000 0000 0000 0010 1100 1010 0000  位移后的结果

之后将h 与 位移后的结果做一个异或运算，整个操作也可以解读为 h的高16位保持不变，将高16位和低16位异或的结果赋值给 低16位 ，最终返回一个更加散列的散列码(也就是将key.hashCode()再一次散列)。

二、 putVal方法

我编写了一段代码 通过debug来观察putVal方法的执行过程，如下：

代码2-1 自定义代码(debug的断点位置已标明)

    public static void main(String[] args) {
        HashMap<strKey, Object> stringObjectHashMap = new HashMap<>();
        strKey strKey = new strKey("a", "b");
        strKey strKey2 = new strKey("b", "a");
        //strKey和strKey2的哈希值相同
        System.out.println(strKey.hashCode());
        System.out.println(strKey2.hashCode());
 断点1   stringObjectHashMap.put(strKey, "hello");
 断点2   stringObjectHashMap.put(strKey2, "hi");
    }

    //创建全参构造方法，重写equals和hashcode方法
    @AllArgsConstructor
    public static class strKey {
        private String a;
        private String b;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            strKey strKey = (strKey) o;
            return Objects.equals(a, strKey.a) && Objects.equals(b, strKey.b);
        }

        @Override
        public int hashCode() {
            if (a == null || b == null)
                return 0;
            int result = 1;
            result = 31 * result + a.hashCode() + b.hashCode();
            return result;
        }
    }

putVal方法的代码如下：

代码2-2 V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

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是一个 Node<K,V> 类型的数组
        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;
            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 {
                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;
                }
            }
            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;
    }

debug 的执行过程如下：

在构造出HashMap类型的对象后，执行断点1处的put方法第一次存储一个键值。

HashMap中存在一个成员变量table，变量table是 Node<K,V> 类型的数组 初始为null，putVal方法最先执行如下代码 第一次调用resize方法做容量的初始化。

代码2-3 putVal方法的第一步

//table最开始为null
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

代码2-4  resize()方法第一次被调用时 主要执行的代码

//声明newCap、newThr ，newCap 为新的容量，newThr为最新的扩容阈值
int newCap, newThr = 0

/**
DEFAULT_INITIAL_CAPACITY的值为 1 << 4 ,即值为16 也就是默认的初始化容量是16，DEFAULT_LOAD_FACTOR的值为0.75f , 也就是 默认的加载因子为0.75
**/
newCap = DEFAULT_INITIAL_CAPACITY 
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)

//threshold 为扩容阈值 ，是HashMap的成员变量
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//将新创建的Node<K,V> 数组赋值给成员变量table

return newTab; //返回newTab

 在代码2-3执行结束后，HashMap第一次初始化时的容量 16 已经赋值给 putVal 方法的局部变量 n

，之后执行putVal 方法的第二步：

代码2-5 putVal方法的第二步

第二步的执行过程中 将hash(也就是在代码1-2中将key的hashCode再次散列的结果) 与 （n-1）也就是15的 二进制 进行一个 与运算，运算的结果是数组tab的下标，因为HashMap的结构是 由 数组+链表+红黑树组成 其实就是 Node<K,V>[] table，数组的每个位置 最初都是一个可以延长的链表，所以最开始应该确定 put存放的元素应该存储在 数组table的哪个位置。

(n - 1) & hash 的最终结果 <= 15 ，有兴趣的读者可以去了解一下 & 运算。

/**
在代码2-3中其实就已经将 table 赋值给了 tab，由于是第一次执行，数组的所有位置都为null，所以将 hash、key、value 构造成一个Node<K,V>对象 并赋值给tab[i]。
**/
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

 代码2-6 putVal方法第三步

++modCount; //modCount会加一
//判断数组容量是否超过阈值，如果超过阈值则调用resize()来扩容，现在是第一次添加 不会执行扩容操作。
if (++size > threshold) 
    resize();

至此断点1就执行完毕，下面开始执行断点2

由于断点1的执行过程中已经进行了初始化 那么断点2的执行直接跳过初始化

 代码2-7 putVal方法第一步

首先获取key所在的数组下标。

由于重写了hashCode方法，致使strKey的hashCode和 strKey2的hashCode相同，但是他们equals的结果却不相同，这里使strKey和strKey2的hashCode相同的目的是为了制造散列冲突（散列冲突指的是 ”桶“ 已经被填充的现象，也就是元素对应的node数组下标的位置已经有值了），即由于hashCode相同导致不同的元素存放在node数组的同一位置，要注意hashCode即便是相同的也会出现散列冲突，这里只是为了模拟散列冲突所以设置了相同的hashCode

//发生了散列冲突，if括号内的结果为false，并且将发生冲突的位置的node赋值给 Node<K,V>类型的 p

if ((p = tab[i = (n - 1) & hash]) == null)

由于第一步的结果为false 所以执行如下代码

代码2-8 putVal方法的第二步 

在第一步中已经说明发生散列冲突时，hashCode可能不相同，也就是代码中的 局部变量 hash 可能不相同（前面已经说明过，hash是hashCode再次散列的结果，所以hashCode相同 hash一定相同）

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
    Node<K,V> e; K k;
    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 {
        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;
        }
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}

那么我开始解读代码2-8中 else代码块各个步骤的含义：

首先看一下node的结构

每一个node 是由put方法传入的key、value、key所对应的hash以及下一个node组成，其实就是链表的结构，也就是所说的 HashMap是由数组+链表组成，数组中的每一个元素就是 一个node，也就是链表的第一个节点。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
        ...............
}

1、此时p是tab[i]处的元素，也是链表的第一个node

首先判断p的key的hash和要存入的key的hash是否相同，如果hash不相同 也就是 hashCode不相同，那么两个key一定不是同一个对象 结果返回false，但也有可能出现不同对象的hash相同的情况，所以会出现后续判断 (k = p.key) == key || (key != null && key.equals(k))，如果p的key的内存地址和传入的key的内存地址相同则两个key一定相等，或者equals的结果相同，则两个key也可以判定为相同，判断的最终结果为true 则执行 e=p，如下代码块：

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
else{ ...................

/**

if为true 则表示p的key和传入的key相同，那么以下操作的意思就是，将put方法的value值覆盖p的value值，也就是所说的 HashMap的put方法中如果key相同，则旧的value将会被新的value替换

**/

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

2、 由于strKey和strKey2进行equals的结果为false，那么就执行到下图：

此处会判断p是不是一个树节点，当链表长度大于8 数组长度大于64的时候，链表会转变为红黑树

 由于此时还未转变为红黑树则执行到下一步骤

3、该步骤如图所示：

 要注意的是 for循环中可能执行多次 e=p.next ，p=e的操作 所以binCount可能是链表中的任意一个位置，图中的for循环先执行如下代码：

if ((e = p.next) == null) {//if判断p的下一个node是否为空
/**
如果p的下一个node为空，则将key、value、以及key对应的hash构造出一个新的node 来作为链表的最后一个node
**/
    p.next = newNode(hash, key, value, null); 
    // TREEIFY_THRESHOLD的值为8，如果链表长度已经达到8 则会调用treeifyBin方法尝试将链表转变为树
    if (binCount >= TREEIFY_THRESHOLD - 1) 
        treeifyBin(tab, hash);
    break;
}

treeifyBin方法的部分代码如下：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY的值为64，如果数组长度小于64则会调用resize方法进行扩容，否则就会执行将链表转为红黑树的操作
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else{
   ..............
}

for循环也可能执行后面的代码 来跳出循环，如下所示：

这个操作的意思是，可能该链表的某个node的key和传入的key相同，则将新的value覆盖该node的value值

else {
    for (int binCount = 0; ; ++binCount) {
        ........
        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;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

至此结束调试，如有疑问欢迎留言一起探讨。