共计 2387 个字符,预计需要花费 6 分钟才能阅读完成。
前言:
HashMap 应该算是 Java 后端工程师面试的必问题,因为其中的知识点太多,很适宜用来考查面试者的 Java 根底。比方 HashMap 和 HashTable 以及 ConcurrentHashMap,这个就是 hashmap 面试的精华,大家来一起看看是如何面试的吧!
收场
面试官: 你先自我介绍一下吧!
我: 我是 ,毕业于 **,目前在 – 公司做 – 零碎开发。开发的我的项目有 – 布拉布拉 ……
面试官: 看你简历上写相熟 Java 汇合,HashMap 用过的吧?
我: 用过的。(还是相熟的滋味)
面试官: 那你跟我讲讲 HashMap 的外部数据结构?
我: 目前我用的是 JDK1.8 版本的,外部应用数组 + 链表红黑树;
我: 不便我给您画个数据结构图吧:
面试官: 那你分明 HashMap 的数据插入原理吗?
我: 呃 …… 我感觉还是应该画个图比较清楚,如下:
- 判断数组是否为空,为空进行初始化;
- 不为空,计算 k 的 hash 值,通过 (n – 1) & hash 计算该当寄存在数组中的下标 index;
- 查看 table[index] 是否存在数据,没有数据就结构一个 Node 节点寄存在 table[index] 中;
- 存在数据,阐明产生了 hash 抵触 (存在二个节点 key 的 hash 值一样), 持续判断 key 是否相等,相等,用新的 value 替换原数据 (onlyIfAbsent 为 false);
- 如果不相等,判断以后节点类型是不是树型节点,如果是树型节点,发明树型节点插入红黑树中;
- 如果不是树型节点,创立一般 Node 退出链表中;判断链表长度是否大于 8,大于的话链表转换为红黑树;
- 插入实现之后判断以后节点数是否大于阈值,如果大于开始扩容为原数组的二倍。
面试官: 方才你提到 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,111111 + 1 = 1000000 = 2 的 6 次方(合乎大于 50 并且是 2 的整数次幂)
面试官: 你提到 hash 函数,你晓得 HashMap 的哈希函数怎么设计的吗?
我:(不是吧,非要问到我不会为止吗)hash 函数是先拿到通过 key 的 hashcode,是 32 位的 int 值,而后让 hashcode 的高 16 位和低 16 位进行异或操作。
重点来了!
面试官:HashMap 和 HashTable 的区别是什么?
我:HashMap 不是线程平安的
HashMap 是 map 接口的子类,是将键映射到值的对象,其中键和值都是对象,并且不能蕴含反复键,但能够蕴含反复值。HashMap 容许 null key 和 null value,而 hashtable 不容许。
HashTable 是线程平安。
HashMap 是 Hashtable 的轻量级实现(非线程平安的实现),他们都实现了 Map 接口,次要区别在于 HashMap 容许空(null)键值(key), 因为非线程平安,效率上可能高于 Hashtable。
HashMap 容许将 null 作为一个 entry 的 key 或者 value,而 Hashtable 不容许。HashMap 把 Hashtable 的 contains 办法去掉了,改成 containsvalue 和 containsKey。因为 contains 办法容易让人引起误会。Hashtable 继承自 Dictionary 类,而 HashMap 是 Java1.2 引进的 Map interface 的一个实现。最大的不同是,Hashtable 的办法是 Synchronize 的,而 HashMap 不是,在多个线程拜访 Hashtable 时,不须要本人为它的办法实现同步,而 HashMap 就必须为之提供外同步。Hashtable 和 HashMap 采纳的 hash/rehash 算法都大略一样,所以性能不会有很大的差。
那 ConcurrentHashMap 呢,它是干嘛的?
尽管 jdk 提供了 HashMap 和 HashTable 然而如何同时满足线程平安和效率高呢,显然这两个都无奈满足,所以就诞生了 ConcurrentHashMap 神器,让咱们利用于高并发场景。
该神器采纳了分段锁策略,通过把整个 Map 分成 N 个 Segment(相似 HashTable),能够提供雷同的线程平安,效率晋升 N 倍,默认晋升 16 倍。
ConcurrentHashMap 的长处就是 HashMap 和 HashTable 的毛病,当然该神器也是不反对键值为 null 的
ConcurrentHashMap 的呈现也意味着 HashTable 的闭幕,所以在当前的我的项目中,尽量少用 HashTable。
面试官:(心田 os: 小伙子能够的,对底层理解的很深啊,根底很好,剩下的不必问了)
你的程度我这边根本理解了,我对你还是比较满意的,根底和原理还是很好的,我这边会跟下面进行反馈,会对你的简历进行评估筛选,通过了会进行二面的,你回去等告诉吧。
我:好的好的,谢谢面试官,我这边先回去了。心田 OS:好险好险,一个 hashmap 差点被问倒,幸好面试前好好看了一下,不然明天就难堪了,回家等告诉!
《2020 最新 Java 根底精讲视频教程和学习路线!》
链接:https://juejin.cn/post/691758…