Java 集合面试题集

总题数: 26道 | 重点领域: List、Map、Set、并发容器 | 难度分布: 中级

本文档整理了 Java 集合的完整26道面试题目，涵盖集合框架、数据结构、性能特点等各个方面。

---

面试题目列表

1. 说说 Java 中 HashMap 的原理？

答案：

HashMap是基于哈希表实现的键值对存储结构。

核心原理：

1. 数据结构（JDK 1.8+）

1数组 + 链表 + 红黑树
2
3数组：Node<K,V>[] table
4链表：解决哈希冲突
5红黑树：链表长度>8且数组长度>=64时转换

2. 存储过程

java

1public V put(K key, V value) {
2    // 1. 计算hash值
3    int hash = hash(key);
4    
5    // 2. 计算数组下标：(n-1) & hash
6    int index = (table.length - 1) & hash;
7    
8    // 3. 如果没有冲突，直接放入
9    if (table[index] == null) {
10        table[index] = new Node(hash, key, value, null);
11    }
12    // 4. 如果有冲突，遍历链表/红黑树
13    else {
14        // 链表处理或红黑树处理
15    }
16    
17    // 5. 判断是否需要扩容
18    if (++size > threshold) {
19        resize();
20    }
21}

3. 查找过程

java

1public V get(Object key) {
2    // 1. 计算hash
3    int hash = hash(key);
4    
5    // 2. 定位数组位置
6    Node<K,V> first = table[(table.length - 1) & hash];
7    
8    // 3. 遍历链表/红黑树查找
9    if (first != null) {
10        if (first.hash == hash && key.equals(first.key)) {
11            return first.value;
12        }
13        // 继续查找...
14    }
15    return null;
16}

4. 关键参数

• 默认初始容量：16
• 默认负载因子：0.75
• 扩容阈值：capacity * loadFactor
• 树化阈值：8（链表转红黑树）
• 退化阈值：6（红黑树转链表）

2. 使用 HashMap 时，有哪些提升性能的技巧？

答案：

1. 设置合适的初始容量

java

1// 不好：默认容量16，需要多次扩容
2Map<String, String> map = new HashMap<>();
3
4// 好：预估大小，减少扩容
5Map<String, String> map = new HashMap<>(1024);
6
7// 更好：考虑负载因子
8int expectedSize = 1000;
9Map<String, String> map = new HashMap<>((int)(expectedSize / 0.75) + 1);

2. 选择好的hash算法

java

1// 重写hashCode方法，减少冲突
2@Override
3public int hashCode() {
4    return Objects.hash(field1, field2, field3);
5}

3. 使用不可变对象作key

java

1// 推荐：使用String、Integer等不可变类
2Map<String, User> map = new HashMap<>();
3
4// 不推荐：使用可变对象
5Map<MutableKey, User> map = new HashMap<>();

4. 避免在遍历时修改

java

1// 错误：导致ConcurrentModificationException
2for (String key : map.keySet()) {
3    map.remove(key);
4}
5
6// 正确：使用迭代器
7Iterator<String> it = map.keySet().iterator();
8while (it.hasNext()) {
9    it.next();
10    it.remove();
11}

5. 并发场景使用ConcurrentHashMap

java

1// 多线程环境
2Map<String, String> map = new ConcurrentHashMap<>();

3. 什么是 Hash 碰撞？怎么解决哈希碰撞？

答案：

Hash碰撞定义： 不同的key经过hash计算后得到相同的数组下标。

解决方法：

1. 链地址法（HashMap采用）

java

1// 数组 + 链表
2class Node<K,V> {
3    final int hash;
4    final K key;
5    V value;
6    Node<K,V> next;  // 指向下一个节点
7}
8
9// 碰撞后形成链表
10[数组] -> [Node1] -> [Node2] -> [Node3]

2. 开放定址法

1线性探测：依次查找下一个空位置
2index = (hash + i) % capacity
3
4二次探测：使用二次hash函数
5index = (hash1 + i * hash2) % capacity

3. 再哈希法

1使用多个hash函数，直到找到空位置

4. 建立公共溢出区

1所有碰撞的元素放入一个公共区域

HashMap的优化：

java

1// JDK 1.8优化：链表 -> 红黑树
2if (链表长度 > 8 && 数组长度 >= 64) {
3    转换为红黑树;  // O(n) -> O(log n)
4}
5
6if (红黑树节点 < 6) {
7    转换为链表;
8}

4. Java 的 CopyOnWriteArrayList 和 Collections.synchronizedList 有什么区别？分别有什么优缺点？

答案：

实现机制对比：

特性	CopyOnWriteArrayList	synchronizedList
同步机制	写时复制	synchronized锁
读操作	无锁	需要加锁
写操作	复制整个数组	加锁
迭代器	快照，不会抛异常	需要手动同步
适用场景	读多写少	读写均衡

CopyOnWriteArrayList：

java

1public class CopyOnWriteArrayList<E> {
2    private volatile Object[] array;
3    
4    // 读操作：无锁
5    public E get(int index) {
6        return (E) array[index];
7    }
8    
9    // 写操作：复制数组
10    public boolean add(E e) {
11        synchronized (lock) {
12            Object[] newArray = Arrays.copyOf(array, array.length + 1);
13            newArray[array.length] = e;
14            array = newArray;  // 原子替换
15        }
16        return true;
17    }
18    
19    // 迭代器：使用快照
20    public Iterator<E> iterator() {
21        return new COWIterator<>(array, 0);
22    }
23}
24
25// 优点：
26// 1. 读操作完全无锁，性能高
27// 2. 迭代器不会ConcurrentModificationException
28
29// 缺点：
30// 1. 写操作开销大（复制整个数组）
31// 2. 内存占用高
32// 3. 数据一致性问题（读到的可能是旧数据）

Collections.synchronizedList：

java

1public static <T> List<T> synchronizedList(List<T> list) {
2    return new SynchronizedList<>(list);
3}
4
5static class SynchronizedList<E> {
6    final Object mutex;  // 锁对象
7    
8    // 所有操作都加锁
9    public E get(int index) {
10        synchronized (mutex) {
11            return list.get(index);
12        }
13    }
14    
15    public boolean add(E e) {
16        synchronized (mutex) {
17            return list.add(e);
18        }
19    }
20    
21    // 迭代器需要手动同步
22    public Iterator<E> iterator() {
23        return list.iterator();  // 不安全！
24    }
25}
26
27// 优点：
28// 1. 内存开销小
29// 2. 实时性好
30
31// 缺点：
32// 1. 读写都需要加锁，性能低
33// 2. 迭代器需要手动同步

使用建议：

java

1// 读多写少：使用CopyOnWriteArrayList
2List<String> list = new CopyOnWriteArrayList<>();
3
4// 读写均衡：使用synchronizedList
5List<String> list = Collections.synchronizedList(new ArrayList<>());

5. Java 中有哪些集合类？请简单介绍

答案：

Java集合框架体系：

1Collection
2├── List（有序，可重复）
3│   ├── ArrayList：动态数组
4│   ├── LinkedList：双向链表
5│   ├── Vector：线程安全的ArrayList
6│   └── CopyOnWriteArrayList：写时复制
7│
8├── Set（无序，不重复）
9│   ├── HashSet：基于HashMap
10│   ├── LinkedHashSet：有序的HashSet
11│   ├── TreeSet：红黑树，有序
12│   └── CopyOnWriteArraySet：写时复制
13│
14└── Queue（队列）
15    ├── PriorityQueue：优先级队列
16    ├── ArrayDeque：双端队列
17    ├── LinkedList：也实现了Deque
18    └── BlockingQueue：阻塞队列
19        ├── ArrayBlockingQueue
20        ├── LinkedBlockingQueue
21        └── PriorityBlockingQueue
22
23Map（键值对）
24├── HashMap：哈希表
25├── LinkedHashMap：有序的HashMap
26├── TreeMap：红黑树，有序
27├── Hashtable：线程安全，过时
28├── ConcurrentHashMap：并发HashMap
29├── WeakHashMap：弱引用
30└── IdentityHashMap：比较引用

常用集合特点：

集合	底层结构	线程安全	有序性	允许null
ArrayList	数组	否	有序	是
LinkedList	链表	否	有序	是
Vector	数组	是	有序	是
HashSet	HashMap	否	无序	是
TreeSet	红黑树	否	有序	否
HashMap	数组+链表+红黑树	否	无序	是
TreeMap	红黑树	否	有序	否
ConcurrentHashMap	数组+链表+红黑树	是	无序	否

6. Java 数组和链表在 Java 中的区别是什么？

答案：

特性	数组	链表
存储方式	连续内存	离散内存
随机访问	O(1)	O(n)
插入/删除	O(n)	O(1)
内存开销	固定	额外指针
缓存友好	好	差
大小	固定	动态

数组：

java

1// 优点：
2// 1. 随机访问快：O(1)
3// 2. 内存连续，缓存命中率高
4// 3. 空间利用率高
5
6int[] arr = new int[10];
7int value = arr[5];  // O(1)
8
9// 缺点：
10// 1. 大小固定，不能动态扩展
11// 2. 插入/删除需要移动元素：O(n)
12// 3. 内存分配需要连续空间

链表：

java

1// 优点：
2// 1. 动态大小，灵活扩展
3// 2. 插入/删除快：O(1)
4// 3. 不需要连续内存
5
6class Node {
7    int data;
8    Node next;
9}
10
11// 缺点：
12// 1. 随机访问慢：O(n)
13// 2. 额外的指针开销
14// 3. 缓存命中率低

使用场景：

java

1// 需要频繁随机访问：使用数组
2ArrayList<String> list = new ArrayList<>();
3
4// 需要频繁插入/删除：使用链表
5LinkedList<String> list = new LinkedList<>();

7. Java 中的 List 接口有哪些实现类？

答案：

常用实现类：

1. ArrayList

java

1// 基于动态数组
2public class ArrayList<E> {
3    private Object[] elementData;
4    private int size;
5}
6
7// 特点：
8// - 随机访问快：O(1)
9// - 尾部插入快：O(1)
10// - 中间插入/删除慢：O(n)
11// - 线程不安全

2. LinkedList

java

1// 基于双向链表
2public class LinkedList<E> {
3    private Node<E> first;
4    private Node<E> last;
5    private int size;
6}
7
8// 特点：
9// - 随机访问慢：O(n)
10// - 头尾插入/删除快：O(1)
11// - 实现了Deque接口
12// - 线程不安全

3. Vector

java

1// 线程安全的ArrayList
2public class Vector<E> {
3    protected Object[] elementData;
4    
5    // 所有方法都加synchronized
6    public synchronized boolean add(E e) {
7        // ...
8    }
9}
10
11// 特点：
12// - 线程安全
13// - 性能低（已过时）
14// - 默认扩容2倍

4. CopyOnWriteArrayList

java

1// 写时复制
2public class CopyOnWriteArrayList<E> {
3    private volatile Object[] array;
4    
5    public boolean add(E e) {
6        synchronized (lock) {
7            Object[] newArray = Arrays.copyOf(array, len + 1);
8            newArray[len] = e;
9            array = newArray;
10        }
11    }
12}
13
14// 特点：
15// - 读操作无锁
16// - 写操作复制数组
17// - 适合读多写少

对比总结：

实现类	底层结构	线程安全	适用场景
ArrayList	数组	否	随机访问多
LinkedList	链表	否	插入/删除多
Vector	数组	是	已过时
CopyOnWriteArrayList	数组	是	读多写少

8. Java 中 ArrayList 和 LinkedList 有什么区别？

答案：

核心区别：

特性	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1)	O(1)
中间插入	O(n)	O(n)
内存开销	较小	较大（指针）
缓存友好	好	差

ArrayList：

java

1public class ArrayList<E> {
2    private Object[] elementData;
3    private int size;
4    
5    // 随机访问：O(1)
6    public E get(int index) {
7        return (E) elementData[index];
8    }
9    
10    // 尾部添加：O(1)
11    public boolean add(E e) {
12        elementData[size++] = e;
13        return true;
14    }
15    
16    // 中间插入：O(n)
17    public void add(int index, E element) {
18        System.arraycopy(elementData, index, 
19                        elementData, index + 1, size - index);
20        elementData[index] = element;
21    }
22}
23
24// 优点：
25// 1. 支持快速随机访问
26// 2. 内存连续，缓存命中率高
27// 3. 尾部操作效率高
28
29// 缺点：
30// 1. 中间插入/删除需要移动元素
31// 2. 扩容有开销

LinkedList：

java

1public class LinkedList<E> {
2    private Node<E> first;
3    private Node<E> last;
4    private int size;
5    
6    private static class Node<E> {
7        E item;
8        Node<E> next;
9        Node<E> prev;
10    }
11    
12    // 随机访问：O(n)
13    public E get(int index) {
14        Node<E> node = first;
15        for (int i = 0; i < index; i++) {
16            node = node.next;
17        }
18        return node.item;
19    }
20    
21    // 头部添加：O(1)
22    public void addFirst(E e) {
23        Node<E> newNode = new Node<>(e, first, null);
24        first = newNode;
25    }
26}
27
28// 优点：
29// 1. 头尾插入/删除快
30// 2. 不需要扩容
31// 3. 实现了Deque接口
32
33// 缺点：
34// 1. 随机访问慢
35// 2. 额外的指针开销
36// 3. 缓存不友好

选择建议：

java

1// 需要频繁随机访问：使用ArrayList
2List<String> list = new ArrayList<>();
3String item = list.get(100);  // 快
4
5// 需要频繁头尾插入/删除：使用LinkedList
6Deque<String> deque = new LinkedList<>();
7deque.addFirst("first");  // 快
8deque.addLast("last");    // 快
9
10// 大多数情况：优先选择ArrayList

9. Java ArrayList 的扩容机制是什么？

答案：

扩容触发条件： 当元素数量超过当前数组容量时触发扩容。

扩容过程：

java

1public class ArrayList<E> {
2    private Object[] elementData;
3    private int size;
4    
5    public boolean add(E e) {
6        // 1. 检查是否需要扩容
7        ensureCapacityInternal(size + 1);
8        
9        // 2. 添加元素
10        elementData[size++] = e;
11        return true;
12    }
13    
14    private void ensureCapacityInternal(int minCapacity) {
15        if (minCapacity > elementData.length) {
16            grow(minCapacity);
17        }
18    }
19    
20    private void grow(int minCapacity) {
21        int oldCapacity = elementData.length;
22        
23        // 3. 新容量 = 旧容量 * 1.5
24        int newCapacity = oldCapacity + (oldCapacity >> 1);
25        
26        // 4. 如果还不够，直接使用最小需求
27        if (newCapacity < minCapacity) {
28            newCapacity = minCapacity;
29        }
30        
31        // 5. 复制数组
32        elementData = Arrays.copyOf(elementData, newCapacity);
33    }
34}

扩容特点：

1. 扩容倍数：1.5倍

java

1// JDK 1.8
2newCapacity = oldCapacity + (oldCapacity >> 1);
3
4// 示例：
510 -> 15 -> 22 -> 33 -> 49 -> 73...

2. 初始容量

java

1// 默认容量：10
2private static final int DEFAULT_CAPACITY = 10;
3
4// 第一次add时才初始化（延迟初始化）
5ArrayList<String> list = new ArrayList<>();  // 此时容量为0
6list.add("first");  // 此时扩容为10

3. 扩容开销

java

1// 每次扩容都需要：
2// 1. 分配新数组
3// 2. 复制旧数据
4// 3. 替换引用
5
6// 时间复杂度：O(n)

优化建议：

java

1// 不好：频繁扩容
2ArrayList<String> list = new ArrayList<>();
3for (int i = 0; i < 10000; i++) {
4    list.add("item" + i);  // 多次扩容
5}
6
7// 好：预估容量
8ArrayList<String> list = new ArrayList<>(10000);
9for (int i = 0; i < 10000; i++) {
10    list.add("item" + i);  // 不需要扩容
11}
12
13// 更好：考虑负载因子
14int expectedSize = 10000;
15ArrayList<String> list = new ArrayList<>((int)(expectedSize / 0.75) + 1);

10. Java 中的 HashMap 和 Hashtable 有什么区别？

答案：

主要区别：

特性	HashMap	Hashtable
线程安全	否	是
性能	高	低
null键	允许	不允许
null值	允许	不允许
初始容量	16	11
扩容倍数	2倍	2倍+1
迭代器	fail-fast	Enumeration
JDK版本	1.2	1.0
推荐使用	是	否（已过时）

HashMap：

java

1public class HashMap<K,V> {
2    // 非线程安全
3    public V put(K key, V value) {
4        // 允许null键和null值
5        if (key == null) {
6            return putForNullKey(value);
7        }
8        // ...
9    }
10    
11    public V get(Object key) {
12        if (key == null) {
13            return getForNullKey();
14        }
15        // ...
16    }
17}
18
19// 特点：
20// 1. 非线程安全，性能高
21// 2. 允许null键和null值
22// 3. JDK 1.8引入红黑树优化

Hashtable：

java

1public class Hashtable<K,V> {
2    // 所有方法都加synchronized
3    public synchronized V put(K key, V value) {
4        // 不允许null
5        if (value == null) {
6            throw new NullPointerException();
7        }
8        // ...
9    }
10    
11    public synchronized V get(Object key) {
12        // ...
13    }
14}
15
16// 特点：
17// 1. 线程安全，但性能低
18// 2. 不允许null键和null值
19// 3. 已过时，不推荐使用

代码对比：

java

1// HashMap：允许null
2Map<String, String> hashMap = new HashMap<>();
3hashMap.put(null, "value");   // OK
4hashMap.put("key", null);     // OK
5
6// Hashtable：不允许null
7Map<String, String> hashtable = new Hashtable<>();
8hashtable.put(null, "value"); // NullPointerException
9hashtable.put("key", null);   // NullPointerException

替代方案：

java

1// 单线程：使用HashMap
2Map<String, String> map = new HashMap<>();
3
4// 多线程：使用ConcurrentHashMap
5Map<String, String> map = new ConcurrentHashMap<>();
6
7// 或者使用Collections.synchronizedMap
8Map<String, String> map = Collections.synchronizedMap(new HashMap<>());

11. Java ConcurrentHashMap 和 Hashtable 的区别是什么？

答案：

核心区别：

特性	ConcurrentHashMap	Hashtable
锁机制	分段锁/CAS	全表锁
并发度	高	低
性能	高	低
null键值	不允许	不允许
迭代器	弱一致性	强一致性
JDK版本	1.5	1.0

ConcurrentHashMap（JDK 1.8）：

java

1// 使用CAS + synchronized实现
2public class ConcurrentHashMap<K,V> {
3    // put操作：只锁定单个桶
4    public V put(K key, V value) {
5        int hash = spread(key.hashCode());
6        for (Node<K,V>[] tab = table;;) {
7            Node<K,V> f = tabAt(tab, i);
8            if (f == null) {
9                // CAS插入
10                if (casTabAt(tab, i, null, new Node<>(hash, key, value)))
11                    break;
12            } else {
13                // synchronized锁定单个桶
14                synchronized (f) {
15                    // 插入逻辑
16                }
17            }
18        }
19    }
20}
21
22// 优点：
23// 1. 细粒度锁，并发性能高
24// 2. 读操作无锁
25// 3. 支持高并发

Hashtable：

java

1// 所有方法都用synchronized
2public class Hashtable<K,V> {
3    public synchronized V put(K key, V value) {
4        // 锁定整个表
5    }
6    
7    public synchronized V get(Object key) {
8        // 锁定整个表
9    }
10}
11
12// 缺点：
13// 1. 粗粒度锁，性能低
14// 2. 读写都需要加锁
15// 3. 已过时

12. Java 中的 HashSet 和 HashMap 有什么区别？

答案：

核心关系：HashSet底层就是HashMap

java

1public class HashSet<E> {
2    private HashMap<E, Object> map;
3    private static final Object PRESENT = new Object();
4    
5    public boolean add(E e) {
6        return map.put(e, PRESENT) == null;
7    }
8    
9    public boolean contains(Object o) {
10        return map.containsKey(o);
11    }
12}

主要区别：

特性	HashSet	HashMap
接口	Set	Map
存储	只存储对象	存储键值对
添加方法	add(E e)	put(K key, V value)
允许null	一个null	一个null键，多个null值
底层实现	HashMap	数组+链表+红黑树

使用场景：

java

1// HashSet：去重、判断存在
2Set<String> set = new HashSet<>();
3set.add("apple");
4boolean exists = set.contains("apple");
5
6// HashMap：键值映射
7Map<String, Integer> map = new HashMap<>();
8map.put("apple", 100);
9Integer price = map.get("apple");

13. Java 中 HashMap 的扩容机制是怎样的？

答案：

扩容时机： 当元素数量 > 容量 * 负载因子时触发扩容。

扩容过程：

java

1final Node<K,V>[] resize() {
2    Node<K,V>[] oldTab = table;
3    int oldCap = oldTab.length;
4    
5    // 1. 计算新容量：2倍
6    int newCap = oldCap << 1;
7    
8    // 2. 创建新数组
9    Node<K,V>[] newTab = new Node[newCap];
10    
11    // 3. 重新hash所有元素
12    for (int j = 0; j < oldCap; ++j) {
13        Node<K,V> e = oldTab[j];
14        if (e != null) {
15            if (e.next == null) {
16                // 单个节点：直接放入新位置
17                newTab[e.hash & (newCap - 1)] = e;
18            } else {
19                // 链表/红黑树：拆分重新分配
20                // 元素要么在原位置，要么在原位置+oldCap
21            }
22        }
23    }
24    return newTab;
25}

关键点：

1. 容量翻倍：newCap = oldCap * 2
2. 重新计算位置：index = hash & (newCap - 1)
3. 优化：元素位置只有两种可能
   • 保持原位置
   • 原位置 + oldCap

14. Java 为什么 HashMap 在扩容时采用 2 的 n 次方倍？

答案：

原因1：高效的位运算

java

1// 计算数组下标
2// 方式1：取模运算（慢）
3index = hash % capacity;
4
5// 方式2：位运算（快）
6index = hash & (capacity - 1);
7
8// 当capacity是2的n次方时，两种方式等价
9// 例如：capacity = 16 = 2^4
10// capacity - 1 = 15 = 0b1111
11// hash & 15 等价于 hash % 16

原因2：扩容时元素分布均匀

java

1// 扩容前：capacity = 16，index = hash & 15
2// 扩容后：capacity = 32，index = hash & 31
3
4// 元素新位置只有两种可能：
5// 1. 保持原位置（hash的第5位为0）
6// 2. 原位置+16（hash的第5位为1）
7
8// 示例：
9hash = 0b10101  // 21
10旧位置 = 21 & 15 = 0b01111 & 0b10101 = 5
11新位置 = 21 & 31 = 0b11111 & 0b10101 = 21
12// 新位置 = 旧位置 + 16

原因3：减少hash冲突

java

1// 2的n次方-1的二进制全是1
216 - 1 = 15 = 0b1111
332 - 1 = 31 = 0b11111
4
5// 与运算时保留更多hash信息
6// 减少冲突概率

15. Java 为什么 HashMap 的默认负载因子是 0.75？

答案：

负载因子定义：

java

1loadFactor = 元素数量 / 数组容量
2threshold = capacity * loadFactor  // 扩容阈值

0.75的权衡：

1. 空间与时间的平衡

1loadFactor = 0.5：
2- 空间利用率低（50%）
3- 冲突少，查询快
4
5loadFactor = 1.0：
6- 空间利用率高（100%）
7- 冲突多，查询慢
8
9loadFactor = 0.75：
10- 空间利用率适中（75%）
11- 冲突适中，性能较好

2. 泊松分布

1根据统计学，当loadFactor=0.75时：
2- 单个桶中元素个数超过8的概率小于千万分之一
3- 这是红黑树转换阈值的理论依据

3. 实际测试结果

java

1// JDK注释说明：
2// 0.75在时间和空间成本之间提供了良好的权衡
3// 更高的值会减少空间开销但增加查找成本
4// 更低的值会增加空间开销但减少查找成本

16. Java 为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？

答案：

改动原因：解决链表过长导致的性能问题

JDK 1.7问题：

java

1// 链表结构
2数组[index] -> Node1 -> Node2 -> ... -> NodeN
3
4// 查找时间复杂度：O(n)
5// 当链表很长时，性能退化严重

JDK 1.8优化：

java

1// 当链表长度>8且数组长度>=64时，转为红黑树
2if (binCount >= TREEIFY_THRESHOLD - 1) {
3    treeifyBin(tab, hash);
4}
5
6// 红黑树查找：O(log n)
7// 性能提升明显

转换条件：

java

1// 链表 -> 红黑树
21. 链表长度 > 8
32. 数组长度 >= 64
4
5// 红黑树 -> 链表
61. 节点数 <= 6

为什么是8和6？

1- 8：根据泊松分布，链表长度达到8的概率极低
2- 6：避免频繁转换（如果用7，可能反复转换）

17. Java JDK 1.8 对 HashMap 除了红黑树还进行了哪些改动？

答案：

主要改动：

1. 数据结构变化

java

1// JDK 1.7：数组 + 链表
2Entry<K,V>[] table;
3
4// JDK 1.8：数组 + 链表 + 红黑树
5Node<K,V>[] table;

2. 插入方式改变

java

1// JDK 1.7：头插法
2void addEntry(int hash, K key, V value, int bucketIndex) {
3    Entry<K,V> e = table[bucketIndex];
4    table[bucketIndex] = new Entry<>(hash, key, value, e);
5}
6// 问题：并发扩容时可能形成环形链表
7
8// JDK 1.8：尾插法
9// 避免了环形链表问题

3. 扩容优化

java

1// JDK 1.7：重新计算所有元素的hash
2for (Entry<K,V> e : table) {
3    int index = indexFor(e.hash, newCapacity);
4}
5
6// JDK 1.8：元素位置只有两种可能
7// 原位置 或 原位置+oldCap
8// 不需要重新计算hash

4. hash算法优化

java

1// JDK 1.7
2int hash = hash(key);
3int index = indexFor(hash, table.length);
4
5// JDK 1.8：扰动函数简化
6static final int hash(Object key) {
7    int h;
8    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
9}

18. Java 中的 LinkedHashMap 是什么？

答案：

LinkedHashMap是HashMap的子类，维护了插入顺序或访问顺序。

实现原理：

java

1public class LinkedHashMap<K,V> extends HashMap<K,V> {
2    // 双向链表头尾节点
3    transient LinkedHashMap.Entry<K,V> head;
4    transient LinkedHashMap.Entry<K,V> tail;
5    
6    // 排序模式：true=访问顺序，false=插入顺序
7    final boolean accessOrder;
8    
9    static class Entry<K,V> extends HashMap.Node<K,V> {
10        Entry<K,V> before, after;  // 双向链表指针
11    }
12}

使用示例：

java

1// 1. 插入顺序（默认）
2Map<String, Integer> map = new LinkedHashMap<>();
3map.put("a", 1);
4map.put("c", 3);
5map.put("b", 2);
6// 遍历顺序：a, c, b
7
8// 2. 访问顺序（LRU缓存）
9Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
10lru.put("a", 1);
11lru.put("b", 2);
12lru.get("a");  // a被访问，移到末尾
13// 遍历顺序：b, a
14
15// 3. 实现LRU缓存
16class LRUCache<K, V> extends LinkedHashMap<K, V> {
17    private int capacity;
18    
19    public LRUCache(int capacity) {
20        super(capacity, 0.75f, true);
21        this.capacity = capacity;
22    }
23    
24    @Override
25    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
26        return size() > capacity;
27    }
28}

19. Java 中的 TreeMap 是什么？

答案：

TreeMap是基于红黑树实现的有序Map。

核心特点：

java

1public class TreeMap<K,V> extends AbstractMap<K,V> {
2    private transient Entry<K,V> root;  // 红黑树根节点
3    private final Comparator<? super K> comparator;
4    
5    static final class Entry<K,V> {
6        K key;
7        V value;
8        Entry<K,V> left;
9        Entry<K,V> right;
10        Entry<K,V> parent;
11        boolean color = BLACK;
12    }
13}

特性：

1. 有序：按key自然顺序或自定义顺序
2. 时间复杂度：O(log n)
3. 不允许null key
4. 非线程安全

使用示例：

java

1// 1. 自然顺序
2TreeMap<Integer, String> map = new TreeMap<>();
3map.put(3, "three");
4map.put(1, "one");
5map.put(2, "two");
6// 遍历顺序：1, 2, 3
7
8// 2. 自定义排序
9TreeMap<String, Integer> map = new TreeMap<>(
10    (a, b) -> b.compareTo(a)  // 降序
11);
12
13// 3. 范围查询
14map.subMap(1, 5);      // [1, 5)
15map.headMap(3);        // < 3
16map.tailMap(3);        // >= 3
17map.firstKey();        // 最小key
18map.lastKey();         // 最大key

20. Java 中的 IdentityHashMap 是什么？

答案：

IdentityHashMap使用==而不是equals()比较key。

与HashMap的区别：

java

1// HashMap：使用equals()
2Map<String, Integer> hashMap = new HashMap<>();
3String s1 = new String("key");
4String s2 = new String("key");
5hashMap.put(s1, 1);
6hashMap.put(s2, 2);
7System.out.println(hashMap.size());  // 1（s1.equals(s2)）
8
9// IdentityHashMap：使用==
10Map<String, Integer> identityMap = new IdentityHashMap<>();
11identityMap.put(s1, 1);
12identityMap.put(s2, 2);
13System.out.println(identityMap.size());  // 2（s1 != s2）

实现原理：

java

1public class IdentityHashMap<K,V> {
2    // 使用System.identityHashCode()
3    private static int hash(Object x) {
4        return System.identityHashCode(x);
5    }
6    
7    // 使用==比较
8    private static boolean eq(Object x, Object y) {
9        return x == y;
10    }
11}

使用场景：

java

1// 1. 对象图遍历（避免循环引用）
2Set<Object> visited = Collections.newSetFromMap(
3    new IdentityHashMap<>()
4);
5
6// 2. 代理对象映射
7Map<Object, ProxyInfo> proxyMap = new IdentityHashMap<>();
8
9// 3. 序列化/反序列化

21. Java 中的 WeakHashMap 是什么？

答案：

WeakHashMap的key是弱引用，当key没有强引用时会被GC回收。

实现原理：

java

1public class WeakHashMap<K,V> {
2    private Entry<K,V>[] table;
3    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
4    
5    private static class Entry<K,V> extends WeakReference<Object> {
6        V value;
7        int hash;
8        Entry<K,V> next;
9        
10        Entry(Object key, V value, ReferenceQueue<Object> queue) {
11            super(key, queue);  // key是弱引用
12            this.value = value;
13        }
14    }
15}

使用示例：

java

1// 普通HashMap：key不会被回收
2Map<Object, String> map = new HashMap<>();
3Object key = new Object();
4map.put(key, "value");
5key = null;
6System.gc();
7System.out.println(map.size());  // 1（key仍在map中）
8
9// WeakHashMap：key会被回收
10Map<Object, String> weakMap = new WeakHashMap<>();
11Object weakKey = new Object();
12weakMap.put(weakKey, "value");
13weakKey = null;
14System.gc();
15System.out.println(weakMap.size());  // 0（key被回收）

使用场景：

• 缓存实现
• 监听器注册
• 避免内存泄漏

22. Java 中 ConcurrentHashMap 1.7 和 1.8 之间有哪些区别？

答案：

特性	JDK 1.7	JDK 1.8
数据结构	Segment数组 + HashEntry数组	Node数组 + 链表 + 红黑树
锁机制	分段锁（Segment继承ReentrantLock）	CAS + synchronized
锁粒度	锁整个Segment	锁单个Node
并发度	Segment数量（默认16）	Node数量
查询操作	需要加锁	无锁（volatile）

JDK 1.7实现：

java

1public class ConcurrentHashMap<K,V> {
2    final Segment<K,V>[] segments;
3    
4    static final class Segment<K,V> extends ReentrantLock {
5        transient volatile HashEntry<K,V>[] table;
6        
7        V put(K key, int hash, V value) {
8            lock();  // 锁定整个Segment
9            try {
10                // 插入逻辑
11            } finally {
12                unlock();
13            }
14        }
15    }
16}

JDK 1.8实现：

java

1public class ConcurrentHashMap<K,V> {
2    transient volatile Node<K,V>[] table;
3    
4    public V put(K key, V value) {
5        int hash = spread(key.hashCode());
6        for (Node<K,V>[] tab = table;;) {
7            if ((f = tabAt(tab, i)) == null) {
8                // CAS插入
9                if (casTabAt(tab, i, null, new Node<>(hash, key, value)))
10                    break;
11            } else {
12                // synchronized锁定单个桶
13                synchronized (f) {
14                    // 插入逻辑
15                }
16            }
17        }
18    }
19}

23. Java 中 ConcurrentHashMap 的 get 方法是否需要加锁？

答案：

不需要加锁，使用volatile保证可见性。

实现原理：

java

1public class ConcurrentHashMap<K,V> {
2    // table用volatile修饰
3    transient volatile Node<K,V>[] table;
4    
5    static class Node<K,V> {
6        final int hash;
7        final K key;
8        volatile V val;      // value用volatile修饰
9        volatile Node<K,V> next;  // next用volatile修饰
10    }
11    
12    public V get(Object key) {
13        Node<K,V>[] tab;
14        Node<K,V> e, p;
15        int n, eh;
16        K ek;
17        int h = spread(key.hashCode());
18        
19        // 无锁读取
20        if ((tab = table) != null && (n = tab.length) > 0 &&
21            (e = tabAt(tab, (n - 1) & h)) != null) {
22            if ((eh = e.hash) == h) {
23                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
24                    return e.val;
25            }
26            // 遍历链表或红黑树
27            while ((e = e.next) != null) {
28                if (e.hash == h &&
29                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
30                    return e.val;
31            }
32        }
33        return null;
34    }
35}

为什么不需要加锁：

1. table、value、next都用volatile修饰
2. volatile保证可见性和有序性
3. 读操作不会修改数据

24. Java 为什么 ConcurrentHashMap 不支持 key 或 value 为 null？

答案：

原因：避免二义性问题

问题场景：

java

1// HashMap允许null
2Map<String, String> map = new HashMap<>();
3map.put("key", null);
4
5// 情况1：key存在，value为null
6String value = map.get("key");  // null
7
8// 情况2：key不存在
9String value = map.get("notExist");  // null
10
11// 无法区分这两种情况！

在并发环境下的问题：

java

1ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
2
3// 线程1
4if (map.containsKey("key")) {
5    String value = map.get("key");  // 可能返回null
6    // 无法判断是value为null还是被其他线程删除了
7}
8
9// 线程2（同时执行）
10map.remove("key");

HashMap为什么可以：

java

1// HashMap是单线程的，可以用containsKey判断
2if (map.containsKey("key")) {
3    // 确定key存在
4    String value = map.get("key");
5}

Doug Lea的解释：

1在并发环境中，如果允许null值，
2你无法判断get()返回null是因为：
31. key不存在
42. key存在但value为null
53. key刚被其他线程删除
6
7这会导致程序逻辑混乱。

25. Java 中的 CopyOnWriteArrayList 是什么？

答案：

CopyOnWriteArrayList是线程安全的List，写时复制整个数组。

实现原理：

java

1public class CopyOnWriteArrayList<E> {
2    private transient volatile Object[] array;
3    final transient ReentrantLock lock = new ReentrantLock();
4    
5    // 读操作：无锁
6    public E get(int index) {
7        return (E) array[index];
8    }
9    
10    // 写操作：复制数组
11    public boolean add(E e) {
12        lock.lock();
13        try {
14            Object[] elements = getArray();
15            int len = elements.length;
16            // 复制整个数组
17            Object[] newElements = Arrays.copyOf(elements, len + 1);
18            newElements[len] = e;
19            // 原子替换
20            setArray(newElements);
21            return true;
22        } finally {
23            lock.unlock();
24        }
25    }
26    
27    // 迭代器：使用快照
28    public Iterator<E> iterator() {
29        return new COWIterator<E>(getArray(), 0);
30    }
31}

特点：

1. 读操作完全无锁
2. 写操作复制整个数组
3. 迭代器不会抛ConcurrentModificationException
4. 适合读多写少场景

使用场景：

java

1// 监听器列表
2List<Listener> listeners = new CopyOnWriteArrayList<>();
3
4// 黑名单/白名单
5List<String> blacklist = new CopyOnWriteArrayList<>();
6
7// 配置信息
8List<Config> configs = new CopyOnWriteArrayList<>();

26. Java 你遇到过 ConcurrentModificationException 错误吗？它是如何产生的？

答案：

产生原因： 在迭代集合时，集合被修改了。

触发场景：

1. 单线程场景：

java

1List<String> list = new ArrayList<>();
2list.add("a");
3list.add("b");
4list.add("c");
5
6// 错误：迭代时删除
7for (String item : list) {
8    if (item.equals("b")) {
9        list.remove(item);  // ConcurrentModificationException
10    }
11}

2. 多线程场景：

java

1List<String> list = new ArrayList<>();
2
3// 线程1：迭代
4new Thread(() -> {
5    for (String item : list) {
6        System.out.println(item);
7    }
8}).start();
9
10// 线程2：修改
11new Thread(() -> {
12    list.add("new");  // ConcurrentModificationException
13}).start();

实现机制：

java

1public class ArrayList<E> {
2    protected transient int modCount = 0;  // 修改计数
3    
4    private class Itr implements Iterator<E> {
5        int expectedModCount = modCount;
6        
7        public E next() {
8            checkForComodification();
9            // ...
10        }
11        
12        final void checkForComodification() {
13            if (modCount != expectedModCount)
14                throw new ConcurrentModificationException();
15        }
16    }
17}

解决方案：

1. 使用迭代器删除：

java

1Iterator<String> it = list.iterator();
2while (it.hasNext()) {
3    String item = it.next();
4    if (item.equals("b")) {
5        it.remove();  // 正确
6    }
7}

2. 使用removeIf：

java

1list.removeIf(item -> item.equals("b"));

3. 使用并发集合：

java

1List<String> list = new CopyOnWriteArrayList<>();
2// 迭代时修改不会抛异常

4. 使用Stream：

java

1list = list.stream()
2    .filter(item -> !item.equals("b"))
3    .collect(Collectors.toList());

---

学习指南

核心要点：

• Java 集合框架体系结构
• HashMap 和 ConcurrentHashMap 实现原理
• 集合类的性能特点和使用场景
• 线程安全集合的实现机制

学习路径建议：

1. 掌握集合框架的基本结构
2. 深入理解 HashMap 的实现原理
3. 熟悉并发集合的使用
4. 掌握集合类的性能优化

---

学习指南

核心要点：

• Java 集合框架体系结构
• HashMap 和 ConcurrentHashMap 实现原理
• 集合类的性能特点和使用场景
• 线程安全集合的实现机制

学习路径建议：

1. 掌握集合框架的基本结构
2. 深入理解 HashMap 的实现原理
3. 熟悉并发集合的使用
4. 掌握集合类的性能优化

forum

评论区 / Comments