Java 面试笔记之 HashMap 和 ConcurrentHashMap

HashMap 和 ConcurrentHashMap 都是面试常考知识点，比如：如何存储数据、如何扩容、如何获取及删除数据，下面的内容是结合面试经历和阅读源码而总结出来的笔记，祝各位顺利找到满意的高新工作。

本篇文章你将会获得以下知识：

HashMap 笔记

• 主要属性
• 数据结构
• put() 主要流程及源码分析
• resize() 主要流程及源码分析
• get() 主要流程及源码分析
• remove() 主要流程及源码分析

ConcurrentHashMap 笔记

• 主要属性
• 数据结构
• put() 主要流程及源码分析
• resize() 主要流程及源码分析
• get() 主要流程及源码分析
• remove() 主要流程及源码分析

由于篇幅有限，这边只展示一部分，其余知识点已经整理成文档，有需要的朋友可以点一点下方链接免费领取！

链接：1103806531暗号：CSDN

HashMap学习

• HashMap是基于哈希表实现的Map接口，且允许null键和null值
• HashMap的实现不是同步的！！因此它不是线程安全的
• HashMap的映射不是有序的！

JDK1.8以前，HashMap是由数组 + 链表 组成的！数组是HashMap的主体，链表则是主要为了解决哈希冲突！！！而存在的（“拉链法解决冲突”）

哈希冲突：

​ 两个对象调用的hashCode方法计算的哈希码值一致，导致计算的数组索引值相同

JDK1.8以后在解决哈希值冲突时，有了较大的变化！！！，当链表长度大于阔值（红黑树的边界值，默认为8），并且当前数组的长度大于64时，此时索引位置上的所有数据改为使用红黑树存储

注意：将链表转换成红黑树前会判断，即使阔值大于8，但是数组长度小于64，此时并不会将链表变为红黑树，而是选择进行数组扩容！！！

因为数组比较小的时候，应该尽量避免红黑树结构，这种情况下，反而会降低效率！因为红黑树会进行左旋转、右旋转、变色这些操作来保持平衡。同时数组长度小于64时，搜索时间相对要快一些。综上，只有在阔值大于8，数组长度小于64时，链表才转为红黑树。

一、存储过程

• jdk1.8之前，HashMap由 数组 + 链表 数据结构组成
• jdk1.8之后，HashMap由 数组 + 链表 + 红黑树 数据结构组成

Map<Integer, String> map = new HashMap<>();

1.当创建HashMap集合对象的时候，在JDK8以前，构造方法中创建一个长度是16的Entry[] table 用来存放键值对。在jdk8以后，不是在HashMap的构造方法底层创建数组了，是在第一次调用put方法时创建数组，Node[] table用来存储键值对数据的。

map.put(1 ," 一号");

2.假设向哈希表中存储1-1号数据，根据1调用Integer类中重写之后的hashCode()方法计算出值，然后结合数组长度采用某种算法计算出向Node数组中存储数据的空间的索引，

• 若计算出的索引空间没有数据，则直接将1-一号存储到数组中

map.put(2 ," 二号");

3.向哈希表中存储数据2-二号，假设2计算出的hashCode方法结合数组长度计算出的索引值和1计算出的hashCode方法结合数组长度计算出的索引值一样的话，那么此时数组空间不是null，此时底层会比较1和2的hash值是否一致！

• 若不一致，则在此空间划出一个节点来存储键值对（拉链法）

map.put(2 ," 三号");

4.假设向哈希表中存储数据2-三号，那么根据2调用hashCode方法结合数组长度计算出索引肯定和之前的2一样，那么此时比较后一个2和之前已经存储的2的hash值是否相等

• 若hash值相等，此时发生哈希冲突（碰撞）

  于是，底层会调用2所属类Integer中的equals方法比较两个内容是否相等：

• 相等：则将后添加的数据的value覆盖之前的value

• 不相等：那么继续向下和其他的数据的key进行比较，若都不相等，则划出一个节点存储数据

面试题：哈希表底层采用何种算法计算hash值？还有哪些算法可以计算出hash值？

1.底层采用的key的hashCode方法的值结合数组长度进行无符号右移(>>>)、按位异或(^)、按位与(&)计算出索引

2.还有平方取中法、取余数、伪随机数法

二、扩容

在不断的添加数据的过程，会涉及到扩容问题，当超出临界值（且要存放的位置非空）时，扩容。

默认的扩容方式为：扩容到原来容量的2倍，并将原有的数据复制过来

HashMap使用单链表时，时间复杂度为O(n)，使用红黑树的时间复杂度为O(logn)

• size表示HashMap中K-V的实时数量，注意这个不等于数组的长度
• threshold（临界值）= capacity（容量）* loadFactory（加载因子）
• size若超过这个临界值就重新resize（扩容），扩容后的HashMap容量是之前容量的两倍

扩容机制

当HashMap中的元素个数超过数组大小（数组长度 * loadFactory）时，就会进行数组扩容，loadFactor的默认值（DEFAULT_LOAD_FACTOR）是0.75，这是一个折中的值。

即默认情况下，数组大小为16，那么当HashMap中的元素个数超过16 * 0.75 = 12（即这个值就是阔值或者边界值threshold值！！！），就把数组的大小扩展为 2 * 16 = 32，即扩大一倍

当HashMap中一个链表的对象个数如果达到了8个，此时如果数组长度没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链表会变成红黑树，节点类型由Node变成TreeNode类型，当然，若映射关系被移除后，下次执行resize方法时判断树的节点个数低于6，也会再把树转换为链表！！！

没进行依次扩容，会税额这一次重新hash分配，并且会遍历hash表中所有的元素，非常耗时，我们应该尽量避免resize

HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算（n-1）&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到”原位置+旧容量“这个位置

最后

希望这篇文章对大家有帮助！

我这边也整理了一份 架构师全套**** 和关于java的系统化资料，包括java核心知识点、面试专题和20年最新的互联网真题、电子书等都有。有需要的朋友可以点一点下方链接免费领取！

链接：1103806531暗号：CSDN