游客您好
第三方账号登陆
  • 点击联系客服

    在线时间:8:00-16:00

    客服电话

    020-85534346

    电子邮件

    81058337@qq.com
  • 码云社APP

    随时掌握码云社动态

  • 扫描二维码

    关注砺锋微信公众号

害怕面试被问HashMap?这一篇就搞定了!

发布时期:2020-1-7 16:28
阅读:171 回复:0

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

搞定HashMap

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

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

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

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

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

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

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

Map是个啥?

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

害怕面试被问HashMap?这一篇就搞定了!上图展示了Map的家族,都是狠角色啊,我们对这些其实都要了解并掌握,这里简单的介绍下这几个狠角色:

TreeMap从名字上就能看出来是与树有关,它是基于树的实现,而HashMap,HashTable和ConcurrentHashMap都是基于hash表的实现,另外这里的HashTable和HashMap在代码实现上,基本上是一样的,还记得之前在讲解ArrayList的时候提到过和Vector的区别嘛?这里他们是很相似的,一般都不怎么用HashTable,会用ConcurrentHashMap来代替,这个也需要好好研究,它比HashTable性能更好,它的锁粒度更小。

由于这不是本文的重点,只做简单说明,后续会发文单独介绍。

简单来说,Map就是一个映射关系的数据集合,就是我们常见的k-v的形式,一个key对应一个value,大致有这样的图示害怕面试被问HashMap?这一篇就搞定了!这只是简单的概念,放到具体的实例当中,比如在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。

感谢阅读

好了,到了这里就差不多了,开篇就说过HashMap可以说是Java集合的精髓了,想要彻底搞懂真心不容易,但是我们所掌握的应该足够应对平常的面试,关于HashMap更多的高级内容,后续会继续分享。

感谢大家的阅读,如有错误之处欢迎指正!

TOOBUG(开发工程师)-本文作者
一个毫无志向的程序员,我就是我,不是toobug
171 0 2020-1-7 16:28
本文暂无评论,快来抢沙发!

扫一扫关注官方微信号

最前沿的技术信息一手掌握

滚动新闻
CODESEEDING(码云社)一家致力于程序员成长、以内容为核心、以提问为引导的多元化成长社区。我们在线上为技术爱好者提供了一个优质的交流氛围环境,在线下同样和众多高校联合开办了技术沙龙品牌。
020-85534346
关注我们
  • 访问移动H5版
  • 官方微信公众号

码云社 - CODESEEDING 2.0© 2018-2019 码云社. TOOBUG ( 粤ICP备16114193号-3 )