您现在的位置是:首页 > 文章 > HashMap源码初体验 网站文章

HashMap源码初体验

孙玉超 2019-12-07 11:56:36 0 评论 324 浏览 0 收藏 201 赞


   HashMap结构参考图 (红黑树叶子节点省去NULL)                                                                                                                                                           


     一. HashMap要点导航


      (1)HashMap 各个成员变量含义。  
      (2)HashMap put()方法具体代码详细分析。
      (3)HashMap hash值计算方法
      (4)HashMap 扩容机制。
      (5)HashMap 底层数据结构,1.8做了怎样的优化。


    二. 代码分析

    

        从我们最常用的写法开始。无参构造初始化HashMap。

   

        好的,第一个成员变量出现。loadFactor 默认加载因子。常量值为 0.75 。这个字段代表的意思是,当前HashMap的元素数量到达容量的3/4的时候开始扩容(扩容机制下面会提)。

        1. 下面开始HashMap的核心方法。put(K key,V value)





       重点一:238行(注意我这里行数和源码不一样)hash值计算。

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

        这里代码不难看懂,用key的 hashcode 值和 hashcode 值右移16位进行异或操作的值作为返回值。为什么这么做呢,以 "money" 为 key 举例。字符串 "money" 的hashcode为:104079552。二进制:110001101000010000011000000   。右移 16 位之后 000000000000000011000110100  。先看一下如果不做这个操作会出现什么情况:

        // (h = key.hashCode()) ^ (h >>> 16)
        // 0110 0011 0100 0010 0000 1100 0000    // h
        // 0000 0000 0000 0000 0110 0011 0100    // h >>> 16
        // 0110 0011 0100 0010 0110 1111 0100    // h ^ (h >>> 16)
        // 0000 0000 0000 0000 0000 0000 1111    // 16 - 1
        // 0110 0011 0100 0010 0110 1111 0100    // h & (16 - 1)

        在谈这个问题之前,我们需要先了解一下什么叫做哈希碰撞。我们都知道HashMap的数据结构是 数组+链表(+红黑树)。那么一个元素被存放的时候就要计算hash索引,即它要被存放在数组哪个位置。比如计算出来的hash = 5。如果数组的第五个位置已经有元素了,那么就称为出现了哈希碰撞。


        上面代码中 h 是key的hashcode。因为hash索引值最终是 h & (容量 - 1) 来得出的,我们都知道HashMap容量是2的幂次方(最小为16)。减一之后二进制表现为 ***...*** 1111的形式。所以hash索引的值基本上取决于这个 h 。这里一开始的时候 HashMap 容量是16 。如果不进行无符号右移16位操作 将 h & (16 - 1) 。我们会发现运算之后  h 的高位特征消失。那么这高位的一点点差异就可能容易导致一次哈希碰撞,造成哈希碰撞的概率就被加大了。再看我们将 h >>> 16 之后。高位特征跑到低位。然后 h ^ (h >>> 16) 将高低位特征进行混合,这样再与容量进行按位与操作就降低了 hash 碰撞的概率。不得不说这真的是非常NB的做法。还记得刚开始提的 loadFactor  吗,为什么是0.75?因为源码有一段注释说明,当选取这个数字时,哈希碰撞超过8次几乎是不可能的!


        重点二:269行 从链表转为红黑树

        这之前的代码虽然乍看之下没有看下去的欲望,但是仔细分析还是不难的,而且我也放了注释。就不多说了,直接看JDK1.8新增的红黑树。267行 TREEIFY_THRESHOLD 这个值是 8 。用来判断当前数据结构是否要从链表和红黑树之间发生变化。266行将数据放进链表之后,判断当前链表的长度是不是等于8。如果是,那么就要改变存储的数据结构为红黑树。为什么要做这个改变呢?我们都知道链表是基于线性表的数据结构,物理内存不连续,只存放了下一个节点的指针,查找效率随着长度增加越来越低。而红黑树是一个自平衡二叉树,其本身的旋转和变色等特性能够保证增删和查询的效率。为了防止数据量过多导致查询效率问题,JDK8才引入了红黑树结构。


        重点三:287,288行 扩容机制

        由于篇幅问题这里就不再贴代码了……HashMap每次都是在元素数量大于容量的 3/4 时进行扩容,每次扩容都是2的幂次方,这里去看288行的 resize() 方法源码就一目了然了,因为要保证计算的hash索引均匀分布。如果不是2的幂次方,那么在做 h & (n - 1) 操作的时候,由于 n-1 二进制位上的0会导致和重点一一样的问题,丢失key的hashcode高低位的特征,增加哈希碰撞的概率。


          不知不觉已经写了这么多,原谅博主文采实在不好,自己也感觉写的很乱……代码细节基本有注释,希望大家能够参考,有错误欢迎指正!感觉有太多的话写不不出来如果大家哪里有问题可以给我留言一起交流。另外文章为原创,转载请注明出处,谢谢。


        

转载请注明出处:转载请注明出处

上一篇 : 人活着到底是为了什么? 下一篇 : 我的爱情观

留言评论

所有回复

暮色妖娆丶

96年草根站长,2019年接触互联网踏入Java开发岗位,喜欢前后端技术。对技术有强烈的渴望,2019年11月正式上线自己的个人博客