Java基础 面试题

1. HashMap 底层原理与 JDK 演进

❓ 题目： 请详细说明 HashMap 的数据结构，以及 put 和 get 操作的完整流程。

追问1：JDK 7 到 JDK 8，HashMap 做了哪些关键优化？为什么链表转红黑树的阈值是 8？ 追问2：HashMap 在多线程环境下使用会出现什么问题？ConcurrentHashMap 是如何解决这些问题的？

💡 答案：

主问题： JDK 8 的 HashMap 底层采用数组 + 链表 + 红黑树的复合结构。put 操作的完整流程是：首先对 key 做 hash，将 hashCode 的高 16 位与低 16 位做异或运算（目的是让高位也参与取模，减少低位相同的碰撞），然后对数组长度取模找到桶下标。如果桶为空，直接创建新节点放入。如果桶不为空，需要判断桶中第一个节点：如果是 TreeNode 说明这个桶已经是红黑树，走树的插入逻辑；如果是普通 Node，遍历链表，找到了相同 key 就覆盖 value，找不到就插入到链表尾部，插入后检查链表长度是否达到树化阈值（8）且数组长度是否大于等于 64，满足条件则将链表转为红黑树。插入完成后检查 size 是否超过 threshold，超过则扩容为原来的两倍。get 操作相对简单：计算 hash 找到桶下标，判断桶中第一个节点是否是目标（先比较 hash，再比较 key 的引用和 equals），如果是树节点走 getTreeNode 查找，否则遍历链表查找。

追问1： JDK 7 到 8 有三个关键优化。第一，哈希算法简化了——JDK 7 的 hash 方法做了多次移位和异或试图让哈希更均匀，JDK 8 只做了一次高 16 位与低 16 位的异或，因为 JDK 8 引入了红黑树，即使偶尔碰撞多一点也能在 O(log n) 时间内完成查找，不再需要那么重的哈希扰动。第二，链表插入方式变了——JDK 7 是头插法（新节点插入链表头部），JDK 8 改为了尾插法。头插法在扩容迁移节点时会导致链表反转，多线程环境下会产生循环链表，尾插法彻底解决了这个问题。第三、引入了红黑树。链表转红黑树阈值设为 8 的原因与泊松分布有关：理想情况下 put 操作的哈希碰撞概率极低，链表长度达到 8 的概率是千万分之一级别。如果一条链表真的到了 8，说明哈希函数的随机性出了问题，通过转为红黑树来兜底，避免退化为 O(n)。红黑树节点占用的内存大约是链表节点的两倍，所以阈值不能太低；而在 8 以内链表遍历的性能已经完全够用。

追问2： HashMap 多线程最典型的两个问题是死循环和数据覆盖。死循环只出现在 JDK 7 中——两个线程同时扩容时，头插法导致链表反转形成环形链表，get 操作触发无限循环 CPU 100%。JDK 8 尾插法解决了死循环但数据覆盖问题依然存在——两个线程同时 put，size++ 不是原子操作导致计数不准确，或者两个线程同时判断桶为空并分别插入导致其中一个数据丢失。ConcurrentHashMap 在 JDK 8 中采用 CAS + synchronized 的并发策略：数组中没有节点时用 CAS 尝试插入；已有节点时对桶中第一个节点加 synchronized 锁（锁粒度在单个桶而非整个 Map），并支持多线程并发扩容（每个线程负责一部分桶的迁移）。这种设计的并发度远高于 JDK 7 的分段锁（Segment），因为只要两个线程访问不同桶就完全无锁竞争。

📌 易错点 / 加分项：

  • 树化需要同时满足链表长度 ≥ 8 且数组长度 ≥ 64，数组太小时优先扩容而不是树化
  • ConcurrentHashMap 的 get 不需要加锁，因为 Node 的 val 和 next 都被 volatile 修饰
  • HashMap 容量永远是 2 的幂，是为了能用 (n-1) & hash 代替取模运算，位运算效率更高

2. ArrayList vs LinkedList 深入对比

❓ 题目： ArrayList 和 LinkedList 在底层实现、随机访问、插入删除上的性能差异是怎样的？

追问1：很多人说 LinkedList 插入删除快，这个说法在什么条件下成立？什么条件下反而不如 ArrayList？ 追问2：ArrayList 扩容为什么是 1.5 倍？为什么不用 2 倍？

💡 答案：

主问题： ArrayList 底层是 Object 数组，元素在内存中连续存储；LinkedList 是双向链表，每个节点维护前后指针。随机访问上，ArrayList 由于底层数组的连续性，时间复杂度是 O(1)；LinkedList 必须从头或尾开始遍历直到找到目标位置，时间复杂度 O(n)。插入删除的结论其实比较微妙：如果是”在尾部追加”，ArrayList 在容量够时 O(1)，不够时需要扩容导致 O(n)；LinkedList 永远只需要调整指针 O(1)。如果是在中间位置插入/删除，ArrayList 需要将后续元素整体前移或后移 O(n)，LinkedList 定位到目标位置就需要 O(n) 遍历，定位之后调整指针是 O(1)。所以整体看，中间位置插入删除两者差不多，不是说 LinkedList 就一定快。

追问1： “LinkedList 插入删除快”只在一种情况下成立：你已经持有了目标位置的节点引用，这时候确实是 O(1)。但在实际开发中，我们几乎总是”在某个下标位置插入”——LinkedList 要先遍历到这个位置，遍历的代价是 O(n)，而 ArrayList 移动数组元素虽然是 O(n) 却是连续内存的批量复制（底层用 System.arraycopy，这是一条 native 指令，极快）。实际 benchmark 测试中，对于中小规模数据，ArrayList 在中间位置的插入性能经常反超 LinkedList——因为遍历链表的指针跳转会导致大量的 cache miss，而数组的连续内存在 CPU 缓存友好性上有巨大优势。所以”LinkedList 插入快”是一个需要加很多前提条件的说法，不能背死答案。

追问2： ArrayList 扩容倍数是 1.5 倍（oldCapacity + (oldCapacity >> 1)）。这样做是综合考虑了内存利用和扩容频率。如果用 2 倍，每次扩容后新容量都是 2 的幂，在极端情况下可能造成大量内存碎片——因为 Jemalloc 等内存分配器处理 2 的幂大小的内存块时有特殊的 bin 分类，频繁分配和释放 2 的幂大小的数组容易产生碎片。用 1.5 倍增长的序列不是严格的 2 的幂，内存分配器的行为更优。另外 1.5 倍的扩容次数虽比 2 倍略多，但内存占用更平滑，不会出现扩容后一半空间浪费的情况。这也参考了 C++ vector 的实现——大部分标准库用的就是 1.5 倍增长。

📌 易错点 / 加分项：

  • 能提到 CPU cache miss 和连续内存复制的比较，说明对底层有理解
  • ensureCapacity 可以预防性扩容减少扩容次数，这在批量 add 时很有用
  • ArrayList 的最大长度是 Integer.MAX_VALUE - 8，减 8 是因为有些 JVM 需要在数组头存一些元信息

3. 泛型擦除与实际应用

❓ 题目： Java 泛型是如何实现的？“泛型擦除”指的是什么？它带来了哪些限制？

追问1：既然有泛型擦除，为什么运行时通过反射还能拿到泛型信息？什么场景下可以拿到，什么场景下拿不到？

💡 答案：

主问题： Java 泛型是通过”类型擦除”实现的，这一点和 C# 在运行时保留具体泛型类型的方式完全不同。类型擦除的意思是：编译器在编译期检查泛型类型安全后，会把所有类型参数信息擦除掉，生成的字节码中不带任何泛型信息。具体来说，无边界限制的泛型类型 <T> 被替换为 Object，有上界的泛型 <T extends Number> 被替换为 Number，在需要的地方自动插入强制类型转换。这样做的目的是保持向后兼容——JDK 5 引入泛型时，旧的字节码和类库无需修改就可以继续运行。但代价也很明显：第一，基本类型不能作为泛型参数；第二，instanceof 不能检查泛型类型；第三，不能 new 泛型数组；第四，静态方法和静态变量不能使用类的泛型参数；第五，不能创建泛型类型的异常类。

追问1： 这里的关键是：泛型擦除只擦除局部变量和方法参数的泛型信息。如果类型信息是声明在类、字段、方法签名这些”声明层面”的，它们会保留在字节码的 Signature 属性表中。所以当我们通过反射获取 Field.getGenericType()、Method.getGenericReturnType()、Class.getTypeParameters() 时，拿到的泛型信息来自 Signature 属性，不是编译期变量持有的那部分。具体来说：假设 List<String> 作为类的成员变量，运行时可以拿到 String 这个类型参数。但如果是一个方法内部的局部变量 List<String> list = new ArrayList<>()，运行时通过反射是拿不到这个 String 的——因为局部变量的泛型信息根本不进入字节码。最有代表性的场景是 Gson/Fastjson 这种 JSON 框架，它们在反序列化 List<User> 时，必须通过子类化匿名类（new TypeToken<List<User>>(){}）来”捕捉”泛型参数到类的 Signature 中，否则运行时无法知道 List 里装的是什么类型。

📌 易错点 / 加分项：

  • 泛型 eraser 和 reified 的区分——Java 是 eraser，C#/Kotlin 内联函数可以是 reified
  • List<String> 和 List<Integer> 的 Class 是同一个——List.class，这是擦除的直接后果
  • 桥接方法（bridge method）是类型擦除的一个副作用，子类重写父类泛型方法时编译器自动生成