java面试常问系列之HashMap详细源码分析。

àì夳堔傛蜴生んèń 2023-02-20 03:23 68阅读 0赞

### 文章目录 ###

*   *  一、HashMap初体验
     *  二、put方法源码分析
     *  三、resize方法源码分析
     *  四、get方法源码分析
     *  总结

## 一、HashMap初体验 ##

hashmap一直都是面试的高频问题。这次让我们一起彻底干掉它，以后再也不怕面试官问这个问题了。

首先我们先对这个方法的文档阅读一下，下面做个简单大概的翻译，先提前了解一下hashmap。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70]

那么，我们再来看一下hashmap中的一些成员变量

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70 1]  
熟悉了这些变量之后，我们先大概了解一下在JDK8中，hashmap的结构是什么样子的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70 2]

在hashmap中，元素最小单位是entry，里面存放的是一个key-value键值对，还有一种叫法是bucket（桶）。

在扣源码的时候，我们先补点位运算知识：

<table> 
 <thead> 
  <tr> 
   <th>符号</th> 
   <th>描述</th> 
   <th>运算规则</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>&amp;</td> 
   <td>与</td> 
   <td>两个位都为1时，结果才为1</td> 
  </tr> 
  <tr> 
   <td>|</td> 
   <td>或</td> 
   <td>两个位都为0时，结果才为0</td> 
  </tr> 
  <tr> 
   <td>^</td> 
   <td>异或</td> 
   <td>两个位相同为0，相异为1</td> 
  </tr> 
  <tr> 
   <td>~</td> 
   <td>取反</td> 
   <td>0变1，1变0</td> 
  </tr> 
  <tr> 
   <td>&lt;&lt;</td> 
   <td>左移</td> 
   <td>各二进位全部左移若干位，高位丢弃，低位补0</td> 
  </tr> 
  <tr> 
   <td>&gt;&gt;</td> 
   <td>右移</td> 
   <td>各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）</td> 
  </tr> 
 </tbody> 
</table>

那么，我们从头开始，先上一段代码。

public static void main(String[] args) {
        
            //实例化一个无参HashMap对象
        	Map map = new HashMap();
        	//put一个值
            map.put("1","2");
        }

首先，先new一个HashMap对象，不传入任何参数，使用默认参数。

//无参构造只是设置了一个默认加载因子为0.75.并没有初始化容量，懒加载机制
    public HashMap() {
        
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

## 二、put方法源码分析 ##

//1、该方法是有返回值的。返回啥呢？
    //2、调用putVal方法
    public V put(K key, V value) {
        
        return putVal(hash(key), key, value, false, true);
    }
    
    //onlyIfAbsent和evict两个参数暂时忽略掉
    //我们分析一下这个putVal方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        
        //这个Node其实就是我们的entry，只是表示不一样。
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //这个if条件其实就是用于初始化的。当数组tab为空或者长度为0时
        if ((tab = table) == null || (n = tab.length) == 0)
            //调用一下resize方法。在JDK8中，初始化容量和扩容都用resize方法进行.后面详解
            n = (tab = resize()).length;
        //如果当前数组为空，则直接put进去。（n-1）& hash涉及位运算，作用就是计算出tab数组下标。n-1是为了避免
        //刚好n是2的幂次方。出现数组下标越界的情况
        //举例：hash:0101 1010  n-1(15):0000 1111  进行&位运算，0000 1010(10)
        //即i=10，此时，数组为空
        if ((p = tab[i = (n - 1) & hash]) == null)
            //将k-v："1"-"2"放到tab数组下标为10的位置。newNode其实就是一个entry，不展开讲
            tab[i] = newNode(hash, key, value, null);
        //这个地方是什么情况呢？其实就是当hash冲突时，即数组tab上已经存在k-v时的情况
        else {
        
            Node<K,V> e; K k;
            //先判断hash冲突时，数组中Node是否是key相等，将e赋值为p，即为目标值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //如果是key相等，将新建k-v对象e赋值为p(当前数组中的k-v对象)
                e = p;
            //判断是否是红黑树中节点
            else if (p instanceof TreeNode)
                //是的话，存放到红黑树中，能力有限，红黑树就不展开讲。
                //用红黑树是介于平衡二叉树和单链表结构综合考量，读写效率介于两者之间
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        
                //循环链表中的Node对象
                for (int binCount = 0; ; ++binCount) {
        
                    //如果尾结点为null,则将对象放置在尾部
                    //在JDK7中，是采用头插法，多线程出现循环链表，JDK8中使用尾插法，避免了该情况 
                    if ((e = p.next) == null) {
        
                        //循环链表
                        //刚好循环到尾部时。put这个新元素
                        p.next = newNode(hash, key, value, null);
                        //当链表大小超过8-1=7时，链表转换成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //这个其实就是判断是否要覆盖链表中有key相等的value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //p为当前对象e，循环下去
                    p = e;
                }
            }
            //如果e不为null，则表示存在key相同，使用传入的value覆盖当前value
            if (e != null) {
         // existing mapping for key
                //原值赋值给oldVlaue
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                //并返回这个oldValue值
                return oldValue;
            }
        }
        ++modCount;
        //如果当前元素个数大于16*0.75=12.触发扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        //没有重复key则返回null值
        return null;
    }

上面是HashMap的put方法，我们可以根据下面的流程图进行一个简单的理解。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70 3]

在putVal方法中，我们可以看到，当map初始化或者Node个数超过阈值，默认也就是12时，会触发扩容机制。其实还有一种情况会触发扩容，后再说。

## 三、resize方法源码分析 ##

final Node<K,V>[] resize() {
        
        Node<K,V>[] oldTab = table;
        //初始化时，oldCap为0，扩容时则为原数组长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //将参数threshold阈值设置为当前map的阈值
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
        
            //如果达到最大值，就不扩容了
            if (oldCap >= MAXIMUM_CAPACITY) {
        
                //阈值设为int的最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //扩容为原来的2倍，并保证要小于最大容量，且原来容量大于默认初始容量
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //阈值也同样翻倍
                newThr = oldThr << 1; // double threshold
        }
        //这个地方注意，是给有参HashMap的初始化，利用阈值做参数，具体如果操作我们后面
        //结合有参构造和tableSizeFor方法讲一下。
        else if (oldThr > 0) // initial capacity was placed in threshold
            //可能有人会有疑问，为什么是将阈值当做容量大小？先记下，后面详细讲
            newCap = oldThr;
        //无参构造了，使用默认容量和阈值
        else {
                       // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        
        //给阈值赋值，针对有参构造。即新阈值为0时，尚未进行赋值
        if (newThr == 0) {
        
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({
        "rawtypes","unchecked"})
        //创建一个新的数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //新数组赋值给成员变量table
        table = newTab;
        //开始数组的转移，前提是旧数组不为空
        if (oldTab != null) {
        
            for (int j = 0; j < oldCap; ++j) {
        
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
        
                    //清空当前数组
                    oldTab[j] = null;
                    //如果当前节点的下一个节点为空，即该节点为尾部
                    if (e.next == null)
                        //将该节点放入到新数组，并重新计算下标。其实下标是有规律的
                        //前一个例子：hash:0101 1010  n-1(扩容后31):0001 1111  进行&位运算，0001 1010(26)
                        //转移到新数组后要么是原来的位置(10)，要么是原位置下标+扩容的大小(10+16).
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果是红黑树节点
                    else if (e instanceof TreeNode)
                        //调用红黑树的方法
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {
         // preserve order
                        //链表拆分，这段很精彩同学们，注意听
                        //定义了两个链表，lo链表和hi链表。其中loHead,loTail，hiHead,hiTail可以分别看做头结点和尾结点
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        //循环体
                        do {
        
                            next = e.next;
                            //hash冲突并不是hash值一模一样，所以运算出结果会有两个，要么等于0，要么不等于0；
                            //我们将运算结果为0的看做是lo链表，就好理解了。可以去翻一下后面那张图，比较形象
                            if ((e.hash & oldCap) == 0) {
        
                                //如果lo链表尾结点是空值，代表lo链表还没有元素存在
                                if (loTail == null)
                                    //将头结点指向e元素
                                    loHead = e;
                                else
                                    //有头之后就将loTail的下一个后移
                                    loTail.next = e;
                                //同时移动loTail指针
                                loTail = e;
                            }
                            else {
        
                                //hi链表也一样
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //将链表迁移到新数组原下标位置
                        if (loTail != null) {
        
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //将链表迁移到新数组原下标+oldCap处
                        if (hiTail != null) {
        
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

hash 冲突并不代表hash值是一模一样的，只能表示hash值的低位是相同的，比如说：

//hashA:1010 1111    hashB:0011 1111   hashC:1001 1111  当数组大小都为16时
    //三者对应数组下标为hashA:0000 1111(15)
    //但是e.hash&oldCap分别为：0000 0000;0001 0000;0001 0000

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70 4]  
以上，就完成了一个HashMap的初始化以及扩容过程。

那么，我们之前提到，出了初始化和size大于阈值时会触发resize扩容，还有一个地方会触发扩容，我们看代码：

final void treeifyBin(Node<K,V>[] tab, int hash) {
        
        int n, index; Node<K,V> e;
        //当前数组为空，或者数组的大小小于最小树容量
        //也就是说当数组比较小时，不会出现转化为红黑树，会进行扩容
        //尽可能将元素存放在数组中，数组log（1）的效率还是要高一些
        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);
        }
    }

## 四、get方法源码分析 ##

//其实，弄清楚hashmap的底层结构和put方法，这个就比较简单了
    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;
    }

get方法其实不难理解。就是一个查找加比较的一个过程。

后面一些方法这里也不再详解了，有兴趣的小伙伴自己可以去源码看看。话说写这个JDK的老哥是真的大佬，让人膜拜了。

## 总结 ##

1、JDK8采用的是数组+链表+红黑树的结构

2、JDK8采用尾插法，有效避免了多线程情况下JDK7出现的循环链表的情况

3、JDK8简化hash算法。

4、扩容机制有区别。JDK7会rehash，JDK8不会，只是根据数组大小重新计算位置。

ps:以上内容难免有不正确的地方，希望您能够及时指出，谢谢！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200623070912493.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020062307090899.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200623070905460.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200623070911237.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200623070910660.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTA4NTEwOQ==,size_16,color_FFFFFF,t_70