HashMap源码解析

更新时间:2019-12-19 16:16:56 点击次数:248次
一、HashMap主要参数及其含义
这部分内容网上博客有很多,但在此处还是列举一下:

    /**
        HashMap的初始容量,这边我们看到默认是16,可根据自身需求进行指定,如果是一个合适的值可避 
     免扩容操作带来的性能损耗
       **/
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 
    /**
     * HashMap的最大容量 我们看到相当于Integer整形的最大值
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
 
    /**
     * 加载因子,我个人更喜欢称之为负载因子 Hash桶内元素个数达到容量*负载因子时进行扩容操作
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
    /**
     *HashMap的树化阈值,jdk1.8后引入红黑树来优化之前由于链表过长带来性能损耗的问题
     */
    static final int TREEIFY_THRESHOLD = 8;
 
    /**
     * HashMap的解树化阈值,jdk1.8通过链表高低位巧妙的解决1.7死锁问题,同时如果长度小于此值则进 
     行解树化
     */
    static final int UNTREEIFY_THRESHOLD = 6;
 
    /**
     * HashMap的最小树化容量  其实并不一定是链表长度达到8进行扩容,容量如果没有64 会优先进行扩容
        这一点下面会说明
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
二、put方法
我们可以看到,put方法其实调用了putVal方法

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
 
来看一下putVal方法,这里面比较关键,我尽可能一行一行解释。首先,上面的注解写明了方法的参数,第一个很好理解,对key做hash之后的hash值,第二个和第三个参数分别是key和value,第四个参数如果为true,则不覆盖已有的key。这边类似于redis的setNx命令,如果你用过redis,那么肯定很好理解;最后一个参数我们这边不做讲解,是提供给子类LinkedHashMap使用的。

/**
     * 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
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */ 
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是否为空,长度是否为0,如果是的话,对hash表进行扩容操作
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //这里的n是扩容后的hash表长度,(n-1)& hash相当于对hash进行取余操作,只不过位运算
        //速度上更快,这里不得不佩服大师的智慧
        if ((p = tab[i = (n - 1) & hash]) == null)
            //如果数组该位置为空的话,就新建一个node节点直接放在那个位置
            tab[i] = newNode(hash, key, value, null);
        else {
            //以下走的都是数组对应位置不为空的逻辑
            Node<K,V> e; K k;
            //这里的p是上面if获取的链表对应位置的节点,如果和我们新加入的key相等的话,则将该节点
            //保存到 上面声明的e节点
            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理解一下,既不是key相等,也不是树节点,那是什么呢?聪明的你应该能想到
            //该位置已有节点,key不相同,且可能为长度大于1的链表
            else {
                //这边是个死循环,其实目的是为了获得链表长度binCount
                for (int binCount = 0; ; ++binCount) {
                    //如果该位置下一个节点为空,则走此判断
                    if ((e = p.next) == null) {
                        //将当前插入的节点挂在后面
                        p.next = newNode(hash, key, value, null);
                        //如果binCount大于树化的阈值,则走树化逻辑
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        //跳出循环
                        break;
                    }
                    //如果便利链表到某个位置,该节点的key和我们插入的key相等,则跳出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //把e赋值给p方便便利链表,这边很好理解
                    p = e;
                }
            }
            //这里对应上面的判断链表中已经找到相同key的情况,否则e==null,会插入新节点到链表尾
            //覆盖该节点的value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //这里就是上面提到的第三个参数,可以回去看看,当他为否才会覆盖
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //完事后hash表的长度如果大于扩容阈值,则进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
接着来看一下hashmap是如何扩容的,上resize()方法:老规矩,看一下上面的注释,我英文水平低下,理解不对请大佬在下面评论区指正:首先初始化或者给数组容量加倍,如果为空,根据我们设定的初始容量值分配空间;下面半句是关于扩容后元素移动的,我翻译不来,读者自行翻译

 /**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        //保存原始hash表
        Node<K,V>[] oldTab = table;
        //保存原始表的原始容量,如果原始表为空则为0 否则是原始表的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //保存老扩容阈值
        int oldThr = threshold;
        int newCap, newThr = 0;
        //如果原始容量大于0,走这个逻辑
        if (oldCap > 0) {
            //如果原始容量大于2的30次方
            if (oldCap >= MAXIMUM_CAPACITY) {
                //把阈值设置为整形最大值,意思是不再进行扩容
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //否则如果原始容量扩大两倍后仍然小于2的30次方并且原始容量大于等于16,新容量等于老容            
             //量乘以2
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //新的阈值也变为原来的两倍,这个很好理解
                newThr = oldThr << 1; // double threshold
        }
        //如果老的扩容阈值阈值大于0,这个判断一般是hashmap初始化的时候第一次扩容会走
        else if (oldThr > 0) // initial capacity was placed in threshold
            //把新的容量设置为原始的阈值
            newCap = oldThr;
        //这里看注释很好理解,如果我们hashmap初始化把容量设置为0走这个判断
        else {
               // zero initial threshold signifies using defaults
            //把新的容量设置为16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //新的阈值设置为16*0.75,等于多少自己算
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //猜一下这个判断什么时候会走,很明显上面如果走else分支 newThr绝对不可能等于0,所以只可能
        //走上面两个判断分支,很显然第一个if判断分支内部两个小分支第一个直接返回第二个给newThr赋            
        //了值,所以只能是走中间分支,也就是第一次初始化的时候表容量为0,但是扩容阈值不是的情况
        if (newThr == 0) {
            //计算新的扩容阈值,如果新的容量小于2的30次方并且新的容量乘以负载因子之后小于2的30次        
            //方,则新的阈值等于新的容量乘以负载因子,否则设置为整数的最大值
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //将当前扩容阈值设置为新的阈值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        //用新的表容量初始化一个新的table
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //把当前的hash表设置为新的table
        table = newTab;
        //下面是扩容之后的rehash操作
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //遍历数组节点,如果当前节点不等于null,则进行下面的迁移操作
                if ((e = oldTab[j]) != null) {
                    //先把节点保存到e,然后把数组该位置设置为null
                    oldTab[j] = null;
                    //如果e的下一个节点等于null,也就是当前位置只有一个节点,链表长度为1,
                    //那么进行和新的表容量进行取余运算后放到newTable的对应节点
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果此节点是树节点,对它进行树的拆分,我对红黑树了解不多,这里不做过多介绍
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //这里走的是节点是个长度大于1的链表,但是又没到树化阈值的情况
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        //循环
                        do {
                            //获取e的下一个节点,保存到next
                            next = e.next;
                            //如果e的hash值与上oldCap等于0,这里解释一下,oldCap是一个2的
                            //幂次方,转化成二进制只有1位等于1,其他位都是0,所以结果要么为
                            //0,要么为oldCap
                            if ((e.hash & oldCap) == 0) {
                                //等于0,代表低位,如果低位链表尾节点等于null,将e赋值给低位
                                //链表头节点
                                if (loTail == null)
                                    loHead = e;
                                //否则将e赋值给尾节点的下一个节点,再将e节点设置为尾节点,这                
                                //是一个标准的尾插法
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //如果结果不等于0
                            else {
                                //逻辑和上面一样,只是放到高位链表
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //如果低位尾节点不等于null,将其next设置为null,并且将低位头节点
                        //放置到newTable的j位置,也就是说位置是一样的
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //如果是高位,则放置到j加上oldCap偏移量的位置,比如如果原来容量是16,        
                        //新容量是32,原来j=8,在第九个位置,现在放到8+16=24,的位置
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
关于扩容上面已经写的较为详细了,读者如果有不明白的地方欢迎评论或者私信我。

我接下来要讲的是一个比较容易忽略的点,还记得上面分析putVal的树化操作吗?来分析一下代码:注意上面的注释,把所有链表节点都换成树节点除非表太小,将使用扩容代替。所以网上很多博客都是装逼的,根本没提到这个点,所以当你你出去面试,面试官问:树化的阈值是8,那链表长度到8一定会树化吗?你看别人的博客,一定会说:对啊,达到8就会树化,我看过put的代码。然而很遗憾,你要回去等消息了,因为你根本没点进来这个方法,关于树化的条件,我在下面代码中已经注释,请自行阅读。

 /**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //首先第一件事,什么也不干,先判断tab是否等于null以及tab的长度是否小于64,如果是的话
        //会扩容而不是树化
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
/**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
三、get方法
可以看到他真实调用的是getNode方法

 public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
 关于第一个判断,一个是 == ,一个是equals,我们都知道一个是比较地址,一个是内容。所以我们重写equals的时候建议重写hashcode,毕竟如果作为key的话就会有点尴尬,不重写显然是获取不到的,因为他首先比较的就是hashcode。

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //如果hash表不等于null且长度大于0,且和key的hash取余之后的节点位置不为null,走里面逻        
          //辑,否则直接返回null,说明map里没有
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //上面已经把hash取余后的位置的节点赋值给first节点,首先检查第一个节点的hash值是不是
            //等于传进来的key的hash值并且,first节点的key等于传进来的key或者传进来的key不等于     
             //null并且内容相等,则直接返回第一个节点
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //走到这里说明不是第一个节点,判断他的下一个节点是否为null
            if ((e = first.next) != null) {
             // 如果是树化的节点,则走红黑树的遍历逻辑   
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    //否则一直循环到链表尾,如果找到相同的key则返回该节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        //这里有两种情况,第一种是表为空或者表长度为0,直接返回null,另一种是链表遍历完没有找到
        //对应的key,则返回null
        return null;
    }

本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责,本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台,网站上部分文章为转载,并不用于任何商业目的,我们已经尽可能的对作者和来源进行了通告,但是能力有限或疏忽,造成漏登,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

回到顶部
嘿,我来帮您!