HashMap的源码学习(jdk8)-蒲公英云

hashmap的源码学习了，做个笔记

hashmap中的一些属性

transient Node<K, V>[] table; // 数组,存放的为Node<K,V>
    int threshold; // 扩容的阈值,当前数组长度*扩容因子
    final float loadFactor; // 扩容因子
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的大小 16
    static final int MAXIMUM_CAPACITY = 1 << 30; // 数组的最大空间
    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认的负载因子大小
    static final int TREEIFY_THRESHOLD = 8; // 树化,链表需要达到阈值
    static final int UNTREEIFY_THRESHOLD = 6; // 退化为链表的阈值
    static final int MIN_TREEIFY_CAPACITY = 64; // 树化,数组需要达到的阈值

hashmap中的链表Node

// 由代码可知此链表为单向的链表
    static class Node<K, V> implements Map.Entry<K, V> {
        final int hash; // 根据hash(key)计算出来的hash值,
        final K key;
        V value;
        Node<K, V> next; // 指向下一个节点
        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public final K getKey() {
            return key;
        }
        public final V getValue() {
            return value;
        }
        public final String toString() {
            return key + "=" + value;
        }
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        public final boolean equals(Object o) {
            if (o == this) {
                return true;
            }
            if (o instanceof Map.Entry) {
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue())) {
                    return true;
                }
            }
            return false;
        }
    }

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;
        // eg1: table=null
        /** 如果是空的table，那么默认初始化一个长度为16的Node数组*/
        if ((tab = table) == null || (n = tab.length) == 0) {
            // eg1: resize返回(Node<K, V>[]) new Node[16]，所以：tab=(Node<K, V>[]) new Node[16]， n=16
            n = (tab = resize()).length;
        }
        /** 如果计算后的下标i，在tab数组中没有数据，那么则新增Node节点*/
        if ((p = tab[i = (n - 1) & hash]) == null) {
            // eg1: tab[0] = newNode(0, 0, "a0", null)
            // eg2: tab[1] = newNode(1, 1, "a1", null)
            tab[i] = newNode(hash, key, value, null);
        } else {
     /** 如果计算后的下标i，在tab数组中已存在数据，则执行以下逻辑 */
            Node<K, V> e;
            K k;
            // 判断key是否相等
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
     /** 如果与已存在的Node是相同的key值*/
                e = p;
            }
            // 判断是树还是链表
            else if (p instanceof TreeNode) {
     /** 如果与已存在的Node是相同的key值，并且是树节点*/
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            } else {
     /** 如果与已存在的Node是相同的key值，并且是普通节点，则循环遍历链式Node，并对比hash和key，如果都不相同，则将新的Node拼装到链表的末尾。如果相同，则进行更新。*/
                for (int binCount = 0; ; ++binCount) {
                    /** 获得p节点的后置节点，赋值给e。直到遍历到横向链表的最后一个节点，即：该节点的next后置指针为null */
                    if ((e = p.next) == null) {
                        // eg3: p.next = newNode(16, 16, "a16", null);
                        // eg4-loop2: p.next == newNode(32, 32, "a32", null);
                        // eg6: p.next == newNode(128, 128, "a128", null);
                        p.next = newNode(hash, key, value, null);
                        // eg3: binCount == 0
                        // eg4-loop2: binCount == 1
                        /** 是否要树化 ,binCount从0开始，横向链表中第2个node对应binCount=0，如果Node链表大于8个Node，那么试图变为红黑树 */
                        if (binCount >= TREEIFY_THRESHOLD - 1) {
                            // eg6: tab={newNode(0, 0, "a0", ［指向后面1个链表中的7个node］), newNode(1, 1, "a1", null)}, hash=128
                            treeifyBin(tab, hash); // 树化
                        }
                        break;
                    }
                    // eg4-loop1: e.hash==16 hash==32 所以返回false
                    /** 更新操作,针对链表中的每个节点，都来判断一下，是否待插入的key与已存在的链表节点相同，如果相同，则跳出循环，并在后续的操作中，将该节点内容更新为最新的插入值 */
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        break;
                    }
                    p = e;
                }
            }
            // 更新的操作
            /** 如果存在相同的key值*/
            if (e != null) {
                V oldValue = e.value;
                // onlyIfAbsent=false,HashMap初始化的参数,判断是否是不能修改,默认是false
                if (!onlyIfAbsent || oldValue == null) {
                    /** 则将新的value值进行更新*/
                    e.value = value;
                }
                afterNodeAccess(e); /** doing nothing */
                //  返回oldValue
                return oldValue;
            }
        }
        ++modCount; // 好像是并发用的
        // eg4: size=8, threshold=12
        if (++size > threshold) {
            resize();
        }
        afterNodeInsertion(evict); /** doing nothing */
        return null;
    }

get()方法

public V get(Object key) {
        Node<K, V> e;
        // getNode(hash(key),key)得到对应的Node节点,在e.value获得值
        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;
        Node<K, V> e;
        int n;
        K k;
        /**利用hash&(n-1)计算出数组下标 ,table存在元素 并且根据hash寻址后的下标位置也有元素存在 */
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
            /** hash值相同，并且key值也相同。真幸运，第一个元素就是待寻找的元素！！！ */
            if (first.hash == hash &&  ((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;
    }

总结一下,put()方法直接调用putVal(hash(key,key,value,false.true))方法，
hash（key）这个方法是计算一个hash值出来，主要的是它的函数扰动，也就是 (h = key.hashCode()) ^ (h >>> 16)，用key的hashcode（）和自己的高16位做异或运算，这样的好处是，使用这个值分布的更加分散，减少哈希冲突的出现。
在putVal方法中：
判断tab是不是null，长度是否为0，如果是那就扩容成初始大小16.
计算出这个key应该放入的数组下标，计算方法是：用hash（key）与数组大小减一做与运算，这样可以保证计算出来的值在数组大小之内（之所以不采用模运算，是因为‘与运算‘的效率是要高于模运算的）。
下标计算出来之后，判断下标处，是否已经有值，如果没有，便直接生成一个Node对象，放在这个位置。
这个位置有值，需要比较一下，key是否是相等的，如果是则做更新操作。
如果key的值不相等，那这可能就是那就要开始遍历,一种是遍历链表,一种是遍历红黑树。
遍历链表的话，就是比较key是否和链表上的key相等，如果没有相等的key，则尾插法，插入到链表中，如果有相等的key，将会和上面的走一样的更新操作。
遍历红黑树的话，就比较麻烦了，从根节点开始遍历，查找是否有和key相等的存在，存在便是更新操作，不存在则是将数据添加到红黑树的节点上，再做树的自旋操作，让树保持红黑树的特性。最好还要保证root节点放在数组中。
get()方法,主要是先通过调用hash()方法计算出hash值,确定key在数组中的下标,之后进行key的比较,如果下标位置的key相同,则直接返回这个Node节点,得到value值.
若是不相等,下一步则是遍历链表或者遍历红黑树（first instanceof TreeNode判断是红黑树还是链表）,找到对应的Node节点,并返回。

本人对HashMap的源码理解有限，如有错误还望大家不吝赐教。