我说HashMap初始容量是16,面试官让我回去等通知
持续创作,加速成长!这是我参与「掘金日新计划 · 10 月更文挑战」的第3天,点击查看活动详情
众所周知HashMap是工作和面试中最常遇到的数据类型,但很多人对HashMap的知识止步于会用的程度,对它的底层实现原理一知半解,了解过很多HashMap的知识点,却都是散乱不成体系,今天一灯带你一块深入浅出的剖析HashMap底层实现原理。
看下面这些面试题,你能完整的答对几道?
1. HashMap底层数据结构?
JDK1.7采用的是数组+链表,数组可以通过下标访问,实现快速查询,链表用来解决哈希冲突。
链表的查询时间复杂度是O(n),性能较差,所以JDK1.8做了优化,引入了红黑树,查询时间复杂度是O(logn)。
JDK1.8采用的是数组+链表+红黑树的结构,当链表长度大于等于8,并且数组长度大于等于64时,链表才需要转换成成红黑树。
2. HashMap的初始容量是多少?
如果面试的时候,你回答是16,面试官肯定让你回去等通知。
JDK1.7的时候初始容量确实是16,但是JDK1.8的时候初始化HashMap的时候并没有指定容量大小,而是在第一次执行put数据,才初始化容量。
```java // 负载因子大小 final float loadFactor;
// 默认负载因子大小 static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 初始化方法 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } ```
执行new HashMap()方法初始化的时候,只指定了负载因子的大小。
3. HashMap的put方法流程?
- 计算key的哈希值
- 判断数组是否为空,如果为空,就执行扩容,初始化数据大小。
- 如果数组不为空,根据哈希值找到数组所在下标
- 判断下标元素是否为null,如果为null就创建新元素
- 如果下标元素不为null,就判断是否是红黑树类型,如果是,则执行红黑树的新增逻辑
- 如果不是红黑树,说明是链表,就追加到链表末尾
- 如果判断链表长度是否大于等于8,数组长度是否大于等于64,如果不是就执行扩容逻辑
- 如果是,则需要把链表转换成红黑树
- 最后判断新增元素后,判断元素个数是否大于阈值(16*0.75=12),如果是则执行扩容逻辑,结束。
源码如下:
```java // put方法入口 public V put(K key, V value) { // 计算哈希值 return putVal(hash(key), key, value, false, true); }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node
4. HashMap容量大小为什么要设置成2的倍数?
java
int index = hash(key) & (n-1);
为了更快的计算key所在的数组下标位置。
当数组长度(n)是2的倍数的时候,就可以直接通过逻辑与运算(&)计算下标位置,比取模速度更快。
5. HashMap为什么是线程不安全?
原因就是HashMap的所有修改方法都没有加锁,导致在多线程情况下,无法保证数据一致性和安全性。
比如:一个线程删除了一个key,由于没有加锁,其他线程无法及时感知到,还继续能查到这个key,无法保证数据的一致性。
比如:一个线程添加完一个元素,由于没有加锁,其他线程无法及时感知到,另一个线程正在扩容,扩容后就把上一个线程添加的元素弄丢了,无法保证数据的安全性。
6. 解决哈希冲突方法有哪些?
常见有链地址法、线性探测法、再哈希法等。
- 链地址法
就是把发生哈希冲突的值组成一个链表,HashMap就是采用的这种。
- 线性探测法
发生哈希冲突后,就继续向下遍历,直到找到空闲的位置,ThreadLocal就是采用的这种,以后再详细讲。
- 再哈希法
使用一种哈希算法发生了冲突,就换一种哈希算法,直到不冲突为止(就是这么聪明)。
7. JDK1.8扩容流程有什么优化?
在JDK1.7扩容的时候,会遍历原数组,重新哈希,对新数组长度逻辑与,计算出数据下标,然后放到新数组中,比较麻烦耗时。
在JDK1.8扩容的时候,会遍历原数组,然后统计出两组数据,一组是新数组的下标位置不变,另一组是新数组的下标位置等于原数组的下标位置加上原数组的长度。
比如:数组长度由16扩容到32,哈希值是0和32的元素,在新旧数组中下标位置不变,都是下标为0的位置。而哈希值是16和48的元素,在新数组的位置=原数组的下标+原数组的长度,也就是下标为16的位置。
- 再有人说synchronized是重量级锁,就把这篇文章扔给他看
- 不允许还有Java程序员不了解BlockingQueue阻塞队列的实现原理
- 深度剖析Java的volatile实现原理,再也不怕面试官问了
- 我说HashMap初始容量是16,面试官让我回去等通知
- 我说MySQL联合索引遵循最左前缀匹配原则,面试官让我回去等通知
- 查询效率提升10倍!3种优化方案,帮你解决MySQL深分页问题
- 别再问我MySQL为啥没走索引?就这几种原因,全都告诉你
- 老程序员总结的四条工作经验教训,一部血泪史,推荐观看
- 高级程序员必知必会,一文详解MySQL主从同步原理
- 记一次ThreadLocal引发的线上故障,年终奖没了,可能还面临辞退
- 面试官:高并发场景下,你们是怎么保证数据的一致性的?
- Java8有哪些新特性?
- 手撕HashMap源码jdk7版
- 面试官:你能写个LRU缓存吗?