网站首页 > 教程文章 正文
HashMap 和 ConcurrentHashMap 都是面试常考知识点，比如：如何存储数据、如何扩容、如何获取及删除数据，下面的内容是结合面试经历和阅读源码而总结出来的笔记（针对 Java 7 版本），祝各位顺利找到满意的高新工作。
本文你将会获得以下知识：
1.HashMap 笔记
主要属性
数据结构
put() 主要流程及源码分析
resize() 主要流程及源码分析
get() 主要流程及源码分析
remove() 主要流程及源码分析
2.ConcurrentHashMap 笔记
主要属性
数据结构
put() 主要流程及源码分析
resize() 主要流程及源码分析
get() 主要流程及源码分析
remove() 主要流程及源码分析
适合人群： Java 面试、技术整理总结。
温馨提示：下面是以 Java 7 版本进行讲解，除非有特定说明。
HashMap 笔记
主要属性
/**
* 存储元素的数组
*/
transient Entry<K,V>[] table;
/**
* 存放元素的个数，非 table 数组长度
*/
transient int size;
/**
* 阈值，计算公式：capacity * load factor
*/
int threshold;
/**
* 负载因子，默认 0.75，用于扩容
*/
final float loadFactor;
/**
* 记录结构性修改次数，用于快速失败
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* 真正存储数据的节点
*/
static class Entry<K,V> implements Map.Entry<K,V> {
//节点的 key 值
final K key;
//节点的 value 值
V value;
//下一个节点的引用
Entry<K,V> next;
//节点的 hash 值
int hash;
}
HashMap 属性的常考的知识点是 loadFactor，看过源码都能答得出是 0.75，也常考 modCount 的作用，可以这样回答，用于快速失败，比如：在遍历 HashMap 的同时删除集合中的某个元素，因为 expectedModCount 不等于 modCount，所以在没有遍历完毕之前就会报这个异常。
数据结构
如果面试官问 HashMap 数据结构是什么，可以直接回答数组 + 单链表。
put() 主要流程及源码分析
主要流程：
- 判断 Entry[] 数组是否为空数组，如果是则根据阈值 threshold 进行初始化；
- 如果 key 为 null，则把待新增数据放到 table[0] 的位置；
- 如果 key 不为 null，则计算待新增数据 key 的 hash 值，再经过取模计算出数组下标；
- 遍历数组下标对应的链表，如果找到 key 和 hash 值同时相等，则进行覆盖，返回旧值；
- 如果没有找到，先判断是否要扩容再插值，如果当前数组的长度 >= 阈值，并且定位到的那个数组不能为空，才进行扩容，扩容需要重新计算 hash 和数组下标；
- 最后将新值插入到链表的最前面（头插法）。
源码分析：
public V put(K key, V value) {
//判断 table 数组是否为空，如果是则根据阈值初始化 table
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果 key 为 null，则把待新增数据放到 table[0]的位置，返回旧值。
if (key == null)
return putForNullKey(value);
//计算待新增数据 key 的 hash 值
int hash = hash(key);
//经过取模计算出数组下标
int i = indexFor(hash, table.length);
//遍历数组下标对应的链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果找到 key 和 hash 值同时相等，则进行覆盖，返回旧值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//如果没有找到 key 和 hash 值同时相等，则执行新增操作
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果当前数组的长度>=阈值，并且定位到的那个数组不能为空
if ((size >= threshold) && (null != table[bucketIndex])) {
//进行扩容
resize(2 * table.length);
//重新计算 hash
hash = (null != key) ? hash(key) : 0;
//重新数组下标
bucketIndex = indexFor(hash, table.length);
}
//最后将新值插入到链表的最前面(头插法)
createEntry(hash, key, value, bucketIndex);
}
put()常考的知识点是如何定位数组下标，回答通过计算 key 的 hash 值，再根据 hash 值取模得出数组下标即可。
resize() 主要流程及源码分析
主要流程：
- 创建一个新的 Entry[] 数组（即原来的 2 倍），将数据迁移到新的 Entry 数组
- 迁移步骤是遍历旧的 Entry 数组的每一个元素，每个元素可能需要重新计算 key 的 hash 值，再根据 hash 值计算得出数组下标，再进行赋值（即数据迁移）；
- 迁移数据完毕后，修改引用，改为引用新数组（即替换旧数据）；
- 重新计算阈值，因为集合长度变化了。
源码分析：
void resize(int newCapacity) {
//创建一个新的 Entry[]数组(即原来的 2 倍)，newCapacity 这个参数是已经乘 2 后的值
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//将数据迁移到新的 Entry 数组
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//修改引用，引用新数组(即替换旧数据)
table = newTable;
//重新计算阈值，因为集合长度变化了
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//遍历旧的 Entry 数组
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
//true 代表重新计算 hash 值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//计算数组下标
int i = indexFor(e.hash, newCapacity);
//数据迁移
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
resize() 常考的知识点是什么情况下需要扩容，回答当前数组的长度 >= 阈值，并且定位到的那个数组不能为空才进行扩容即可。
get() 主要流程及源码分析
主要流程：
- 如果 key 为 null，则从数组 table[0] 中取值
- 如果 key 不为 null，则根据 put() 方法的方式计算出数组的下标；
- 遍历数组下标对应的链表，如果找到 key 和 hash 值同时相等就返回对应的值，否则返回 null。
源码分析：
public V get(Object key) {
//如果 key 为 null，则从数组 table[0]中取值
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//计算待新增数据 key 的 hash 值
int hash = (key == null) ? 0 : hash(key);
//取模计算出数组下标，遍历链表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//如果找到 key 和 hash 值同时相等就返回对应的值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
get() 常考的知识点跟 put() 差不多，也是如何定位数组下标。
remove() 主要流程及源码分析
主要流程：
- 根据 get() 方法的方式计算出数组的下标；
- 遍历数组下标对应的链表，如果找到 key 和 hash 值同时相等就删除对应的值并返回被删除的 value，否则返回 null。
源码分析：
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
//计算 hash 值
int hash = (key == null) ? 0 : hash(key);
//计算数组下标
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
//遍历链表
while (e != null) {
Entry<K,V> next = e.next;
Object k;
//如果找到 key 和 hash 值同时相等就删除对应的值并返回被删除的 value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
//如果没找到 key 和 hash 值同时相等，则进入下一个循环
prev = e;
e = next;
}
return e;
}
remove() 常考的知识点是删除操作返回值是被删除的 key，还是 value，答案是 value 或者 null（删除一个不存在的元素）。
ConcurrentHashMap 笔记
主要属性
/**
* 段掩码，用于定位段，默认值 15，是不可变的
*/
final int segmentMask;
/**
* 段偏移量，用于定位段，默认值 28，是不可变的
*/
final int segmentShift;
/**
* 段数组
*/
final Segment<K,V>[] segments;
static final class Segment<K,V> extends ReentrantLock implements Serializable {
/**
* 真正存储数据的数组
*/
transient volatile HashEntry<K,V>[] table;
/**
* 用于统计当前 Segement 的大小，即 HashEntry 数组的长度
*/
transient int count;
/**
* 记录结构性修改次数，用于快速失败
*/
transient int modCount;
/**
* 阈值
*/
transient int threshold;
/**
* 负载因子，默认 0.75
*/
final float loadFactor;
}
static final class HashEntry<K,V> {
//节点的 hash 值
final int hash;
//节点的 hash 值
final K key;
//节点的 value 值
volatile V value;
//下一个节点的引用
volatile HashEntry<K,V> next;
}
ConcurrentHashMap 属性的常考的知识点是 segments、segmentMask 和 segmentShift。可以认为一个 segment（段）就是一个 HashMap，多个 HashMap 组成一个 ConcurrentHashMap；segmentMask 和 segmentShift 组合起来使用，用于定位段的数组下标。
数据结构
如果面试官问 ConcurrentHashMap 数据结构是什么，可以直接回答 Segment 数组 + HashEntry 数组 + 单链表。
put() 主要流程及源码分析
主要流程：
- 计算待新增数据 key 的 hash 值；
- 根据 hash 值、segmentShift 和 segmentMask 通过无符号右移运算和位运算定位到哪个 Segment，一个 Segment 对应一个 HashEntry[] 数组；
- 尝试获取锁，如果获取失败则自旋获取锁；
- 根据 hash 值通过位运算得到 HashEntry 数组的下标，即得到链表的表头节点，然后遍历链表；
- 如果链表不为空，判断传入的 key 和 hash 值与当前遍历的 key 和 hash 值是否都相等，相等则覆盖旧的 value；
- 如果链表为空（即表头为空），则将根据待新增数据的 key 和 value 创建结点，即初始化链表；
- 判断元素个数是否超过了阈值，数组长度大于阈值 threshold 并且小于最大容量，则进行 rehash 扩容；
- 如果不需要扩容，则把新的节点放到 HashEntry[] 数组中对应的位置（即把新的节点设置成原链表的表头）；
- 最后释放锁。
源码分析：
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
//计算 key 的 hash 值
int hash = hash(key);
//根据 hash 值、segmentShift 和 segmentMask 通过无符号右移运算和位运算定位到哪个 Segment
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject (segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//尝试获取锁，如果获取失败则自旋获取锁
HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
//根据 hash 值通过位运算得到 HashEntry 数组的下标，即得到链表的表头节点
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
//遍历链表
for (HashEntry<K,V> e = first;;) {
//如果链表不为空
if (e != null) {
K k;
//判断传入的 key 和 hash 值与当前遍历的 key 和 hash 值是否都相等，相等则覆盖旧的 value
if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else { //如果链表为空（即表头为空）
if (node != null)
node.setNext(first);
else
//将根据待新增数据的 key 和 value 创建结点，即初始化链表
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
//判断元素个数是否超过了阈值，数组长度大于阈值 threshold 并且小于最大容量，则进行 rehash 扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
//如果不需要扩容，则把新的节点放到 HashEntry[]数组中对应的位置(即把新的节点设置成原链表的表头)
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
//释放锁
unlock();
}
return oldValue;
}
put() 常考的知识点是如何定位 Segment 数组下标，回答通过根据 hash 值、segmentShift 和 segmentMask 通过无符号右移运算和位运算计算得到即可；也会问到 put() 时发现待新增的元素 key 和 hash 值都已经存在，怎么处理？回答直接覆盖返回旧值即可。
resize() 主要流程及源码分析
主要流程：
- 创建新 HashEntry[]数组，数组长度是原来的 2 倍，重新计算新的阈值；
- 遍历旧数组，把每一个元素（即 HashEntry 链表）迁移到新数组里面，步骤如下；
- 如果旧数组只有一个结点，则直接放入新的数组中；
- 如果链表有多个结点，遍历旧链表，计算存放在新数组中的位置，使用头插法插入到新数组，即旧链表的表头结点做为新链表的尾结点；
- 迁移完成之后将待新增数据插入链表的头部（头插法），最后将新数组的引用替换旧的。
源码分析：
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
int newCapacity = oldCapacity << 1;
//重新计算新的阈值
threshold = (int)(newCapacity * loadFactor);
//创建新 HashEntry[]数组，数组长度是原来的 2 倍
HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
int sizeMask = newCapacity - 1;
//遍历旧数组，把每一个元素(即 HashEntry 链表)迁移到新数组里面
for (int i = 0; i < oldCapacity ; i++) {
HashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
int idx = e.hash & sizeMask;
//如果旧数组只有一个结点，则直接放入新的数组中
if (next == null)
newTable[idx] = e;
else { //如果链表有多个结点
HashEntry<K,V> lastRun = e;
int lastIdx = idx;
//遍历旧链表
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
//计算存放在新数组中的位置
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
newTable[lastIdx] = lastRun;
// 使用头插法插入到新数组，即旧链表的表头结点做为新链表的尾结点
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
//迁移完成之后将待新增数据插入链表的头部（头插法），最后将新数组的引用替换旧的
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
resize() 常考的知识点是对谁进行扩容？Segment 数组，还是 HashEntry 数组？
答案是 HashEntry 数组，Segment 数组是使用 final 修饰的，不可变；迁移旧数组同一个链表数据到新数组时，是不是都在迁移到同一个链表中，答案是否定的，也可能在新数组的其他链表。
get() 主要流程及源码分析
主要流程：
- 计算获取数据 key 的 hash 值；
- 根据 hash 值、segmentShift 和 segmentMask 通过无符号右移运算和位运算定位到哪个 Segment，一个 Segment 对应一个 HashEntry[] 数组；
- 根据 hash 值通过位运算得到 HashEntry 数组的下标，即得到链表的表头节点，然后遍历链表；
- 判断传入的 key 和 hash 值与当前遍历的 key 和 hash 值是否都相等，相等则返回对应 value，否则返回 null。
源码分析：
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
//计算获取数据 key 的 hash 值
int h = hash(key);
//根据 hash 值、segmentShift 和 segmentMask 通过无符号右移运算和位运算定位到哪个 Segment
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
//根据 hash 值通过位运算得到 HashEntry 数组的下标，即得到链表的表头节点，然后遍历链表
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
//判断传入的 key 和 hash 值与当前遍历的 key 和 hash 值是否都相等，相等则返回对应 value
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
get() 常考的知识点是整个过程需不需要加锁，答案是不需要，因为读取数据的属性使用 volatile 修饰，实现了线程可见性，提高性能。
remove() 主要流程及源码分析
主要流程：
- 计算待删除数据 key 的 hash 值；
- 根据 hash 值、segmentShift 和 segmentMask 通过无符号右移运算和位运算定位到哪个 Segment，一个 Segment 对应一个 HashEntry[] 数组；
- 尝试获取锁，如果获取失败则自旋获取锁；
- 跟 get() 算法一样找到待删除结点，如果找不到则返回 null；
- 如果找到，假如待删除是表头节点，则把待删除节点的下一个节点设置为头节点，从而达到删除节点效果；
- 假如不是头结点，则把待删除节点的上一个节点的 next 指向待删除节点的下一个节点，从而达到删除节点效果；
- 最后释放锁。
源码分析：
public V remove(Object key) {
//计算待删除数据 key 的 hash 值
int hash = hash(key);
//根据 hash 值、segmentShift 和 segmentMask 通过无符号右移运算和位运算定位到哪个 Segment
Segment<K,V> s = segmentForHash(hash);
return s == null ? null : s.remove(key, hash, null);
}
final V remove(Object key, int hash, Object value) {
//尝试获取锁，如果获取失败则自旋获取锁
if (!tryLock())
scanAndLock(key, hash);
V oldValue = null;
try {
HashEntry<K,V>[] tab = table;
//计算 HashEntry 数组的下标
int index = (tab.length - 1) & hash;
//找到对应的 HashEntry 数组
HashEntry<K,V> e = entryAt(tab, index);
HashEntry<K,V> pred = null;
//遍历链表
while (e != null) {
K k;
HashEntry<K,V> next = e.next;
//判断传入的 key 和 hash 值与当前遍历的 key 和 hash 值是否都相等，相等则找到待删除的元素
if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
V v = e.value;
if (value == null || value == v || value.equals(v)) {
if (pred == null)
//假如待删除是表头节点，则把待删除节点的下一个节点设置为头节点，从而达到删除节点效果
setEntryAt(tab, index, next);
else
//假如不是头结点，则把待删除节点的上一个节点的 next 指向待删除节点的下一个节点，从而达到删除节点效果
pred.setNext(next);
++modCount;
--count;
oldValue = v;
}
break;
}
pred = e;
e = next;
}
} finally {
//释放锁
unlock();
}
//返回旧值
return oldValue;
}
remove() 常考的知识点是在已经找到存储待删除元素的节点情况下，如何删除此节点，删除分两种情况，情况 1 待删除节点是头节点，则把待删除节点的下一个节点设置为头节点；情况 2 待删除节点不是头节点，则把待删除节点的上一个节点的 next 指向待删除节点的下一个节点。
- 上一篇： 架构篇-一分钟掌握可扩展架构
- 下一篇： 揭秘HashMap扩容机制:为何应用变慢，如何彻底解决问题?
猜你喜欢
- 2025-04-27 Java程序员，一周Python入门:数组，元组，集合，集合，字典
- 2025-04-27 redis Scan 踩坑记 key的模糊匹配
- 2025-04-27 Java开发面试官终结者!HashMap高频面试题总结，务必拿下
- 2025-04-27 内存溢出OutOfMemoryError科普系列一
- 2025-04-27 关于API接口的签名和权鉴，你知道多少?
- 2025-04-27 Java学习总结 2020/4/8
- 2025-04-27 LinkedHashMap源码分析及LRU实现原理
- 2025-04-27 揭秘HashMap扩容机制:为何应用变慢，如何彻底解决问题?
- 2025-04-27 架构篇-一分钟掌握可扩展架构
- 2025-04-27 我是如何做列表页的
- 最近发表
- 标签列表
-
- location.href (44)
- document.ready (36)
- git checkout -b (34)
- 跃点数 (35)
- 阿里云镜像地址 (33)
- qt qmessagebox (36)
- md5 sha1 (32)
- mybatis plus page (35)
- semaphore 使用详解 (32)
- update from 语句 (32)
- vue @scroll (38)
- 堆栈区别 (33)
- 在线子域名爆破 (32)
- 什么是容器 (33)
- sha1 md5 (33)
- navicat导出数据 (34)
- 阿里云acp考试 (33)
- 阿里云 nacos (34)
- redhat官网下载镜像 (36)
- srs服务器 (33)
- pico开发者 (33)
- https的端口号 (34)
- vscode更改主题 (35)
- 阿里云资源池 (34)
- os.path.join (33)