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。

四、性能特点‌

‌操作‌	‌时间复杂度‌	‌说明‌
‌随机访问‌	O(1)	数组索引直接定位元素
‌尾部插入‌	均摊 O(1)	偶尔触发扩容复制操作
‌中间插入/删除‌	O(n)	需移动后续元素（System.arraycopy）

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

五、高频面试题

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

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

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

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

3. ‌ArrayList 与 LinkedList 的区别？ ‌

‌特性‌	‌ArrayList‌	‌LinkedList‌
底层结构	动态数组	双向链表
随机访问效率	O(1)（快）	O(n)（慢）
中间增删效率	O(n)（慢）	O(1)（快）
内存占用	连续内存，无额外指针	节点存储前后指针

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 时定位到不同桶。

✅ ‌关键总结

‌特性‌	‌JDK 1.7‌	‌JDK 1.8‌
数据结构	数组 + 链表	数组 + 链表/红黑树
插入方式	头插法	尾插法
哈希冲突解决	纯拉链法	链表树化优化
多线程扩容安全性	可能死循环	无死循环（尾插法保证）

Queue

一、队列核心原理

1. ‌FIFO 机制‌

队列遵循先进先出（FIFO）原则，元素在队尾添加（入队 ），在队头移除（出队 ）。

• ‌接口定义‌：

public interface Queue<E> {
    boolean add(E e);    // 队尾插入，失败抛异常
    boolean offer(E e);  // 队尾插入，失败返false
    E remove();          // 移除队头，空队列抛异常
    E poll();            // 移除队头，空队列返null
    E element();         // 查看队头，空队列抛异常
    E peek();            // 查看队头，空队列返null
}

2. ‌数据结构实现‌

队列类型	底层结构	特点
‌LinkedList‌	双向链表	支持高效插入/删除，天然支持双端操作（实现 Deque 接口）
‌ArrayDeque‌	环形动态数组	内存连续访问快，扩容时性能优于链表；不支持 null 元素
‌PriorityQueue‌	二叉堆	按自然顺序或自定义 Comparator排序，队头始终为最小元素
‌阻塞队列‌	数组/链表+锁	如 ArrayBlockingQueue，提供线程安全的入队/出队阻塞控制

‌二、Deque

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

Deque接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

三、典型队列适用场景

1. 常规任务调度‌

• ‌ArrayDeque
  适用于高频入队/出队操作（如事件循环、缓存系统），因数组连续内存访问高效。
• ‌LinkedList‌
  需同时使用队列和栈功能时（如撤销操作栈），或需频繁在两端操作数据。

2. 优先级调度‌

• ‌PriorityQueue 任务按优先级处理场景

  • 订单系统（VIP 订单优先处理）
  • 定时任务调度（时间戳排序、优先级排序）

PriorityQueue<Task> queue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));

3. 高并发场景

• ‌ConcurrentLinkedQueue‌
  无锁并发队列，适合生产者-消费者模型（如日志异步收集），吞吐量高但需处理消费速度匹配。
• ‌阻塞队列（如 ArrayBlockingQueue）
  线程池任务管理（ThreadPoolExecutor 默认使用），通过固定容量防止资源耗尽。

BlockingQueue<Runnable> queue = new ArrayBlockingQueue<>(100);
executor = new ThreadPoolExecutor(5, 10, 60s, queue);

4. 延迟任务‌

• ‌DelayQueue‌
  实现延迟执行（如订单超时关闭），元素需实现 Delayed 接口：

class DelayTask implements Delayed {
    long executeTime;
    public long getDelay(TimeUnit unit) {
        return unit.convert(executeTime - System.nanoTime(), NANOSECONDS);
    }
}

5. 资源限制‌

• ‌有界队列（如 ArrayBlockingQueue）
  控制系统内存消耗，防止高并发下 OOM（如 API 请求限流）。
• ‌无界队列（如LinkedBlockingQueue）
  适合任务量不可预测但需保证不丢弃任务的场景（如实时数据流）。

四、选型对比总结

‌场景需求‌	‌推荐队列‌	‌关键优势‌
高频非阻塞操作	ArrayDeque	内存局部性好，性能稳定
优先级调度	PriorityQueue	动态排序，最小堆高效取极值
高并发非阻塞	ConcurrentLinkedQueue	无锁设计，高吞吐
线程池任务缓冲	ArrayBlockingQueue	阻塞控制，防止资源耗尽
延迟任务管理	DelayQueue	内置时间优先级调度
需同时支持栈/队列操作	LinkedList	灵活双端操作

持续更新中…