java基础知识点

第二章JAVA集合框架

Java集合框架是面试绝对重点，尤其是 HashMap、ConcurrentHashMap 的源码级理解。

2.1 ArrayList vs LinkedList

2.1.1 ArrayList 扩容机制
ArrayList 的扩容是面试高频考点

// ArrayList扩容源码（JDK 8）
// 默认初始容量：10（JDK7+是懒初始化，new ArrayList()时是空数组，首次add才扩容到10）
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}

private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 扩容1.5倍：oldCapacity + oldCapacity >> 1
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity – minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity – MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Arrays.copyOf 底层调用 System.arraycopy（native方法），深拷贝数组
elementData = Arrays.copyOf(elementData, newCapacity);
}

// 示例：容量变化
// add第1个元素: 0 → 10
// add第11个元素: 10 → 15 (10+10/2)
// add第16个元素: 15 → 22 (15+15/2=22)
// 扩容开销：每次扩容需要将旧数组的元素复制到新数组，时间复杂度O(n)

2.2 HashMap（超级重点）

⚠️ HashMap 是中厂面试最高频的考点，没有之一！需要达到源码级掌握。

2.2.1 JDK7 vs JDK8 数据结构差异
JDK7：数组 + 链表（头插法）
JDK8：数组 + 链表 + 红黑树（尾插法），当链表长度 ≥ 8 且数组长度 ≥ 64，链表转为红黑树
红黑树退化为链表的条件：当红黑树节点数 ≤ 6 时，退化为链表（中间差 7 是为了避免频繁转换的缓冲）

2.2.2 HashMap put 流程（必须背熟）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;

// 步骤1：数组为空 → 初始化（resize）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;

// 步骤2：计算下标，该位置为空 → 直接放入
// 下标计算：i = (n-1) & hash
if ((p = tab[i = (n – 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);

else {
Node<K,V> e; K k;
// 步骤3：该位置有节点，且key相同 → 覆盖旧值
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤4：该位置是红黑树节点 → 插入树中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤5：该位置是链表节点 → 遍历链表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度 ≥ 8（TREEIFY_THRESHOLD）→ 转为红黑树
if (binCount >= TREEIFY_THRESHOLD – 1)
treeifyBin(tab, hash);
break;
}
// 找到相同key → 跳出
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 步骤6：e != null 说明key已存在，覆盖旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // LinkedHashMap用
return oldValue;
}
}
++modCount;
// 步骤7：size > threshold → 扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

2.2.3 HashMap 扩容机制

final Node<K,V>[] resize() {
// … 省略部分代码
// 新容量 = 旧容量 * 2
// 新阈值 = 旧阈值 * 2

// JDK8 的优化：rehash不需要重新计算hash
// 扩容后，节点要么在原位置 j，要么在原位置 j + oldCap
// 原理：下标 = hash & (newCap-1)，newCap-1 比 oldCap-1 多了一位高位bit
// 如果 hash 中该高位bit=0 → 位置不变
// 如果 hash 中该高位bit=1 → 位置变为 j + oldCap
do {
next = e.next;
// (e.hash & oldCap) == 0 → 位置不变
if ((e.hash & oldCap) == 0) {
if (loTail == null) loHead = e;
else loTail.next = e;
loTail = e;
}
// (e.hash & oldCap) != 0 → 位置变为 j + oldCap
else {
if (hiTail == null) hiHead = e;
else hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
}

2.2.4 高频面试问题汇总

Q1: 为什么负载因子是 0.75？
空间利用率和时间效率的折中。负载因子越大，空间利用率越高但冲突概率增加；负载因子越小，冲突概率越低但空间浪费增多。根据泊松分布，0.75时链表长度达到8的概率约为0.00000006，是统计学上的平衡点。
Q2: 为什么容量是 2 的幂？
●1. 方便取模运算：hash % n 等价于 hash & (n-1)，位运算效率远高于取模
●2. 扩容时数据迁移更高效：不需要重新计算 hash，只需判断 (e.hash & oldCap)
●3. 使元素分布更均匀：2的幂-1 的二进制全是1，与 hash 做 & 运算能均匀分布
Q3: 为什么红黑树阈值是 8？
根据泊松分布统计，在负载因子 0.75 时，链表长度达到 8 的概率不到千万分之一。但一旦出现（如被恶意攻击构造大量 hash 冲突），链表查询退化到 O(n)，转红黑树后可保证 O(log n)。这也是为什么 Redis、Nginx 等也选择 8 作为转树阈值。
Q4: JDK7 扩容为什么可能导致死循环（CPU 100%）？
JDK7 采用头插法，在多线程同时扩容时，可能导致链表形成环形，造成 get() 时死循环和 CPU 100%。JDK8 改为尾插法解决了死循环问题，但 HashMap 仍然不是线程安全的（可能丢数据、size 不准确），多线程场景应使用 ConcurrentHashMap。
Q5: HashMap 的 hash 函数为什么这样设计？

// hashCode 的高16位与低16位做异或，增加低位的随机性
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 原因：计算下标时是 (n-1) & hash，当 n 较小时（如16，n-1=15=00001111），
// 只使用 hash 的低4位，高位无法参与运算。通过高16位异或低16位，
// 将高位的影响扩散到低位，使散列更均匀。

2.3 ConcurrentHashMap

⚠️ ConcurrentHashMap 是并发编程面试的核心考点，必须清楚 JDK7 分段锁和 JDK8 CAS+synchronized 的区别。

2.3.1 JDK7 分段锁机制

JDK7 的 ConcurrentHashMap 采用分段锁（Segment）机制，默认 16 个 Segment，每个 Segment 内部是一个独立的 HashMap。不同 Segment 可以并发操作，并发度为 16。

// JDK7 结构示意
// ConcurrentHashMap
// ├── Segment[0] (继承 ReentrantLock)
// │ ├── HashEntry → HashEntry → … (链表)
// │ └── …
// ├── Segment[1]
// │ └── …
// └── Segment[15]
// └── …

// put 流程
public V put(K key, V value) {
int hash = hash(key);
int segmentIndex = (hash >>> segmentShift) & segmentMask; // 定位Segment
Segment<K,V> segment = ensureSegment(segmentIndex);
return segment.put(key, hash, value, false);
}
// Segment.put() 内部先 lock()，然后执行类似于 HashMap 的 put 流程

2.3.2 JDK8 CAS + synchronized 机制
JDK8 完全重构了 ConcurrentHashMap，放弃了分段锁，改用更细粒度的锁策略：
●数组为空时：CAS 初始化数组
●桶位置为空时：CAS 插入节点（无锁）
●桶位置不为空时：synchronized 锁住该桶的头节点（链表头/树根）
●扩容时：多线程协作扩容，每个线程分配一段区间迁移数据

// JDK8 put 核心逻辑
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 1. 计算hash：spread() 使hash为正数(负数有特殊含义)
int hash = spread(key.hashCode());

// 2. 死循环 + CAS
for (Node<K,V>[] tab = table;;) {
// 3. 数组为空 → CAS初始化数组（只有一个线程成功）
if (tab == null) {
// CAS操作 initTable()
}
// 4. 桶位置为空 → CAS放入节点（无锁）
else if ((f = tabAt(tab, i = (n – 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break;
}
// 5. Moved节点 → 帮助扩容
else if ((fh = f.hash) == MOVED) {
tab = helpTransfer(tab, f);
}
// 6. 桶位置有节点 → synchronized锁住头节点
else {
synchronized (f) {
// 如果节点是链表 → 遍历链表
// 如果节点是树 → 遍历树
// size+1
}
}
}
}

2.3.3 ConcurrentHashMap 的 sizeCtl 含义

●sizeCtl = 0：默认值，表示数组未初始化
●sizeCtl = -1：表示正在初始化数组
●sizeCtl > 0 且数组为null：初始化容量
●sizeCtl > 0 且数组已初始化：下次扩容的阈值
●sizeCtl < -1：-(1 + 扩容线程数)，如 -3 表示有 2 个线程在扩容

2.4 HashSet / TreeSet / LinkedHashMap

2.4.1 HashSet

HashSet 底层基于 HashMap 实现，元素作为 HashMap 的 key，value 是一个固定的虚拟对象（PRESENT = new Object()）。

// HashSet 本质
public class HashSet<E> {
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

public boolean add(E e) {
return map.put(e, PRESENT) == null; // 利用HashMap的key不重复特性
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
}

2.4.2 TreeSet

TreeSet 底层基于 TreeMap（红黑树），元素有序（自然排序或 Comparator 排序），查询时间复杂度 O(log n)。
2.4.3 LinkedHashMap

LinkedHashMap 继承 HashMap，在其基础上添加了双向链表来维护元素的插入顺序或访问顺序。这是实现 LRU 缓存的基础。

// LinkedHashMap 的核心：自定义的 Entry 节点
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after; // 双向链表的前后指针
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}

// accessOrder = true：按访问顺序排序（LRU缓存的核心配置）
// accessOrder = false：按插入顺序排序（默认）
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);