《安琪拉与面试官二三事》系列文章
一个HashMap能跟面试官扯上半个小时
一个synchronized跟面试官扯了半个小时
一个volatile跟面试官扯了半个小时
《安琪拉教鲁班学算法》系列文章
HashMap应该算是Java后端工程师面试的必问题,因为其中的知识点太多,很适合用来考察面试者的Java基础。
面试官: 你先自我介绍一下吧!
安琪拉: 我是安琪拉,草丛三婊之一,最强中单(钟馗不服)!哦,不对,串场了,我是**,目前在–公司做–系统开发。
面试官: 看你简历上写熟悉Java集合,HashMap用过的吧?
安琪拉: 用过的。(还是熟悉的味道)
面试官: 那你跟我讲讲HashMap的内部数据结构?
安琪拉: 目前我用的是JDK1.8版本的,内部使用数组 + 链表红黑树;
安琪拉: 方便我给您画个数据结构图吧:
面试官: 那你清楚HashMap的数据插入原理吗?
安琪拉: 呃[做沉思状]。我觉得还是应该画个图比较清楚,如下:
(n - 1) & hash
计算应当存放在数组中的下标 index;面试官: 陷入沉默,讲的这么清楚,难道是也关注了微信公众号【安琪拉的博客】,我继续按照套路问,刚才你提到HashMap的初始化,那HashMap怎么设定初始容量大小的吗?
安琪拉: [这也算问题??] 一般如果new HashMap()
不传值,默认大小是16,负载因子是0.75, 如果自己传入初始大小k,初始化大小为 大于k的 2的整数次方,例如如果传10,大小为16。(补充说明:实现代码如下)
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
补充说明:下图是详细过程,算法就是让初始二进制右移1,2,4,8,16位,分别与自己位或,把高位第一个为1的数通过不断右移,把高位为1的后面全变为1,最后再进行+1操作,111111 + 1 = 1000000 = (符合大于50并且是2的整数次幂 )
面试官: 你提到hash函数,你知道HashMap的哈希函数怎么设计的吗?
安琪拉: [问的还挺细] hash函数是先拿到 key 的hashcode,是一个32位的int值,然后让hashcode的高16位和低16位进行异或操作。
面试官: 那你知道为什么这么设计吗?
安琪拉: [这也要问],这个也叫扰动函数,这么设计有二点原因:
面试官: 为什么采用hashcode的高16位和低16位异或能降低hash碰撞?hash函数能不能直接用key的hashcode?
[这问题有点刁钻], 安琪拉差点原地
如对本文有疑问, 点击进行留言回复!!
网友评论