从源码中分析HashMap的get跟put方法

Question

话不多说直接上代码

put

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


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)
            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;
    }

#get

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) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

问题所在

对于2个方法的逻辑看的不是很懂虽然大概知道，先通过hash去找，如果找不到一样的hash就新建Entry，如果找到一样的判断key是否也相等，如果相等则覆盖value，如果不想等说明是key不相同但是hash相同，那么生成Entry赋值给父的next。本人的逻辑理解是这样的，但是对源码还是看不懂。
1. ,put方法中

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;
                }
            }

这段逻辑不是很懂。

2.get方法中

if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);

这一段不是很理解，求解释。越详细越好。在写笔记看到这里突然卡住了，求支招。哈哈哈。

Answer 1

1. if ((tab = table) == null || (n = tab.length) == 0)
   1. n = (tab = resize()).length;
   2. if ((p = tab[i = (n - 1) & hash]) == null)
   3. tab[i] = newNode(hash, key, value, null);
   4. else {
   5. Node e; K k;
   6. if (p.hash == hash &&
   7. ((k = p.key) == key || (key != null && key.equals(k))))
   8. e = p;
   9. else if (p instanceof TreeNode)
   10. e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
   11. else {
   12. for (int binCount = 0; ; ++binCount) {
   13. if ((e = p.next) == null) {
   14. p.next = newNode(hash, key, value, null);
   15. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
   16. treeifyBin(tab, hash);
   17. break;
   18. }
   19. if (e.hash == hash &&
   20. ((k = e.key) == key || (key != null && key.equals(k))))
   21. break;
   22. p = e;
   23. }
   24. } 解读这一段源码：
2. java1.8中，map的结构是由Node[] + 链表组成的，和之前的主要区别是，链表部分，当超过8个元素会转成TreeNode对象，由TreeBin封装，也就是链表转换为树形结构便于存储和查找。不是线程安全类，但是如果多线程操作会报出ConCurrentxxxException。

下面按行数来说：
1. 如果当前Node[] 为null 或者 Node数组元素个数为0 执行下面一行代码（省略大括号）
2. resize() 方法返回一个扩容后的Node[],扩容的机制为所需容量的两倍，是原有的1.5倍，这个计算是由负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; 来决定的（具体的可以看一下resize()方法，如果有困难我们再讨论一次）。 Node数组元素个数n 赋值为扩容后的长度。
4. 「 (n - 1) & hash] 」定位数组下标位置的经典算法，你可以自己写一个main方法来做几个实验。n=16的话，计算结果肯定在0～15之间。p为计算后取到的一个Node节点 判断是否为null (if else 省略大括号)
5. 如果上述判断为true，那么当前节点赋值为一个新建节点 newNode(x,x,x,x); 这个不用说吧。也是一个经典数据结构。
6. 如果4 中判断结果为false，证明当前下标为i的位置存在节点，那么进行下列操作。
7、8、9. 如果当前node节点的hash 和 节点中key属性值 双等或值等（也就是进行新旧值替换），则将当前节点赋值给e。
10、11. 如果当前节点为TreeNode节点，则将当前操作元素添加到TreeNode[]中（图中，单独的hash，key，value都是当前操作元素的值）。
12. 如果上述都不成立，直接执行下列代码（到这步的意思是，不会是覆盖操作，当前节点也不是treeNode，只能是将当前节点拼接在列表末端）。
13-23. 这是一个看似无限循环的算法，这有几个退出点，按顺序来，第一个break，代表找到了列表末端，把当前元素添加到末端即可。第二个break，是找到新旧值覆盖的元素，进行替换。

14行为常规列表遍历。
15行为如果找到最后一个元素了，直接新建元素，将最后一个元素与新元素逻辑关联。
16行 判断当前个数，是否大于或者等于7，如果是，则将列表转化为TreeBin包装类，其实列表转树的界限是8，但是数组下标是从0开始，所以是TREEIFY_THRESHOLD - 1。
17行就是转化方法了。

用有道笔记纯手打！