用最简单的大白话聊一聊面试必问的HashMap原理和部分源码解析

HashMap在面试中经常会被问到,一定会问到它的存储结构和实现原理,甚至可能还会问到一些源码

今天就来看一下HashMap

首先得看一下HashMap的存储结构和底层实现原理

用最简单的大白话聊一聊面试必问的HashMap原理和部分源码解析

如上图所示,HashMap底层是用数组+链表+红黑树实现的,其中红黑树是JDK1.8对HashMap优化之后加入的,当链表的长度大于8的时候会由链表结构转为红黑树,这些等下在看源码分析的时候都可以看到具体的实现。

那为什么用这几种数据结构来实现?

这种结构在数据结构上称为 散列链表 ,其中的数组就相当于一个一个的桶(Bucket),当有数据准备存进去的时候,它会通过一定的散列算法去计算,尽可能的让数据平均的命中到各个桶上面去,尽可能的避免哈希碰撞。如果发生哈希碰撞,就是不同的数据最后落到了同一个桶上的时候,就采用链表的方式来存储,但是链表长度比较长了的时候,去存储数据,读取数据都需要不停的去遍历循环,所以此时再采用链表结构的话效率会明显下降,所以JDK1.8之后做了优化,当链表的长度大于8的时候就由链表转为红黑树来存储。红黑树是平衡二叉树的其中一种实现,它比普通的二叉树表现更优异,因为普通的查询二叉树在一定条件下也可能会变成链表结构,而红黑树它是平衡二叉树的一种,它是通过左旋右旋变色等保持树的平衡。

简单的了解了HashMap的存储结构后,下面来讲下HashMap其中三个方法的源码

一、hash()方法

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

这个方法里看似简单,却暗藏玄机。

它是拿到了key本身的hashCode后,又做了一次运算,先将原来的hashCode无符号右位移16位,然后再将原来的hashCode异或(^)上这个位移后的值,最后得到一个值。

补充知识:

表示右移,如果该数为正,则高位补0,若为负数,则高位补1。

表示无符号右移,也叫逻辑右移,即若该数为正,则高位补0,而若该数为负数,则右移后高位同样补0。

^ 表示异或运算,每个位相同为0,不同为1

比如:

0 ^ 1 得 1

1 ^ 1 得 0

0 ^ 0 得 0

1 ^ 0 得 1

那为什么要无符号右移16位后做异或运算?key本身的hashCode直接拿来用不好吗?

我们做一个简单演练

用最简单的大白话聊一聊面试必问的HashMap原理和部分源码解析

将h无符号右移16为相当于将高区16位移动到了低区的16位,再与原hashcode做异或运算,可以将高低位二进制特征混合起来

从上文可知高区的16位与原hashcode相比没有发生变化,低区的16位发生了变化

我们可知通过上面(h = key.hashCode()) ^ (h >>> 16)进行运算可以把高区与低区的二进制特征混合到低区,那么为什么要这么做呢?

我们都知道重新计算出的新哈希值在后面将会参与hashmap中数组槽位的计算,计算公式:(n – 1) & hash,假如这时数组槽位有16个,则槽位计算如下:

用最简单的大白话聊一聊面试必问的HashMap原理和部分源码解析

仔细观察上文不难发现,高区的16位很有可能会被数组槽位数的二进制码屏蔽,如果我们不做刚才移位异或运算,那么在计算槽位时将丢失高区特征

也许你可能会说,即使丢失了高区特征不同hashcode也可以计算出不同的槽位来,但是细想当两个哈希码很接近时,那么这高区的一点点差异就可能导致一次哈希碰撞,所以这也是将性能做到极致的一种体现

使用异或运算的原因

异或运算能更好的保留各部分的特征,如果采用&运算计算出来的值会向1靠拢,采用|运算计算出来的值会向0靠拢

为什么槽位数必须使用2^n

1、为了让哈希后的结果更加均匀

这个原因我们继续用上面的例子来说明

假如槽位数不是16,而是17,则槽位计算公式变成:(17 – 1) & hash

![](https://img-blog.csdnimg.cn/20200313150712334.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1XzM2MjIwNDgwMQ==,size_16,color_FFFFFF,t_70)

从上文可以看出,计算结果将会大大趋同,hashcode参加&运算后被更多位的0屏蔽,计算结果只剩下两种0和16,这对于hashmap来说是一种灾难

2、可以通过位运算e.hash & (newCap – 1)来计算,a % (2^n) 等价于 a & (2^n – 1)  ,位运算的运算效率高于算术运算,原因是算术运算还是会被转化为位运算

说了这么多点,上面提到的所有问题,最终目的还是为了让哈希后的结果更均匀的分部,减少哈希碰撞,提升hashmap的运行效率

二、put()方法

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

这个没什么好讲的,调用了下边的putVal()方法

三、putVal()方法

这个方法很重要,是往hashMap里put值的核心逻辑,下边源码里的每一行我都进行了注释

/**
     * Implements Map.put and related methods
     *
     * @param hash hash for keyput
     * @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;
        /**
         * 判断tab是不是为空,如果为空,则将容量进行初始化,也就是说,初始换操作不是在new HashMap()的时候进行的,而是在第一次put的时候进行的
         */
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
 
        /**
         * 初始化操作以后,根据当前key的哈希值算出最终命中到哪个桶上去,并且这个桶上如果没有元素的话,则直接new一个新节点放进去
         */
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
 
        /**
         * 如果对应的桶上已经有元素
         */
        else {
            Node<K,V> e; K k;
            /** 先判断一下这个桶里的第一个Node元素的key是不是和即将要存的key值相同,如果相同,则            
             *把当前桶里第一个Node元素赋值给e,这个else的最下边进行了判断,如果e!=null就执行把
             * 新value进行替换的操作 
             */
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果和桶里第一个Node的key不相同,则判断当前节点是不是TreeNode(红黑树),如果是,则进 
            //行红黑树的插入
            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);
                        //判断元素个数是不是大于等于8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //转换成红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
 
                    /**
                     * 如果在遍历的时候,发现key值相同(就是key已经存在了)就什么都不做跳出循环。因为在上边e = p.next的时候,已经记录e的Node值了,而下边进行了判断,如果e!=null就执行把新value进行替换的操作
                     */
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    
                    //把当前下标赋值给p并进行下一次循环
                    p = e;
                }
            }
 
            /**
              只要e不为空,说明要插入的key已经存在了,覆盖旧的value值,然后返回原来oldValue
              因为只是替换了旧的value值,并没有插入新的元素,所以不需要下边的扩容判断,直接 
               return掉
             */
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        /**
         * 判断容量是否已经到了需要扩充的阈值了,如果到了,则进行扩充
         * 如果上一步已经判断key是存在的,只是替换了value值,并没有插入新的元素,所以不需要判断 
         * 扩容,不会走这一步的
         */
        if (++size > threshold)
            resize();
 
        afterNodeInsertion(evict);
        return null;
    }

hashMap中还有其他的一些方法在此就不挨个来说了

可以在下方进行评论,一起学习进步

原文 

https://segmentfault.com/a/1190000022978769

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 用最简单的大白话聊一聊面试必问的HashMap原理和部分源码解析

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址