在Java中，集合体系结构是怎么样的？主要分为那些类？分别有什么特点？

  • 单列集合（Collection）
    • List：有序、可重复的集合（如 ArrayList、LinkedList）。
    • Set：无序、不可重复的集合（如 HashSet、TreeSet）。
  • 双列集合（Map）
    • 代表一组键值对（Key-Value）的映射关系，键不可重复。（如HashMap、TreeMap、LinkedHashMap）

主要类特点：

  • ArrayList：动态数组，随机访问快，插入删除慢。
  • LinkedList：双向链表，插入删除快（尤其是中间位置），随机访问慢。
  • HashSet：底层依赖HashMap，无序，查询快。
  • TreeSet：基于红黑树，元素有序（自然排序或自定义排序）。
  • HashMap：数组 + 链表 / 红黑树，无序，查询、插入效率高。
  • TreeMap：基于红黑树，key 有序，支持范围查询。

List和Set分别有什么特点？

  • List：
    • 有序（元素插入顺序与遍历顺序一致）。
    • 可重复（允许元素值相同）。
    • 支持通过索引访问（get(int index)）。
    • 允许存储多个null元素。
  • Set：
    • 无序（HashSet）或有序（TreeSet按 key 排序，LinkedHashSet按插入顺序）。
    • 不可重复（元素需重写equals()和hashCode()保证唯一性）。
    • 无索引，不支持随机访问。
    • 最多允许一个null元素（HashSet）。

ArrayList 和 LinkedList有什么区别？

维度 ArrayList LinkedList
底层结构 动态数组（连续内存） 双向链表（非连续内存）
随机访问 快（O(1)，直接通过索引） 慢（O(n)，需遍历链表）
尾部插入 / 删除 快（O(1)） 快（O(1)，仅需调整指针）
中间插入 / 删除 慢（O(n)，需移动元素） 快（O(1)）

ArrayList的扩容机制？

  • 初始容量：默认 10（无参构造），也可通过构造函数指定初始容量。
  • 扩容触发：当添加元素后，size超过当前容量时触发。
  • 扩容逻辑：
    1. 计算新容量：默认是原容量的 1.5 倍（oldCapacity + (oldCapacity >> 1)）。
    2. 若新容量仍不足（如添加大量元素），直接扩容至所需容量。
    3. 通过Arrays.copyOf()复制原数组元素到新数组，替换原数组引用。

说下 HashMap的put流程及扩容机制？

image-20251012162400495.png

  • 扩容机制：
    1. 新容量为原容量的 2 倍（保证容量为 2 的幂）。
    2. 重新计算每个节点的新下标（JDK1.8 中通过hash & oldCapacity判断，0 则下标不变，1 则下标 = 原下标 + oldCapacity）。
    3. 将原数组元素迁移至新数组（链表拆分或红黑树拆分）。

HashMap的扩容如何触发？

  • 当put元素后，size（键值对数量）超过阈值（capacity * loadFactor，默认负载因子 0.75）时触发。
  • 特殊情况：若链表长度超过 8 且数组容量 < 64，会先扩容而非转为红黑树。

HashMap 在 JDK 1.7 和 JDK 1.8 中有什么区别？

维度 JDK 1.7 JDK 1.8
底层结构 数组 + 链表 数组 + 链表 + 红黑树
链表插入方式 头插法（可能导致循环链表） 尾插法（避免循环）
扩容时元素迁移 重新计算 hash 利用高低位判断新下标
hash 计算 多次扰动（4 次移位 + 异或） 1 次扰动（高 16 位异或低 16 位）
阈值判断（转树） 无（仅链表） 链表长度 > 8 且容量≥64 转红黑树
安全性 线程不安全，扩容可能死循环 线程不安全，但避免死循环

CopyOnWriteArrayList有什么特点？

CopyOnWriteArrayList 采用的是写时复制的技术，适用于读多写少的场景，读操作不需要加锁，当时读取到的数据可能不是最新的数据。

ConcurrentHashMap在JDK1.8中是如何保证put流程和初始化流程线程安全的？

  • 初始化：
    • 通过 CAS 操作保证线程安全。当table为null时，多个线程竞争初始化，CAS 成功的线程执行初始化（设置容量），失败的线程自旋等待。
  • put 流程：
    1. 计算 hash 和下标，若数组未初始化则触发初始化。
    2. 若下标位置为空，通过 CAS 插入节点（无锁）。
    3. 若下标位置为MOVED（正在扩容），帮助扩容（多线程协同扩容）。
    4. 否则，对该位置的头节点加synchronized锁，执行插入（链表或红黑树）。
    5. 插入后更新元素数量（通过baseCount或CounterCell，CAS 更新避免锁竞争）。

ConcurrentHashMap在JDK1.8中和JDK1.7中分别是怎么保证线程安全的？哪个效率好？

  • JDK 1.7：
    • 采用分段锁（Segment）：每个 Segment 是独立的 HashMap，自带ReentrantLock。
    • 不同 Segment 的操作互不干扰，锁粒度为 Segment。
  • JDK 1.8：
    • 取消分段锁，采用CAS + synchronized：对数组槽位的头节点加锁（锁粒度为单个节点）。
    • 无竞争时用 CAS，有竞争时才加锁，效率更高。
  • 效率对比：JDK 1.8 效率更高。原因是锁粒度更细（节点级），减少锁竞争，且 CAS 操作在低并发时无需阻塞，性能更优。