大厂面试HashMap,一定要注意这个点,很多人栽在了这儿

2021/6/12 18:29:57

本文主要是介绍大厂面试HashMap,一定要注意这个点,很多人栽在了这儿,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Hashmap是Java中最常用的集合类型,使用非常广泛。不过,有些细节问题很多人没有关注过,这也使很多人在面试时栽了跟头!比如,阿里很多团队为了考察候选人的基础,就出了这么一个面试题:为什么HashMap的初始长度和扩容长度是2的N次幂?

HashMap的数据结构


先了解一下HashMap的数据结构,在java中,数组和链表是最常用的两个基础数据结构,很多集合类都基于他们实现。HashMap也不例外,是一个链表数组,即数组和链表的结合体,当链表长度超过8时,链表转换为红黑树。

大厂面试HashMap,一定要注意这个点,很多人栽在了这儿

 

如上图,HashMap的数组元素存放了key-value键值对或者链表。当新建一个HashMap的时候,就会初始化一个数组。我们来看看java代码:

大厂面试HashMap,一定要注意这个点,很多人栽在了这儿

 

table 就是那个数组,Node是数组中的元素,Node中存放了key,value键值对。

大厂面试HashMap,一定要注意这个点,很多人栽在了这儿

 

当table中某个位置发生hash冲突时,就会自动拉链,该位置的元素也就变成了Node链表。从上图我们可以看到next成员变量,next会指向链表的下一个元素。

当我们往HashMap中put元素的时候,会先根据key的hashCode值计算出数组中对应的位置(下标),然后再把这个元素的key,value封装成Node放到对应的位置上。如果这个元素所在的位置已经存放了其他元素,那么在同一个位置上的元素将以Node链表的形式存放,新加入的Node放在链表头。从HashMap中get元素时,首先会根据key的hashCode值计算出数组中对应的位置,然后通过equals方法在对应位置的链表中找到相应的元素。所以,我们要尽量减少Hash冲突,如果每个位置上只有一个元素而不是形成链表,HashMap的效率将是最高的,时间复杂度将达到最理想的O(1)。不过现实场景中,基本都会拉链,HashMap查询过程也往往需要做链表遍历,这也导致了查询效率的下降。在Java1.8后HashMap数据结构中引入了红黑树,当链表过长时,链表会被转化为树形结构,以此来降低查询时遍历的层级和次数。

为什么长度是2的N次幂?


先了解一下哈希算法。Hash(哈希),一般翻译成散列,Hash是把任意长度的输入通过散列算法变换成固定长度的输出,该输出就是散列值(Hash值)。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说Hash算法就是一种将无限的数据映射到有限地址空间的算法。

我们可以看到在HashMap中要找到某个元素,需要根据key的hashcode(hash值)来求得对应数组中的位置。这种将较大规模的输入数据映射到有限地址空间的算法就是hash算法(hashmap初始化时数组长度只有16,但基于链表数组的数据结构,hashmap可存储的元素数量却远大于16)。前面说过hashmap的数据结构是数组和链表的结合,所以我们希望hashmap里的元素尽量分布均匀些,尽量使每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以取到数组上对应位置的元素,而不用再去遍历链表。

可能很多人想到了用hashcode对数组长度取模得到数组下标位置,不错,取模的方式确实可以让数据分布比较均匀。但是,有没有更好的方式呢?

大厂面试HashMap,一定要注意这个点,很多人栽在了这儿

 

Hashmap是利用位运算实现的,位运算是基于二进制进行计算的,在计算机世界里所有数据最终都要转为二进制数据,所以位运算的效率非常高。位运算效率至少比取模运算高一个数量级。从上图可以看到,Hashmap在put(get)元素时通过 (n-1) & hash 做位运算,来获取数组下标位置,其中n是数组长度。

利用key的hashcode值,和数组的长度减一(n-1)做“与”运算。使用位运算,除了效率高,还有其他玄机吗?当HashMap的容量是2的n次幂时,(n-1)的2进制也就是11111***111这样形式的,此时与key的hashcode值进行位运算时,能够充分的散列,使添加的元素能够均匀分布在数组的每个位置上,使hash碰撞几率降到最低,下面举例说明。

大厂面试HashMap,一定要注意这个点,很多人栽在了这儿

 

HashMap的长度是16(2的4次幂)时,它的二进制是10000,(n-1)的二进制是01111,与hash值的计算结果如上图所示。我们可以看到当hashmap长度是2的n次幂时,n-1与不同的hashcode值的位运算结果都不一样,添加的元素能够均匀分布在数组的不同位置,降低了hash冲突。

大厂面试HashMap,一定要注意这个点,很多人栽在了这儿

 

再看看HashMap的长度不是2的N次幂的情况,假设长度是10,它的二进制是01010,(n-1)的二进制是01001,与hash值的计算结果如上图所示。我们可以看到当HashMap容量不是2的n次幂时,n-1与不同的hashcode值的位运算结果有好几个都一样,这样在添加元素时就产生了严重的hash冲突。

所以,当数组长度为2的n次幂时,不同的key通过位运算获取的数组下标冲突的几率会比较小。冲突少了,添加元素的效率自然会更高,数据在数组上的分布也会更均匀,相应的链表长度也比较短。查询时,由于数据分布均匀,链表长度也比较平均,减少了遍历次数,查询效率也就会更高。

位运算虽然不是什么高深的知识,但是和计算机底层操作非常紧密,是进阶程序高手的必备技能。如果你有读源码的习惯,会发现JDK中有很多对位运算的应用。我们在日常开发中,不妨多用用位运算,一来可以提高程序性能,二来也可以帮自己养成对技术精深探究的习惯,让自己在技术的道路上越走越远!



这篇关于大厂面试HashMap,一定要注意这个点,很多人栽在了这儿的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程