【Java高频面试问题】数据结构篇

ArrayList原理

一、数据结构与初始化

• ‌底层结构‌：基于动态数组（Object[] elementData）实现，支持索引随机访问，查询效率高（O(1)）。

• ‌初始化机制‌：

  • 无参构造时，初始容量为 ‌0‌（首次添加元素时扩容为默认容量 ‌10‌）。
  • 指定容量的构造器（如 new ArrayList(20)）直接分配对应大小的数组。

二、扩容机制（核心）

1. ‌触发条件‌：添加元素时，若当前元素数量 size + 1 > 数组长度，则触发扩容。

2. ‌扩容规则‌：

   • 新容量 = ‌旧容量 × 1.5‌（位运算实现：newCapacity = oldCapacity + (oldCapacity >> 1)）。
   • 首次扩容时，默认容量为 ‌10‌。

3. ‌扩容步骤‌：

   a. 创建新数组（大小为计算后的新容量）；
   b. 复制原数组元素到新数组（Arrays.copyOf()）；
   c. 更新底层数组引用指向新数组。

三、添加元素流程（add方法）

1. 检查当前数组是否需扩容，若需扩容则执行 grow() 方法。
2. 将新元素存入数组末尾（elementData[size] = element）。
3. 元素数量 size 自增 1。

四、性能特点‌

• ‌线程不安全‌：多线程并发修改会导致数据不一致（如 ConcurrentModificationException）。
• ‌替代方案‌：需线程安全时使用 Vector 或 Collections.synchronizedList。

五、高频面试题

1. ‌扩容因子为什么是 1.5？ ‌

   • ‌空间与时间权衡‌：倍数过小导致频繁扩容；过大导致内存浪费。1.5 倍经验证为较优解。

2. ‌ArrayList(int capacity) 会立即分配数组吗？ ‌

   • 是，直接初始化指定容量的数组（不触发首次扩容）。

3. ‌ArrayList 与 LinkedList 的区别？ ‌

4. ‌Arrays.asList() 转换后的 List 能扩容吗？ ‌

   • 不能！返回的是固定大小的 Arrays 内部类 ArrayList（非 java.util.ArrayList）。

✅ ‌关键总结

• ‌扩容是性能瓶颈‌：预估数据量并指定初始容量可避免频繁扩容。
• ‌适用场景‌：高频查询、尾部插入；避免频繁中间增删。
• ‌线程安全‌：优先选择 CopyOnWriteArrayList。

HashMap原理

一、数据结构演进

1. ‌JDK 1.7：数组 + 单向链表‌

• 哈希冲突采用 ‌拉链法‌（头插法），插入新节点到链表头部。
• 问题‌：链表过长时查询退化至 O(n)；多线程扩容时头插法可能形成‌循环链表‌导致死循环。

// JDK 1.7 Entry节点（头插法）
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e); // 新节点指向原头节点
}

2. ‌JDK 1.8：数组 + 链表/红黑树‌

• 链表长度 ≥8 且数组长度 ≥64 时，链表转为‌红黑树‌（查询效率 O(n) → O(log n)）；
• 树节点 ≤6 时退化为链表；
• 插入方式改为‌尾插法‌，解决多线程死循环问题。

二、核心实现原理

1. ‌哈希计算与索引定位‌

   • 扰动函数：(h = key.hashCode()) ^ (h >>> 16)，混合高低位减少哈希冲突。
   • 索引计算：index = (n - 1) & hash（n 为数组长度，‌必须为 2 的幂‌）。

• ‌为何容量为 2 的幂？ ‌

  • 位运算 & 替代取模 % 提升性能；
  • 使 (n-1) 的二进制全为 1，哈希分布更均匀。

2. ‌put 方法流程‌

   a. 数组未初始化则扩容（默认容量 16）；
   b. 计算索引位置，若桶为空则直接插入；
   c. 若桶为红黑树，按树结构插入；
   d. 若桶为链表，遍历插入（尾插法），链表≥8 时触发树化；
   e. 插入后检查负载因子（默认 0.75），超过阈值则扩容。

三、扩容机制（resize）

• ‌触发条件‌：元素数量 > 容量 × 负载因子（默认 16×0.75=12）。
• ‌扩容过程‌：

1. 容量翻倍（新容量 = 旧容量 << 1）；
2. 重新计算节点位置：原节点索引不变或迁移至 原索引 + 旧容量 位置（高位变化判断）。

• ‌树拆分‌：红黑树在扩容时按哈希值高低位拆分为两个链表，若长度≤6则退化为链表。

四、线程安全问题

1. ‌多线程操作风险‌

   • ‌数据覆盖‌：并发 put 时相同哈希值的节点可能被覆盖。
   • ‌死循环（JDK 1.7）：头插法扩容时链表倒序形成环（尾插法在 JDK 1.8 解决）。

2. ‌替代方案‌：使用 ConcurrentHashMap（分段锁或 CAS + synchronized）。

五、高频面试题

1. ‌为什么负载因子是 0.75？ ‌

   • 权衡空间与时间：过低导致频繁扩容；过高增加哈希冲突概率。

2. ‌HashMap 允许 Null 键/值吗？ ‌

   • 允许一个 Null 键和多个 Null 值（HashTable 不允许）。

3. ‌重写 equals 为什么要重写 hashCode？ ‌

   • 确保相同对象哈希值一致，否则可能导致 put/get 时定位到不同桶。

✅ ‌关键总结

持续更新中…