面试整理——Java集合

发表于 2019-10-21 更新于 2025-02-06 分类于面试整理

本文字数： 22k 阅读时长 ≈ 20 分钟

整理面试中常问的Java集合相关问题，持续更新中。

Java集合

第一节综合

问：java的集合框架有哪几种？

两种：collection和map，其中collection分为set和List。

问：平常用到哪些集合类？

答：ArrayList，LinkedList，HashSet，HashMap，TreeMap等（补充：ArrayQueue，PriorityQueue，TreeSet，EnumSet，LinkedHashSet，EnumMap，LinkedHashMap，WeakHashMap，IdentityHashMap）

Java集合(一) 概述

问：集合迭代器的原理？

集合接口Collection继承了接口Iterable，此接口有一个方法 iterator() 返回一个迭代器Iterator接口。

Iterator接口定义了三个方法：hasNext() 、next() 、remove() 。

在如AbstractList和ArrayList中通过私有类Itr实现Iterator接口，采用快速失败模式，定义了一个计数器ModCount来保证在遍历过程中内容未被修改，否则抛出异常。

问：快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

快速失败是指迭代器遍历集合对象时发现内容被同时修改，且修改导致了计数器与期待值不同，导致抛出异常Concurrent Modification Exception（迭代器内部有计数器ModCount，每次移动指针前会检查当前值是否是expected，若修改不会使modCount不匹配就不会抛出异常）

安全失败则是指相应集合并不直接在内部访问，而是先拷贝副本，在副本上进行遍历，所以遍历过程中的修改不会影响到读取。

问：了解了哪些并发安全集合，从list到map都讲一下？

被弃用的两个集合：vector，HashTable。
Collections对集合的安全封装（如Collections.synchronizedList）
Concurrent包提供的：ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListSet和ConcurrentLinkedQueue，还有加了写锁的CopyOnWriteArrayList和CopyOnWriteArraySet。

问：List，Map，Set 接口在存取元素时，各有什么特点？

List：元素存入有顺序，可重复。取元素时可以用迭代器遍历获取，也可以根据下标获取。
Map：元素按键值对存储，无存放顺序，键不可重复，值可重复。可以根据键获得值，也可以获得所有键或值的集合，以及键值组合的对象Entry的集合。
Set：元素存入无顺序，不可重复。取元素时需要用迭代器遍历获取。

问：接口RandomAccess的作用？

类似于Serializable和Cloneable，RandomAccess也是一个标记接口，表示对象支持快速随机访问。比如ArrayList实现了此接口，其底层是数组，而LinkedList则未实现此接口，其底层是链表。

对于支持快速随机访问的集合可以使用循环来高效遍历，而不支持的有序集合最好使用迭代器来遍历。

第二节 List

问：List你使用过哪些？

ArrayList和LinkedList使用的最多，也最具代表性。

问：你知道vector和ArrayList和linkedList的区别嘛？扩容机制等？

ArrayList实现是一个数组，可变数组，默认初始化长度为10，也可以我们设置容量，但是没有设置的时候是默认的空数组，只有在第一步add的时候会进行扩容至10（重新创建了数组），后续扩容按照3/2的大小进行扩容，是线程不安全的，适用多读取，少插入的情况。

linkedList是基于双向链表的实现，使用了尾插法的方式，内部维护了链表的长度，以及头节点和尾节点，所以获取长度不需要遍历。适合一些插入/删除频繁的情况。

Vector是线程安全的，实现方式和ArrayList相似，也是基于数组，但是方法上面都有synchronized关键词修饰。其扩容方式是原来的两倍。

问：ArrayList的实现？怎么扩容？怎么插入？怎么删除？在遍历ArrayList时，删除元素会发生什么？LinkedList呢？

ArrayList底层通过数组来存放元素，但因为实现了自动扩容所以也叫作动态数组。扩容、插入和删除操作都通过grow函数调用数组浅复制库函数（System.arraycopy），其中扩容通过复制生成副本返回一个新的数组，非尾部插入和删除则是对当前数组进行覆盖式的复制，删除操作最后会移除末尾元素。

对于ArrayList，删除元素时，后续元素会前移，所以如果遍历方向是正向，会漏掉删除操作后一位的元素判断，如果使用for-each循环遍历会因为修改了操作数而直接抛出异常。

对于LinkedList，删除元素时会先后断开要元素和前后节点的链接，然后重新链接前后节点，根据情况更新链表首尾节点，并清空元素值。

Java集合(三) List

问：ArrayList和LinkedList区别？使用场景？链表和数组的优缺点？

答：ArrayList是动态索引数组，LinkedList则是有序链表。前者可以快速随机访问，后者则会较慢。但链表更方便删除，因为只要局部变动，而数组则会影响到后续所有元素。所以数组易查难改，链表易改难查。LinkedList也通过迭代器进行插入操作。

ArrayList适合在频繁读取的场景，而LinkedList则适合在频繁插入删除的场景。

问：讲一下写时复制？写时复制和读写锁的区别？

写时复制即CopyOnWrite，通过延迟更新的策略，牺牲数据实时性，保证数据一致性和读线程互不阻塞。

相同点：两者都是通过读写分离思想实现，都实现了读线程间互不阻塞。
不同点：使用读写锁依然会存在线程阻塞等待的情况，而COW则牺牲了数据实时性，保证读线程不会存在等待。

问：CopyOnWriteArrayList 原理？

CopyOnWriteArrayList 通过写时复制思想来实现线程安全的动态数组，底层数据结构仍是对象数组，但被 volatile 修饰来保证可见性。通过可重入锁 ReentrantLock 来保证写线程安全，读操作与单线程无异，写操作则先获取锁，然后通过 System.arraycopy() 进行数组浅复制，在新数组上添加元素，最终再更新数组引用。因为 happens-before 规则，保证读线程可以感知。

问：ArrayBlockingQueue 和 LinkedBlockingQueue 区别？

队列中锁的实现不同：
- ArrayBlockingQueue 队列中的锁是没有分离的，即生产和消费用的是同一个锁；
- LinkedBlockingQueue 队列中的锁是分离的，即生产用的是 putLock ，消费是 takeLock 。
在生产或消费时操作不同：
- ArrayBlockingQueue 队列中在生产和消费的时候，是直接将枚举对象插入或移除的；
- LinkedBlockingQueue 队列中在生产和消费的时候，需要把枚举对象转换为 Node<E> 进行插入或移除，会影响性能。
队列大小初始化方式不同：
- ArrayBlockingQueue 实现的队列中必须指定队列的大小；
- LinkedBlockingQueue 实现的队列中可以不指定队列的大小，但是默认是 Integer.MAX_VALUE 。

第三节 Set

问：HashSet 和 TreeSet 原理？

HashSet 即散列集，因为散列的关系所以集合的访问顺序是随机的。底层是基于一个 HashMap 来实现的，相关操作也是直接调用 HashMap API来完成。其设计就是利用 HashMap 的键来存放元素，用统一的 PRESENT 来作为 HashMap 的值，利用 HashMap 的键的唯一性来实现集合的元素不重复。
TreeSet 即树集，与散列集不同，树集是一个有序集合，其排序通过红黑树来实现，每次新增元素时都会放在正确的排序位置，以新增操作的开销来实现有序访问。

第四节 Map

4.1 HashMap

问：说说你了解的HashMap吧？能讲讲HashMap的实现原理吗？HashMap的底层是什么？HashMap内部数据结构？1.8版本的优化 ⭐⭐⭐

hashMap

内部使用数组+链表的方式实现。默认负载因子是0.75。
通过散列函数把元素均匀的分散到不同的散列值上，也就是对应的数组下标上。
因为散列是不可靠的，会出现哈希冲突，所以采用链表来存放因为哈希冲突而产生的相同哈希值但不同的元素。
1.8版本后增加了红黑树进行优化，在链表结构超过8个节点后就裂变为红黑树，把查询的复杂度变成O(logn)。

操作：

get：计算hashcode，通过(n-1)&hash获取数组下标，遍历链表或红黑树找到节点。
put：通过(n-1)&hash获取数组下标，获取头节点，若为空则要新建Node，分别判断头节点是否命中，以及是否裂变为红黑树，循环遍历链表或红黑树找到节点或者未命中，若未命中则新建节点加入链表，并判断长度是否超过8要变树，若命中则更新value。
扩容：旧容量*2，遍历旧哈希表，重新ReHash再散列到新哈希表。
裂变：链表长度超过8就升级为红黑树。

1.8版本的优化：

计算hashcode优化为h^(h>>>16)，高16位不变，低16位变为原高16位和原低16位的异或，因为获取数组下标时(n-1)&hash，n一般很小，高16位失去意义，异或后可以降低哈希冲突发生的概率。
数组+链表优化为数组+链表+红黑树，使链表查询效率O(n/2)O(n)优化为O(logn)。
头插法改为尾插法，因为头插法多线程扩容时容易导致形成单循环链表，线程1先扩容，新链表顺序倒转，线程2恢复扩容，形成环状结构。
1.7版本扩容操作每个元素都要rehash，1.8优化为hash&oldCap=0则不需要变动位置，而要变动位置的新坐标new=旧坐标x+oldCap。证明：与oldCap=0，表示oldCap为1的位置为0，即oldCap=0100，则X0XX。求下标时为(n-1)&hash，即0011&X0XX，结果为00XX。扩容后(2n-1)&hash，即0111&X0XX，结果还是00XX。所以下标扩容前后不会变。

问：解决hash冲突的方法有哪些？⭐⭐

开放定址法、链地址法（拉链法）、再哈希法、公共溢出区、布谷鸟哈希。
开放定址法（Open Addressing）：当发生哈希冲突时，寻找数组中其他空闲位置的方法。
- 常见策略：
  - 线性探测： 从冲突位置开始，依次检查下一个位置，直到找到空闲位置为止。
  - 二次探测： 与线性探测类似，但是每次移动的步长是二次方数，例如 1，4，9，…。
  - 随机探测： 使用随机数生成器来确定下一个要检查的位置。
  - 双重散列：如果索引位置被占用，就用另一个哈希函数来决定步长。
- 优点：
  - 简单： 实现起来比较简单。
  - 节省空间： 不需要额外的链表等数据结构。
- 缺点：
  - 容易产生聚集： 线性探测容易产生聚集现象，导致查询效率降低。
  - 删除操作复杂： 删除元素时需要进行特殊处理，以避免影响其他元素的查找。
链地址法（Separate Chaining）：将所有哈希地址相同的元素都存储在同一个链表（或红黑树）中的方法。每个数组位置都指向一个链表的头部，当发生哈希冲突时，将新元素添加到链表的尾部。

优点：
- 简单： 实现起来比较简单。
- 解决聚集问题： 可以有效地解决聚集现象。
- 删除操作简单： 删除元素时只需要从链表中移除即可。
缺点：
- 占用额外空间： 需要额外的空间来存储链表。
- 查询效率可能降低： 当链表过长时，查询效率会降低。
再哈希法（Rehashing）：指使用多个不同的哈希函数。当发生哈希冲突时，使用第二个哈希函数计算新的哈希地址，直到找到空闲位置为止。

优点：
- 减少聚集： 可以有效地减少聚集现象。
缺点：
- 计算开销大： 需要计算多个哈希函数。
公共溢出区：建立一个公共溢出区，用于存储所有发生哈希冲突的元素。当发生哈希冲突时，将元素放入溢出区。

优点：
- 简单： 实现起来比较简单。
缺点：
- 查询效率可能降低： 当溢出区元素过多时，查询效率会降低。
布谷鸟哈希：使用两个哈希函数，每个元素有两个可能存储位置。如果发生冲突，踢出原有元素，原有元素再找新位置。
开发地址法会在发生哈希碰撞时通过探测技术继续在哈希表中找到空闲位置来存放，根据探测方式的不同有线性探测、二次探测和双散列探测。链地址法就是将每个散列表元素都对应一个链表。

问：hashmap查询的时间复杂度能达到O(1)是什么实现的？里面的索引是怎么计算的？⭐

HashMap查询时根据哈希映射计算得到哈希码，直接走数组索引找到对应链表，不考虑哈希冲突的情况，可以达到O(1)。
索引通过调用对象的hashcode方法获取原始哈希码，然后右移16位使高区16位和低区16位进行异或运算，保留原高区16位，因为高区16位基本用不到，这样融合高区和低区的特征。在计算数组索引时再通过 (n - 1) & hash 来得到相应下标。

问：HashMap什么时候会进行rehash？⭐

当所存键值对超过阈值，即容量和装填因子loadFactor的积时，HashMap需要扩容并因为容量的变更而对元素进行再散列。

问：HashMap的初始容量设置成多少比较合适呢？

一般设置为预测元素数的75%到150%，因为一般装填因子为0.75，扩容和再散列会比较影响哈希表性能，所以要尽量保证不会发生多次再散列。

问：HashMap为什么不是线程安全的？怎么让HashMap变得线程安全？HashMap多线程有什么问题？怎么解决？⭐

因为HashMap实现中并没有添加锁机制，多线程时容易导致数据错误。

比如：

put操作，多个线程得到相同的哈希码，可能会导致A线程结果覆盖掉B线程结果。
旧版本的resize因为头插法的实现多线程会导致单向循环链表，get操作会陷入死循环。

Collections.synchronizedMap()，生成一个新的SynchronizedMap，向HashMap实现中增加锁机制的设计可以使其线程安全。
使用线程安全的ConcurrentHashMap。虽然Hashtable有加锁，但synchronized会大大降低效率，而ConcurrentHashMap使用了分段锁技术，效率会更高。当然单线程的HashMap的效率更高，能使用就尽量使用。多线程环境下，也可以运用栈封闭、ThreadLocal类、UnmodifiableMap类等方式使用HashMap。

问：结合源码说说HashMap在高并发场景中为什么会出现死循环？

高并发场景中多线程间会发生竞争，HashMap在put时会因为容量不足而进行扩容，旧版本新增元素是头插法，新元素会插在前面链接老元素，而在扩容后新数组链表会倒置，多线程环境下，线程间竞争一个线程读取数据后挂起，另一个线程执行使链表倒置，线程恢复后继续执行形成循环链表，所以形成了死循环。

问：HashMap 扩容机制，为什么都是 2 的 N 次幂？⭐⭐

根据哈希码获取数组索引是 (n - 1) & hash ，计算机可以高效进行按位与运算，当数组长度是2的N次方，其减一后会是前0后1的二进制格式，因此在进行与运算时1的部分就可以充分散列，如果后面还有0就会导致不同哈希码与运算得到相同索引，使散布不均匀。

问：为什么HashMap装填因子是0.75？⭐

为什么是0.75呢？

当负载因子太小，就很容易触发扩容，如果负载因子太大就容易出现碰撞。所以这个是空间和时间的一个均衡点
0.75的负载因子中，能让随机hash更加满足0.5的泊松分布。

问：HashMap和HashTable和ConcurrentHashMap的区别？

HashMap：是map类型的一种最常用的数据结构，其底部实现是数组+链表/红黑树，其key是可以为null的，默认hash值为0，扩容以2的幂等次，是线程不安全的。
HashTable：实现形式和hashMap差不多，它是线程安全的，是继承了Dictionary，也是key-value的模式，但是其key不能为null。
ConcurrentHashMap：是并发包提供的一种线程安全的并发容器，采用分段的思想，早期版本通过分段锁Segment—基于ReetrantLock来实现的，1.8版本修改为 Node[] + CAS + Synchronized。

问：HashMap和HashTable有何不同？

Hashtable对部分方法有线程安全优化，而HashMap非线程安全。HashMap的键值允许为空，Hashtable则都不能为空。Hashtable因为使用synchronized效率不高，而HashMap在单线程环境下效率很高。

问：HashMap 和 WeakHashMap 的区别？

WeakHashMap通过弱引用来保存键，如果没有普通对象引用只剩弱引用在使用对象（忽略映射中value对对象的强引用），GC会在周期性的垃圾回收中收回这些无用对象。
当只剩弱引用在使用对象时WeakHashMap就相当于退化为了HashMap。

问：HashMap 和 ConcurrentHashMap 的区别？在 hash 上的区别？

ConcurrentHashMap线程安全，HashMap非线程安全。
ConcurrentHashMap插入前判断是否需要扩容，HashMap则是插入元素后。
1.8版本的ConcurrentHashMap和HashMap都通过Node数组来实现，但ConcurrentHashMap的Node的val和next是volatile修饰的。
TODO

问：HashMap 1.8版本前后的区别？JDK8 做了什么优化？最小树化容量？比如为什么是红黑树，别的树不可以吗；为什么 8 的时候树化，4 不可以吗？⭐⭐

HashMap优化：

计算hashcode优化为h^(h>>>16)，高16位不变，低16位变为原高16位和原低16位的异或，因为获取数组下标时(n-1)&hash，n一般很小，高16位失去意义，异或后可以降低哈希冲突发生的概率。
数组+链表优化为数组+链表+红黑树，使链表查询效率O(n/2)O(n)优化为O(logn)。
头插法改为尾插法，因为头插法多线程扩容时容易导致形成单循环链表，线程1先扩容，新链表顺序倒转，线程2恢复扩容，形成环状结构。
1.7版本扩容操作每个元素都要rehash，1.8优化为hash&oldCap=0则不需要变动位置，而要变动位置的新坐标new=旧坐标x+oldCap。证明：与oldCap=0，表示oldCap为1的位置为0，即oldCap=0100，则X0XX。求下标时为(n-1)&hash，即0011&X0XX，结果为00XX。扩容后(2n-1)&hash，即0111&X0XX，结果还是00XX。所以下标扩容前后不会变。

最小树化容量？

MIN_TREEIFY_CAPACITY = 64，区别于树化阈值8，其约束哈希表容量超过此值时才能将链表转换为红黑树，通过此参数可以决定是扩容还是树形化。
防止在哈希表容量较小时，链表长度可能频繁地在 8 附近波动，导致 HashMap 不断地进行树化和反树化操作，这会降低性能。

为什么是红黑树？

AVL树是高平衡二叉树，其树的调整和旋转频率更高，当然查询更快，适合查询多、增删少的场景。
红黑树则对平衡要求没那么高，调整代价也更低，旋转次数更少，同时查询也不慢，适合增删频繁的场景。
相比如AVL树等，在单链表过长时，通过优化为红黑树更有利于后续更多节点的插入删除操作，综合性能要优于AVL树。

为什么树化阈值是8：

首先当散列均匀时，链表升级为红黑树的概率不大：理想情况下随机散列函数，概率分布遵循泊松分布，链表长度达到8的概率几乎为不可能。
当节点数量较少时，采用红黑树的意义不大，且因为红黑树节点的大小是普通链表节点大小的两倍，所以还会造成空间上的浪费。

问：jdk1.8中，对HashMap和ConcurrentHashMap做了哪些优化？

HashMap优化：

优化了散列函数，通过移位异或，融合了高位特征；
底层由数组+链表改为数组+链表+红黑树，引入了红黑树来处理链表太长的极端情况，提高插入和查询整体效率；
头插法变为尾插法，链表顺序不会改变，从而优化了多线程的死循环问题。

ConcurrentHashMap优化：

舍弃了臃肿的Segment + HashEntry，改为Node + CAS + Synchronized：Segment继承了ReentrantLock，其分段区域在初始时即确定，即并发数 concurrentLevel是固定的；而后者的并发数 concurrentLevel 是和数组大小保持一致的，每次扩容，并发度扩大一倍。
引入了红黑树来处理链表太长的极端情况等
synchronized在JVM进行了优化：锁粗化、锁消除、锁自旋等等。

4.2 ConcurrentHashMap

问：讲一下你所知道的ConcurrentHashMap？ConcurrentHashMap分段锁？如何分段？1.7与1.8版本的区别？⭐⭐⭐

ConcurrentHashMap 介绍？
- ConcurrentHashMap 是 Java 并发包（JUC）提供的线程安全 Map 实现。
- 主要优化点：
  - JDK 1.7 采用 分段锁（Segment + ReentrantLock），减少锁粒度，提高并发性能。
  - JDK 1.8 采用 CAS + synchronized + 自旋锁，移除 Segment，优化性能，支持链表转红黑树。

JDK 1.7：Segment 分段锁

✅ 1.7 版数据结构

ConcurrentHashMap
 ├── Segment[] segments  // 16个Segment，类似小的HashMap，每个独立加锁
 │   ├── table[]         // 每个 Segment 维护自己的哈希表
 │   │   ├── HashEntry   // 组成链表的节点

ConcurrentHashMap 内部维护了 Segment[] 数组（默认16个），每个 Segment 相当于一个小的 HashMap，独立加锁。
**每个 Segment 继承 ReentrantLock**，写操作时锁住 Segment，不同 Segment 可以并发操作。
最终 size() 计算方式：所有 Segment 的 count 之和。

✅ 1.7 版 put 过程

计算 key 的 hash
确定 Segment（段）：初始化Segment通过并发级别 concurrencyLevel 计算得到Segment长度和段偏移量 segmentShift 和段掩码 segmentMask
1
segmentIndex = (hash >>> segmentShift) & segmentMask;
获取 Segment 的 ReentrantLock
计算 table 位置，插入 HashEntry
释放 Segment 锁

✅ 1.7 版问题

**每次 put() 需要锁整个 Segment**，粒度仍然较大。
**扩容时需要迁移整个 Segment**，仍然影响并发性能。

JDK 1.8：CAS + synchronized

✅ 1.8 版数据结构

ConcurrentHashMap
 ├── Node[] table  // 直接维护一个哈希表，代替 Segment
 │   ├── Node      // 链表节点
 │   ├── TreeNode  // 红黑树节点（当链表 > 8 时转红黑树）

✅ 1.8 版优化

移除了 Segment，直接使用 Node[] table
**写操作采用 CAS + synchronized**（减少锁粒度）
链表长度 >8 时，自动转换为红黑树（提高查询效率）

✅ 1.8 版 put 过程

计算 hash 值，确定数组索引
如果 table[index] == null，用 CAS 插入
如果 table[index] 非空，使用 synchronized 锁住 链表头节点
如果是链表，遍历并插入
如果链表长度 > 8，转换为红黑树

✅ 1.8 版扩容

采用 transfer() + synchronized 控制线程迁移数据，避免 Segment 级扩容的性能瓶颈。

JDK 1.7 vs JDK 1.8 对比

版本	数据结构	加锁机制	扩容方式	链表优化
JDK 1.7	`Segment[] + HashEntry[]`	分段锁（`ReentrantLock`）	Segment 级别扩容	❌ 无优化
JDK 1.8	`Node[]`	CAS + synchronized（头结点锁）	全局 `transfer()`，减少锁竞争	✅ 链表 → 红黑树

重点面试题 & 回答思路

❓1. ConcurrentHashMap 在 1.7 和 1.8 的区别？

✅ 回答要点：

JDK 1.7：
- 采用 **Segment[] + ReentrantLock**（分段锁）。
- **每个 Segment 维护自己的 table**，并独立加锁。
- **size() 计算需要遍历所有 Segment**，效率较低。
JDK 1.8：
- 移除了 Segment，采用 Node[] table 直接存储数据。
- 采用 CAS + synchronized 头节点锁，减少锁粒度，提高并发性能。
- 支持链表转红黑树（TreeNode），提高查询性能。

❓2. ConcurrentHashMap 的 put() 过程？

✅ 回答要点（JDK 1.8）

计算 hash 值
1
int hash = spread(key.hashCode());
确定数组索引
1
int index = (n - 1) & hash;

如果 table[index] == null，CAS 直接插入

1 2	if (casTabAt(tab, i, null, new Node<>(hash, key, value, null))) return;

如果 table[index] 非空

synchronized 锁住头结点
遍历链表，更新值或插入节点
如果链表长度 > 8，转换为红黑树

synchronized (f) {
    if (tabAt(tab, i) == f) { // 确保未被修改
        if (f instanceof TreeBin) {
            ((TreeBin<K, V>) f).putTreeVal(hash, key, value);
        } else {
            Node<K, V> p;
            if ((p = putVal(f, hash, key, value)) != null)
                oldVal = p.val;
        }
    }
}

❓3. ConcurrentHashMap 为什么线程安全？

✅ 回答要点

写操作
- CAS 直接插入，无锁操作。
- synchronized 锁住头结点，保证链表/红黑树插入安全。
扩容
- transfer() 迁移数据，防止并发冲突。
- 并发迁移时，使用 ForwardingNode 作为占位符，防止数据重复迁移。
读操作
- 大部分 get() 只读，不加锁。
- 链表结构遍历时不会修改数据，保证可见性。

❓4. ConcurrentHashMap 为什么比 HashTable 性能高？

✅ 回答要点

HashTable 使用 synchronized 锁住整个 Map，导致并发性能低。
ConcurrentHashMap 1.7 采用分段锁，1.8 采用 CAS + 头结点锁，提高并发能力。

总结

版本	数据结构	加锁机制	扩容优化	链表优化
JDK 1.7	`Segment[] + HashEntry[]`	分段锁（`ReentrantLock`）	Segment 级别扩容	❌ 无优化
JDK 1.8	`Node[]`	CAS + `synchronized`	全局 `transfer()`，减少锁竞争	✅ 链表 → 红黑树

1.7 采用 Segment 分段锁，锁粒度较大。
1.8 移除 Segment，采用 CAS + synchronized，并支持链表转红黑树，提高并发能力！

问：ConcurrentHashMap如何进行散列？⭐⭐

1.7版本：

ConcurrentHashMap会先在Segment分段时对获得的hashcode进行一次再散列，保证元素能均匀的分布在不同分段上，此阶段定位为 (hash >>> segmentShift) & segmentMask 。
在确定分段后，还会再一次散列，分配到不同的HashEntry中，此阶段定位为 hash & (tab.length - 1) 。两次散列方式不同，这样可以避免一次散列后得到的值过于雷同，导致第二次散列时聚集。

1.8版本：

通过获取键的哈希码，并将其高位右移异或 (h ^ (h >>> 16)) & HASH_BITS ，合并高低位特征，得到新的哈希码。
定位数组索引则通过 (tab.length - 1) & hash 。

1.7：两次散列
1. 第一次散列（分段索引）：ConcurrentHashMap在 Segment 分段时，对 key.hashCode() 进行一次再散列：
  1
  2
  3
  segmentShift = 32 - sshift;//计算得到段偏移量
  segmentMask = ssize - 1;//计算得到段掩码
  segmentIndex = (hash >>> segmentShift) & segmentMask;
  作用：保证 key 均匀分布到不同的 Segment，减少冲突。
2. 第二次散列（桶索引）：在 Segment 内部，再次计算 table 数组索引：
  1
  index = hash & (table.length - 1);
  作用：减少 Hash 冲突，避免过多链表或红黑树结构。
1.8：单次散列

JDK 1.8 取消了 Segment，采用单层 Node[] 结构，优化了哈希计算：
1
2
3
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
高 16 位与低 16 位异或，降低哈希冲突，提高分布均匀性。

定位到 table 的索引：
1
index = (n - 1) & hash;
作用：减少 Hash 冲突，避免哈希桶过度堆积。

问：ConcurrentHashMap如何获取元素？get()流程？⭐

✅ get() 查询流程：

计算 hash 值
1
int hash = spread(key.hashCode());
定位 Node[] table 的索引
1
int index = (n - 1) & hash;
找到桶的头节点，依次匹配：
- 如果首节点 key 匹配，直接返回。
- 如果是链表，遍历查找。
- 如果是红黑树，进行 TreeNode 查找。

//高位异或到低位，更多哈希冲突的场景用红黑树来优化，所以采用这种即方便又能解决问题的方案。
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

//获取指定下标在哈希表中的节点
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //把键的hashcode再散列得到h，合并高位低位特征，使散列更均匀
    int h = spread(key.hashCode());
    //散列表不为空，获取节点e，通过(tab.length - 1) & h与运算定位下标，判断对应下标是否已有元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //e不为空，且hash值等于h，再判断key是否相等，是则表示命中，直接返回对应的值
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //e的hash值不等于h，且为负数，表示此时结构为红黑树
        else if (eh < 0)
            //尝试遍历树查询key并返回
            return (p = e.find(h, key)) != null ? p.val : null;
        
        //e未命中，若还有后续节点，则遍历链表查询key并返回
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    //未能找到
    return null;
}

问：ConcurrentHashMap如何放置元素？put()流程？⭐

✅ put() 主要流程

计算 hash 值，进入死循环：
1
int hash = spread(key.hashCode());
**如果 table 为空，则初始化 table**。
计算 table 索引位置：
- 如果该位置为空，则 CAS 插入。
- 否则，进入 synchronized 锁定头节点，进行链表或红黑树插入。
链表长度 > 8，转换为红黑树。
如果 size() 超过阈值，触发扩容。

/*
 * Encodings for Node hash fields. 特殊的哈希值
 */
static final int MOVED     = -1; // hash for forwarding nodes 转移节点的hash
static final int TREEBIN   = -2; // hash for roots of trees 树根的hash
static final int RESERVED  = -3; // hash for transient reservations

public V put(K key, V value) {
    return putVal(key, value, false);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    //首先不允许新增空键或空值
    if (key == null || value == null) throw new NullPointerException();
    //把键的hashcode再散列得到h，合并高位低位特征，使散列更均匀
    int hash = spread(key.hashCode());
    //初始化binCount，用来记录修改的长度
    int binCount = 0;
    
    //死循环遍历Node数组，直到操作成功
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //判断若是首次执行putVal()，则调用initTable进行初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        //已有哈希表，并且hash对应下标节点还为null，此桶还未被使用，CAS新增节点
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //通过Unsafe的compareAndSwapObject尝试新增链表节点，完成任务跳出循环
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        //已有哈希表，首节点也已存在，但f处于MOVED状态表示此时正在扩容，则当前线程尝试帮助扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);//帮助扩容
        //已有哈希表，链表也已初始化，且节点不在移动状态，则加锁进行操作
        else {
            //oldVal用来记录旧值
            V oldVal = null;
            //代码块加锁同步f节点，根据链表或红黑树分别进行操作
            //链表则覆盖或尾插法新增节点
            //红黑树则调用API，返回对应节点（可能是新建节点），并覆盖
            synchronized (f) {
                //若f此时未被修改，则继续操作，否则跳过
                if (tabAt(tab, i) == f) {
                    
                    //1.首节点hash>=0，表示正常态，即链表节点
                    if (fh >= 0) {
                        //binCount记录为1，至少已有一个
                        binCount = 1;
                        //遍历此链表，直到完成操作显式终止循环，计算链表长度
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            //命中节点，覆盖value，完成操作后跳出循环
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                //记录oldVal，此时表示map中此键已对应有值
                                oldVal = e.val;
                                //当onlyIfAbsent为false时才进行覆盖
                                if (!onlyIfAbsent)
                                    e.val = value;
                                //跳出循环
                                break;
                            }
                            //当前节点还不是，e移到下个节点next
                            Node<K,V> pred = e;
                            //已遍历完链表，未找到则新增节点，尾插法，完成跳出循环
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    //2.非正常态，而是TreeBin节点，则向红黑树插入节点
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        //binCount更新为2
                        binCount = 2;
                        //插入树节点，完成操作
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            //同步块结束
            //binCount不为0表示put已对数据产生了影响，不管是否有覆盖
            if (binCount != 0) {
                //若达到链表阈值，就转此节点链表为红黑树
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);//转换红黑树
                //oldVal不为空，表示是一次更新操作，没有对元素个数产生影响，直接返回
                if (oldVal != null)
                    return oldVal;
                //否则元素个数已改变，跳出死循环，继续后续操作
                break;
            }
            //binCount还为0，put操作未成功，继续死循环
        }
    }
    //更新计数值，并继续判断是否需要扩容
    addCount(1L, binCount);
    return null;
}


/**
 * The default initial table capacity.  Must be a power of 2
 * (i.e., at least 1) and at most MAXIMUM_CAPACITY.
 */
private static final int DEFAULT_CAPACITY = 16;

/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    //当哈希表为空或长度为0时循环操作，否则直接返回
    while ((tab = table) == null || tab.length == 0) {
        //若sizeCtl<0，表示散列表正在初始化或扩容，正在被其他线程处理
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin 自旋等待
        //否则CAS更新sizeCtl为-1
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                //确认此时还未初始化
                if ((tab = table) == null || tab.length == 0) {
                    //初始化时sizeCtl可能会自定义，若未自定义则取默认值16
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    //新建节点数组，初始化table
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    //sizeCtl取和无符号右移2位后的差，即每隔n个4，就要减去n，也就是合理的取阈值0.75
                    sc = n - (n >>> 2);
                }
            } finally {
                //更新sizeCtl
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}


/**
 * A node inserted at head of bins during transfer operations.
 */
static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable;

    ......
}

问：ConcurrentHashMap如何统计数目？size()流程？⭐

无并发时只要用baseCount就足以，但一旦并发时CAS修改baseCount失败，就要启用counterCells，计算size时会将所有计数单元数组累加。

两种技术器都是通过 addCount() 来更新，但可能会因为并发而更新失败，会采用备用方法 fullAddCount()，死循环不断尝试。

✅ size() 统计方式

**如果计数单元数组 counterCells 为空，则直接返回 baseCount**。
**如果 counterCells 存在，则累加所有 counterCells 和 baseCount**。

final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

问：ConcurrentHashMap如何更新计数器？addCount()流程？

更新计数器流程分两部分：并发更新和扩容。

首先判断计数单元数组是否已创建，或尝试CAS对baseCount计数更新是否可以成功，二者皆为并发特征。
如果不满足，表示不需要进行并发更新，然后根据check参数是否>=0判断是否需要扩容检查，如果不需要则结束。
如果满足，则表示baseCount不可靠，需要更新计数单元数组。
若当前计数单元数组为空，或选定计数单元为空，或CAS更新计数单元失败，则调用备案fullAddCount，然后结束。
若非上述情况，则表示CAS更新成功，再判断所给check，若<=1表示还是链表，则直接返回，不进行扩容检查；若check>1，表示已是红黑树，需还要再算一下此时的size。
然后进入扩容流程，首先判断只有 check >= 0 才有必要扩容。
当此时size达到sizeCtl扩容阈值等，以此作为循环条件，则进行扩容循环，否则函数执行完毕。
通过哈希表长度获得一个resize标识，是一个低16位首位为1的大数，从而能在左移后变成一个负数。
判断 sizeCtl < 0 ，表示其他线程已经在扩容，然后根据五种特征判断扩容是否要结束，若满足即可跳出扩容循环。
若不满足特征，表示扩容还在继续，则尝试CAS原子操作 sizeCtl++ ，表示帮助线程+1，并执行扩容transfer。
若 sizeCtl >= 0 此时不在扩容，则尝试开启扩容流程，关键在于 (resize << 16) + 2 得到一个大的负数作为初始值，并CAS覆盖 sizeCtl ，后续每个线程都直接 sizeCtl++ ，成功后，执行扩容transfer。
等扩容执行完毕后，更新一下当前size，继续循环，直到扩容条件不满足。

问：ConcurrentHashMap的扩容方式？transfer()流程？⭐

1.7版本：concurrentHashMap是基于了segment的，segment内部维护了HashEntity数组，所以扩容是在这个基础上的，类比hashmap的扩容。

1.8版本：

扩容流程可以多线程协作提高速度，每个线程负责一块区域，要求至少16个桶。
扩容通过转移节点到新表来完成，新表初始化为旧表2倍大小。
因为要线程间协作，在某线程转移某下标链表后，会在旧表用一个转移节点替换表示已处理。
线程按分区一段一段倒序内循环，完成遍历后更新 sizeCtl-- ，表示参与转移线程数-1。
当线程要进行转移时，根据链表和红黑树有不同的实现，但思路是一样的，都保留哈希码不变的，转移哈希码变更的。
转移过程通过 synchronized 锁住同步资源-首节点。

✅ JDK 1.7 扩容

使用 ReentrantLock 加锁 Segment，然后扩容。

✅ JDK 1.8 扩容

采用 transfer() 迁移数据，支持多线程并发扩容。
标记 ForwardingNode 占位，防止重复迁移。

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    if ((stride = (n >>> 3) / NCPU) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // 每个线程负责的最小任务
    for (int i = 0; i < n; i += stride)
        transferStep(tab, nextTab, i, stride);
}

问：为什么说ConcurrentHashMap只具有弱一致性？

首先什么是数据弱一致性：

一致性常包含两类：数据一致性和事务一致性。导致数据一致性问题的原因是复制，弱一致性是相对于强一致性。强一致性的复制是同步的，弱一致性的复制是异步的。强一致性保证数据一定是一致的。

回到问题，并发容器具有弱一致性，主要是因为Java内存模型的 happens-before 原则。

现象是对于ConcurrentHashMap，当put一个元素后，并不一定能立刻get到此元素。对于 hb原则来说，就是put和get的 hb关系并非代码层面的顺序。即get操作运行到某行代码后，此时put操作还未完成，那么对于此get是无法感知到变化的。

ConcurrentHashMap能够保证每一次调用都是原子操作，但是并不保证多次调用之间也是原子操作。

所以Java API中声明的是保证get操作一定能看到已完成的put操作。

ConcurrentHashMap的弱一致性主要是为了提升效率，是一致性与效率之间的一种权衡。要成为强一致性，就得到处使用锁，甚至是全局锁，这就与Hashtable和同步的HashMap一样了。

问：ConcurrentHashMap和LinkedHashMap有什么区别？

LinkedHashMap的节点链表是双向，ConcurrentHashMap则是单向
ConcurrentHashMap是并发容器，LinkedHashMap则不能保证线程安全。

问：为什么ConcurrentHashMap中的链表转红黑树的阀值是8？

红黑树的占用空间是普通链表的两倍，如果哈希表的离散性足够好，各个节点的分布应该很均衡，所以很难会出现某个节点链表聚集的情况，但离散性较差时，就可能出现某个节点频繁哈希碰撞，所以根据概率统计得出随机哈希案例中桶达到8的概率很小仅为0.00000006，置换为红黑树就是为了防止糟糕的设计，使哈希表失去其效率，不如直接替换为红黑树来提升性能。

为什么树化阈值是8：

首先当散列均匀时，链表升级为红黑树的概率不大：理想情况下随机散列函数，概率分布遵循泊松分布，链表长度达到8的概率几乎为不可能。
当节点数量较少时，采用红黑树的意义不大，且因为红黑树节点的大小是普通链表节点大小的两倍，所以还会造成空间上的浪费。

4.3 ConcurrentSkipListMap

问：什么是ConcurrentSkipListMap？他和ConcurrentHashMap有什么区别？

ConcurrentSkipListMap是跳跃列表映射

ConcurrentHashMap
 ❌ Sorted
 ❌ Navigable
 ✅ Concurrent
ConcurrentSkipListMap
 ✅ Sorted
 ✅ Navigable
 ✅ Concurrent

ConcurrentSkipListMap是有序的，ConcurrentHashMap则非有序。
ConcurrentHashMap不能保证其操作的运行时间（散列结构因为重新散列的情况），允许对某些负载因子进行调整（大致是同时修改它的线程数）。ConcurrentSkipListMap则保证了各种操作的平均 O(log n) 性能，其本身是并发的，不支持为了并发性而进行的调优，而ConcurrentHashMap则可以进行并发调优。
ConcurrentSkipListMap还有许多ConcurrentHashMap没有的操作：ceilingEntry/Key 、floorEntry/Key 等。

因为要维护一个排序顺序，相比ConcurrentHashMap，它的 get/put/contains 操作要慢，但它支持SortedMap，NavigableMap，ConcurrentNavigableMap等接口。如果使用ConcurrentHashMap得到一个顺序映射，则必须计算排序顺序（费用很高）。

通常情况下，如果需要快速添加单个键/值对和快速查找单个键，最好使用HashMap。如果需要更快的顺序遍历，并且能够负担额外的插入成本，可以使用SkipListMap。

ConcurrentSkipListMap通过随机数来保持平衡。

4.4 LinkedHashMap

问：LinkedHashMap用过吗？讲一下？存进集合如何比较大小保证顺序？

答：用过，LinkedHashMap会在每次访问元素后把元素放置到节点链表的尾部，也就记录了链表的访问顺序，可以用来实现LRU。

重写removeEldestEntry方法，使其判断当此时链表达到限制地阈值大小时，返回true，这样put方法被调用时会自动删除最老元素即此时链表的首节点。

LinkedHashMap是HashMap的一种特殊分支，是某种有序的hashMap，和TreeMap是不一样的概念，是用了HashMap+链表的方式来构造的，有两者有序模式：访问有序，插入顺序，插入顺序是一直存在的，因为是调用了hashMap的put方法，并没有重载，但是重载了newNode方法，在这个方法中，会把节点插入链表中，访问有序默认是关闭的，如果打开，则在每次get的时候都会把链表的节点移除掉，放到链表的最后面。这样子就是一个LRU的一种实现方式。

4.5 TreeMap

问：讲讲TreeMap？

TreeMap是Map中的一种很特殊的map，我们知道Map基本是无序的，但是TreeMap是会自动进行排序的，也就是一个有序Map(使用了红黑树来实现），如果设置了Comparator比较器，则会根据比较器来对比两者的大小，如果没有则key需要是Comparable的子类（代码中没有事先check，会直接抛出转化异常，有点坑啊）。
树映射TreeMap，由红黑树实现的有序映射。TreeMap为增、删、改、查这些操作提供了 O(log n) 的时间开销，相比HashMap的 O(1) 存储效率要差些，但查询统计的 O(log n) 比HashMap O(n) 要高效。

Java提高十六：TreeMap深入分析

问：TreeMap查询写入的时间复杂度多少？

TreeMap为增、删、改、查这些操作提供了log(N)的时间开销。

Java集合

第一节 综合

问：java的集合框架有哪几种？

问：平常用到哪些集合类？

问：集合迭代器的原理？

问：快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

问：了解了哪些并发安全集合，从list到map都讲一下？

问：List，Map，Set 接口在存取元素时，各有什么特点？

问：接口RandomAccess的作用？

第二节 List

问：List你使用过哪些？

问：你知道vector和ArrayList和linkedList的区别嘛？扩容机制等？

问：ArrayList的实现？怎么扩容？怎么插入？怎么删除？在遍历ArrayList时，删除元素会发生什么？LinkedList呢？

问：ArrayList和LinkedList区别？使用场景？链表和数组的优缺点？

问：讲一下写时复制？写时复制和读写锁的区别？

问：CopyOnWriteArrayList 原理？

问：ArrayBlockingQueue 和 LinkedBlockingQueue 区别？

第三节 Set

问：HashSet 和 TreeSet 原理？

第四节 Map

4.1 HashMap

**问：说说你了解的HashMap吧？能讲讲HashMap的实现原理吗？HashMap的底层是什么？HashMap内部数据结构？1.8版本的优化 **⭐⭐⭐

问：解决hash冲突的方法有哪些？⭐⭐

问：hashmap查询的时间复杂度能达到O(1)是什么实现的？里面的索引是怎么计算的？⭐

问：HashMap什么时候会进行rehash？⭐

问：HashMap的初始容量设置成多少比较合适呢？

问：HashMap为什么不是线程安全的？怎么让HashMap变得线程安全？HashMap多线程有什么问题？怎么解决？⭐

问：结合源码说说HashMap在高并发场景中为什么会出现死循环？

问：HashMap 扩容机制，为什么都是 2 的 N 次幂？⭐⭐

问：为什么HashMap装填因子是0.75？⭐

问：HashMap和HashTable和ConcurrentHashMap的区别？

问：HashMap和HashTable有何不同？

问：HashMap 和 WeakHashMap 的区别？

问：HashMap 和 ConcurrentHashMap 的区别？在 hash 上的区别？

问：HashMap 1.8版本前后的区别？JDK8 做了什么优化？最小树化容量？比如为什么是红黑树，别的树不可以吗；为什么 8 的时候树化，4 不可以吗？⭐⭐

问：jdk1.8中，对HashMap和ConcurrentHashMap做了哪些优化？

4.2 ConcurrentHashMap

问：讲一下你所知道的ConcurrentHashMap？ConcurrentHashMap分段锁？如何分段？1.7与1.8版本的区别？⭐⭐⭐

问：ConcurrentHashMap如何进行散列？⭐⭐

问：ConcurrentHashMap如何获取元素？get()流程？⭐

问：ConcurrentHashMap如何放置元素？put()流程？⭐

问：ConcurrentHashMap如何统计数目？size()流程？⭐

问：ConcurrentHashMap如何更新计数器？addCount()流程？

问：ConcurrentHashMap的扩容方式？transfer()流程？⭐

问：为什么说ConcurrentHashMap只具有弱一致性？

问：ConcurrentHashMap和LinkedHashMap有什么区别？

问：为什么ConcurrentHashMap中的链表转红黑树的阀值是8？

4.3 ConcurrentSkipListMap

问：什么是ConcurrentSkipListMap？他和ConcurrentHashMap有什么区别？

4.4 LinkedHashMap

问：LinkedHashMap用过吗？讲一下？存进集合如何比较大小保证顺序？

4.5 TreeMap

问：讲讲TreeMap？

问：TreeMap查询写入的时间复杂度多少？

第一节综合

问：说说你了解的HashMap吧？能讲讲HashMap的实现原理吗？HashMap的底层是什么？HashMap内部数据结构？1.8版本的优化 ⭐⭐⭐