>>分享Java编程技术,对《Java面向对象编程》等书籍提供技术支持 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
发表一个新主题 开启一个新投票 回复文章 您是本文章第 20595 个阅读者 刷新本主题
 * 贴子主题:  害怕面试被问HashMap? 回复文章 点赞(0)  收藏  
作者:Jacky    发表时间:2020-03-23 19:17:10     消息  查看  搜索  好友  邮件  复制  引用

              

搞定HashMap

作为一个Java从业者,面试的时候肯定会被问到过HashMap,因为对于HashMap来说,可以说是Java<mark>集合中的精髓</mark>了,如果你觉得自己对它掌握的还不够好,我想今天这篇文章会非常适合你,至少,看了今天这篇文章,以后不怕面试被问HashMap了

     其实在我学习HashMap的过程中,我个人觉得HashMap还是挺复杂的,如果真的想把它搞得明明白白的,没有足够的内力怕是一时半会儿做不到,不过我们总归是在不断的学习,因此真的不必强迫自己把现在遇到的一些知识点全部搞懂。

     但是,对于HashMap来说,你所掌握的应该足够可以让你应对面试,所以今天咱们的侧重点就是学会那些经常被问到的知识点。

     我猜,你肯定看过不少分析HashMap的文章了,那么你掌握多少了呢?从一个问题开始吧

新的节点在插入链表的时候,是怎么插入的?

怎么样,想要回答这个问题,还是需要你对HashMap有个比较深入的了解的,如果仅仅知道什么key和value的话,那么回答这个问题就比较难了。

     这个问题大家可以先想想,后面我会给出解答,下面我们一步步的来看HashMap中几个你必须知道的知识点。

Map是个啥?

HashMap隶属于Java中集合这一块,我们知道集合这块有list,set和map,这里的HashMap就是Map的实现类,那么在Map这个大家族中还有哪些重要角色呢?

     点击在新窗口中浏览原图
CTRL+鼠标滚轮放大或缩小

上图展示了Map的家族,都是狠角色啊,我们对这些其实都要了解并掌握,这里简单的介绍下这几个狠角色:
  TreeMap从名字上就能看出来是与树有关,它是基于树的实现,而HashMap,HashTable和ConcurrentHashMap都是基于hash表的实现,另外这里的HashTable和HashMap在代码实现上,基本上是一样的,还记得之前在讲解ArrayList的时候提到过和Vector的区别嘛?这里他们是很相似的,一般都不怎么用HashTable,会用ConcurrentHashMap来代替,这个也需要好好研究,它比HashTable性能更好,它的锁粒度更小。
由于这不是本文的重点,只做简单说明,后续会发文单独介绍。

     简单来说,Map就是一个映射关系的数据集合,就是我们常见的k-v的形式,一个key对应一个value,大致有这样的图示

点击在新窗口中浏览原图
CTRL+鼠标滚轮放大或缩小

这只是简单的概念,放到具体的实例当中,比如在HashMap中就会衍生出很多其他的问题,那么HashMap又是个啥?

HashMap是个啥

上面简单提到过,HashMap是基于Hash表的实现,因此,了解了什么是Hash表,那对学习HashMap是相当重要。

     之前特意写了一篇介绍哈希表的,不了解的赶紧去看看:来吧!一文彻底搞定哈希表!

     建议了解了哈希表之后再学习HashMap,这样很多难懂的也就不那么难理解了。

     接着,HashMap是基于hash表的实现,而说到底,它也是用来存储数据供我们使用的,那么底层是用什么来存储数据的呢?可能有人猜到了,还是数组,为啥还是数组?想想之前的ArrayList,怎么,对ArrayList也不了解。

     没事,刚好我也写了一篇:掌握这些,ArrayList就不用担心了!

     所以,对于HashMap来说,底层也是基于数组实现,只不过这个数组可能和你印象中的数组有些许不同,我们平常整个数组出来,里面会放一些数据,比如基础数据类型或者引用数据类型,数组中的每个元素我们没啥特殊的叫法。

     但是在HashMap中人家就有了新名字,我发现这个知识点其实很多人都不太清楚:
  在HashMap中的底层数组中,每个元素在jdk1.7及之前叫做Entry,而在jdk1.8之后人家又改名叫做Node。
这里可能还是会有人好奇这Entry和Node长啥样,这个看看源码就比较清楚了,后面我们会说。

     到了这里你因该就能简单的理解啥是HashMap了,如果你看过什么是哈希表了,你就会清楚,在HashMap中同样会出现哈希表所描述的那些问题,比如:
  1. 如何确定添加的元素在底层数组的哪个位置?
  2. 怎么扩容?
  3. 出现冲突了怎么处理?
  4. 。。。
没事,这些问题我们后续都会谈到。

HashMap初始化大小是多少

先来看HashMap的基础用法:    

HashMap map  =  new  HashMap ( ) ;

  就这样,我们创建好了一个HashMap,接下来我们看看new之后发生了什么,看看这个无参构造函数吧    

    public  HashMap ( )  {
         this .loadFactor  = DEFAULT_LOAD_FACTOR ;  // all other fields defaulted
     }

解释下新面孔:
  1. loadFactor : 负载因子,之前聊哈希表的时候说过这个概念
  2. DEFAULT_LOAD_FACTOR : 默认负载因子,看源码知道是0.75
很简单,当你新建一个HashMap的时候,人家就是简单的去初始化一个负载因子,不过我们这里想知道的是底层数组默认是多少嘞,显然我们没有得到我们的答案,我们继续看源码。

     在此之前,想一下之前ArrayList的初始化大小,是不是在add的时候才创建默认数组,这里会不会也一样,那我们看看HashMap的添加元素的方法,这里是put    

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

这里大眼一看,有两个方法;
  1. putVal  重点哦
  2. hash
这里需要再明确下,这是我们往HashMap中添加第一个元素的时候,也就是第一次调用这个put方法,可以猜想,现在数据已经过来了,底层是不是要做存储操作,那肯定要弄个数组出来啊,好,离我们想要的结果越来越近了。

     先看这个hash方法:    

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

记得之前聊哈希表的时候说过,哈希表的数据存储有个很明显的特点,就是根据你的key使用哈希算法计算得出一个下标值,对吧,不懂得赶紧看:来吧!一文彻底搞定哈希表!

     而这里的hash就是根据key得到一个hash值,并没有得到下标值哦。

     重点要看这个putVal方法,可以看看源码:    

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

咋样,是不是感觉代码一下变多了,我们这里逐步的有重点的来看,先看这个:    

  if  ( (tab  = table )  == null  ||  (n  = tab .length )  ==  0 )
    n  =  (tab  =  resize ( ) ) .length ;?

这个table是啥?    

  transient Node  <K ,V > [ ] table ;

看到了,这就是HashMap底层的那个数组,之前说了jdk1.8中数组中的每个元素叫做Node,所以这就是个Node数组。

     那么上面那段代码啥意思嘞?其实就是我们第一次往HashMap中添加数据的时候,这个Node数组肯定是null,还没创建嘞,所以这里会去执行resize这个方法。
  resize方法的主要作用就是初始化和增加表的大小,说白了就是第一次给你初始化一个Node数组,其他需要扩容的时候给你扩容
看看源码:    

  final Node  <K ,V > [ ]  resize ( )  {
        Node  <K ,V > [ ] oldTab  = table ;
         int oldCap  =  (oldTab  == null )  ?  0  : oldTab .length ;
         int oldThr  = threshold ;
         int newCap , newThr  =  0 ;
         if  (oldCap  >  0 )  {
             if  (oldCap  >= MAXIMUM_CAPACITY )  {
                threshold  = Integer .MAX_VALUE ;
                 return oldTab ;
             }
             else  if  ( (newCap  = oldCap  <<  1 )  < MAXIMUM_CAPACITY  &&
                     oldCap  >= DEFAULT_INITIAL_CAPACITY )
                newThr  = oldThr  <<  1 ;  // double threshold
         }
         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 ) ;
         }
         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  = 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 )
                        newTab [e .hash  &  (newCap  -  1 ) ]  = e ;
                     else  if  (e  instanceof  TreeNode )
                         ( (TreeNode  <K ,V > )e ) . split ( this , newTab , j , oldCap ) ;
                     else  {  // preserve order
                        Node  <K ,V > loHead  = null , loTail  = null ;
                        Node  <K ,V > hiHead  = null , hiTail  = null ;
                        Node  <K ,V > next ;
                         do  {
                            next  = e .next ;
                             if  ( (e .hash  & oldCap )  ==  0 )  {
                                 if  (loTail  == null )
                                    loHead  = e ;
                                 else
                                    loTail .next  = e ;
                                loTail  = e ;
                             }
                             else  {
                                 if  (hiTail  == null )
                                    hiHead  = e ;
                                 else
                                    hiTail .next  = e ;
                                hiTail  = e ;
                             }
                         }  while  ( (e  = next )  != null ) ;
                         if  (loTail  != null )  {
                            loTail .next  = null ;
                            newTab [j ]  = loHead ;
                         }
                         if  (hiTail  != null )  {
                            hiTail .next  = null ;
                            newTab [j  + oldCap ]  = hiHead ;
                         }
                     }
                 }
             }
         }
         return newTab ;
     }

感觉代码也是比较多的啊,同样,我们关注重点代码:    

newCap  = DEFAULT_INITIAL_CAPACITY ;  

有这么一个赋值操作,DEFAULT_INITIAL_CAPACITY字面意思理解就是初始化容量啊,是多少呢?    

  static  final  int DEFAULT_INITIAL_CAPACITY  =  1  <<  4 ;  // aka 16

这里是个移位运算,就是16,现在已经确定具体的默认容量是16了,那具体在哪创建默认的Node数组呢?继续往下看源码,有这么一句    

Node  <K ,V > [ ] newTab  =  (Node  <K ,V > [ ] ) new  Node [newCap ] ;

ok,到这里我们发现,第一次使用HashMap添加数据的时候底层会创建一个长度为16的默认Node数组。

     那么新的问题来了?

为啥初始化大小是16

这个问题想必你在HashMap相关分析文章中也看到过,那么该怎么回答呢?

     想搞明白为啥是16不是其他的,那首先要知道为啥HashMap的容量要是2的整数次幂?

为什么容量要是 2 的整数次幂?

先看这个16是怎么来的:    

  static  final  int DEFAULT_INITIAL_CAPACITY  =  1  <<  4 ;  // aka 16

这里使用了位运算,为啥不直接16嘞?这里主要是位运算的性能好,为啥位运算性能就好,那是因为位运算人家直接操作内存,不需要进行进制转换,要知道计算机可是以二进制的形式做数据存储啊,知道了吧,那16嘞?为啥是16不是其他的?想要知道为啥是16,我们得从HashMap的数据存放特性来说。

     对于HashMap而言,存放的是键值对,所以做数据添加操作的时候会根据你传入的key值做hash运算,从而得到一个下标值,也就是以这个下标值来确定你的这个value值应该存放在底层Node数组的哪个位置。

     那么这里一定会出现的问题就是,不同的key会被计算得出同一个位置,那么这样就冲突啦,位置已经被占了,那么怎么办嘞?

     首先就是冲突了,我们要想办法看看后来的数据应该放在哪里,就是给它找个新位置,这是常规方法,除此之外,我们是不是也可以聚焦到hash算法这块,就是尽量减少冲突,让得到的下标值能够均匀分布。

     好了,以上巴拉巴拉说一些理念,下面我们看看源码中是怎么计算下标值得:    

i  =  (n  -  1 )  & hash

  这是在源码中第629行有这么一段,它就是计算我们上面说的下标值的,这里的n就是数组长度,默认的就是16,这个hash就是这里得到的值:    

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

继续看它:    

i  =  (n  -  1 )  & hash

这里是做位与运算,接着我们还需要先搞明白一个问题

为什么要进行取模运算以及位运算

要知道,我们最终是根据key通过哈希算法得到下标值,这个是怎么得到的呢?通常做法就是拿到key的hashcode然后与数组的容量做取模运算,为啥要做取模运算呢?

     比如这里默认是一个长度为16的Node数组,我们现在要根据传进来的key计算一个下标值出来然后把value放入到正确的位置,想一下,我们用key的hashcode与数组长度做取模运算,得到的下标值是不是一定在数组的长度范围之内,也就是得到的下标值不会出现越界的情况。

     要知道取模是怎么回事啊!明白了这点,我们再来看:    

i  =  (n  -  1 )  & hash

这里就是计算下标的,为啥不是取模运算而是位与运算呢?使用位与运算的一方面原因就是它的性能比较好,另外一点就是这里有这么一个等式:    

  (n  -  1 )  & hash   =  n  % hash

  因此,总结起来就是使用位与运算可以实现和取模运算相同的效果,而且位与运算性能更高!

     接着,我们再看一个问题

为什么要减一做位运算

理解了这个问题,我们就快接近为什么容量是2的整数次幂的答案了,根据上面说的,这里的n-1是为了实现与取模运算相同的效果,除此之外还有很重要的原因在里面。

     在此之前,我们需要看看什么是位与运算,因为我怕这块知识大家之前不注意忘掉了,而它对理解我们现在所讲的问题很重要,看例子:

     比如拿5和3做位与运算,也就是5 & 3 = 1(操作的是二进制),怎么来的呢?

     5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101

     3转换为二进制:0000 0000 0000 0000 0000 0000 0000 0011

     1转换为二进制:0000 0000 0000 0000 0000 0000 0000 0001

     所以啊,位与运算的操作就是:第一个操作数的的第n位于第二个操作数的第n位如果都是1,那么结果的第n位也为1,否则为0

     看懂了吧,不懂得话可以去补补这块的知识,后续我也会单独发文详细说说这块。

     我们继续回到之前的问题,为什么做减一操作以及容量为啥是2的整数次幂,为啥嘞?
  告诉你个秘密,2的整数次幂减一得到的数非常特殊,有啥特殊嘞,就是2的整数次幂得到的结果的二进制,如果某位上是1的话,那么2的整数次幂减一的结果的二进制,之前为1的后面全是1
啥意思嘞,可能有点绕,我们先看2的整数次幂啊,有2,4,8,16,32等等,我们来看,首先是16的二进制是: 10000,接着16减一得15,15的二进制是: 1111,再形象一点就是:

     16转换为二进制:0000 0000 0000 0000 0000 0000 0001 0000

     15转换为二进制:0000 0000 0000 0000 0000 0000 0000 1111

     再对照我给你说的秘密,看看懂了不,可以再来个例子:

     32转换为二进制:0000 0000 0000 0000 0000 0000 0010 0000

     31转换为二进制:0000 0000 0000 0000 0000 0000 0001 1111

     这会总该懂了吧,然后我们再看计算下标的公式:    

  (n  -  1 )  & hash   =  n  % hash

  n是容量,它是2的整数次幂,然后与得到的hash值做位于运算,因为n是2的整数次幂,减一之后的二进制最后几位都是1,再根据位与运算的特性,与hash位与之后,得到的结果是不是可能是0也可能是1,,也就是说最终的结果取决于hash的值,如此一来,只要输入的hashcode值本身是均匀分布的,那么hash算法得到的结果就是均匀的。

     啥意思?这样得到的下标值就是均匀分布的啊,那冲突的几率就减少啦。

     而如果容量不是2的整数次幂的话,就没有上述说的那个特性,这样冲突的概率就会增大。

     所以,明白了为啥容量是2的整数次幂了吧。

     那为啥是16嘞?难道不是2的整数次幂都行嘛?理论上是都行,但是如果是2,4或者8会不会有点小,添加不了多少数据就会扩容,也就是会频繁扩容,这样岂不是影响性能,那为啥不是32或者更大,那不就浪费空间了嘛,所以啊,16就作为一个非常合适的经验值保留了下来!

出现哈希冲突怎么解决

我们上面也提到了,在添加数据的时候尽管为实现下标值的均匀分布做了很多努力,但是势必还是会存在冲突的情况,那么该怎么解决冲突呢?

     这就牵涉到哈希冲突的解决办法了,详情建议阅读:来吧!一文彻底搞定哈希表!

     了解了哈希冲突的解决办法之后我们还要关注一个问题,那就是新的节点在插入到链表的时候,是怎么插入的?

回答开篇的问题

现在你应该知道,当出现hash冲突,可以使用链表来解决,那么这里就有问题,新来的Node是应该放在之前Node的前面还是后面呢?

     Java8之前是头插法,啥意思嘞,就是放在之前Node的前面,为啥要这样,这是之前开发者觉得后面插入的数据会先用到,因为要使用这些Node是要遍历这个链表,在前面的遍历的会更快。

为什么使用尾插法?

但是在Java8及之后都使用尾插法了,就是放到后面,为啥这样?

     这里主要是一个链表成环的问题,啥意思嘞,想一下,使用头插法是不是会改变链表的顺序,你后来的就应该在后面嘛,如果扩容的话,由于原本链表顺序有所改变,扩容之后重新hash,可能导致的情况就是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。

     这样的话在多线程操作下就会出现死循环,而使用尾插法,在相同的前提下就不会出现这样的问题,因为扩容前后链表顺序是不变的,他们之间的引用关系也是不变的。

关于扩容

下面我们继续说HashMap的扩容,经过上面的分析,我们知道第一次使用HashMap是创建一个默认长度为16的底层Node数组,如果满了怎么办,那就需要进行扩容了,也就是之前谈及的resize方法,这个方法主要就是初始化和增加表的大小,关于扩容要知道这两个概念:
  1. Capacity:HashMap当前长度。
  2. LoadFactor:负载因子,默认值0.75f。
这里怎么扩容的呢?首先是达到一个条件之后会发生扩容,什么条件呢?就是这个负载因子,比如HashMap的容量是100,负载因子是0.75,乘以100就是75,所以当你增加第76个的时候就需要扩容了,那扩容又是怎么样步骤呢?

     首先是创建一个新的数组,容量是原来的二倍,为啥是2倍,想一想为啥容量是2的整数次幂,这里扩容为原来的2倍不正好符号这个规则嘛。

     然后会经过重新hash,把原来的数据放到新的数组上,至于为啥要重新hash,那必须啊,你容量变了,相应的hash算法规则也就变了,得到的结果自然不一样了。

关于链表转红黑树

在Java8之前是没有红黑树的实现的,在jdk1.8中加入了红黑树,就是当链表长度为8时会将链表转换为红黑树,为6时又会转换成链表,这样时提高了性能,也可以防止哈希碰撞攻击,这些知识在来吧!一文彻底搞定哈希表!都有详细讲解,强烈推荐阅读

HashMap增加新元素的主要步骤

下面我们分析一下HashMap增加新元素的时候都会做哪些步骤:
  1. 首先肯定时根据key值,通过哈希算法得到value应该放在底层数组中的下标位置
  2. 根据这个下标定位到底层数组中的元素,当然,这里可能时链表,也可能时树,知道为啥吧,给你个提醒,链表转红黑树
  3. 拿到当前位置上的key值,与要放入的key比较,是否==或者equals,如果成立的话就替换value值,并且需要返回原来的值
  4. 当然,如果是树的话就要循环树中的节点,继续==和equals的判断,成立替换,否则添加到树里
  5. 链表的话就是循环遍历了,同样的判断,成立替换,否则就添加到链表的尾部
所以啊,这里面的重点就是判断放入HashMap中的元素要不要替换当前节点的元素,那怎么判断呢?总结起来只要满足以下两点即可替换:
1、hash值相等。

2、==或equals的结果为true。
----------------------------
原文链接:https://blog.csdn.net/sinat_33921105/article/details/103847137

程序猿的技术大观园:www.javathinker.net



[这个贴子最后由 flybird 在 2020-03-28 09:51:10 重新编辑]
  Java面向对象编程-->异常处理
  JavaWeb开发-->Web运作原理(Ⅲ)
  JSP与Hibernate开发-->第一个helloapp应用
  Java网络编程-->非阻塞通信
  精通Spring-->Vue简介
  Vue3开发-->Vue简介
  10道Java编程基础练习题
   JAVA进阶之IO模型深入解析
  好消息:《精通JPA与Hibernate:Java对象持久化技术详解》出...
  JAVA锁相关知识总结
  Java Optional 解决空指针异常总结
  Redis安装、Redis基本数据类型、Jedis、Redis集群搭建
  使用 RocketMQ 事务消息,实现分布事务
  java中的Static、final、Static final各种用法
  超详细的Java运算符修炼手册(优秀程序员不得不知道的运算技...
  邀请您一起来祝福和祈祷,祈愿疫情早日消除,平安吉祥
  深入分析synchronized实现原理
  Java读取大文件的高效率实现_java大文件
  Java 入门实用代码: 数组差集
  史上最全正则表达式合集(马上收藏)
  关于Java中try finally return语句的执行顺序浅析
  更多...
 IPIP: 已设置保密
树形列表:   
[url=https://www.1686990.c... 发货33 2022-02-15 12:21:23
1页 1条记录 当前第1
发表一个新主题 开启一个新投票 回复文章


中文版权所有: JavaThinker技术网站 Copyright 2016-2026 沪ICP备16029593号-2
荟萃Java程序员智慧的结晶,分享交流Java前沿技术。  联系我们
如有技术文章涉及侵权,请与本站管理员联系。