Java常用数据结构底层实现原理及应用场景

一、线性结构

1. ArrayList

• 底层实现：动态数组（Object[] elementData）。

• 核心特性：

  • 默认初始容量为 10，扩容时容量增长为原来的 1.5 倍（int newCapacity = oldCapacity + (oldCapacity >> 1)）。

  • 随机访问快（O(1)），插入/删除慢（需移动元素，O(n)）。

  • 非线程安全，可用 Collections.synchronizedList 包装。

2. LinkedList

• 底层实现：双向链表（Node<E> 节点，包含前驱、后继指针）。

• 核心特性：

  • 插入/删除快（O(1)，但需先遍历到位置，实际为 O(n)）。

  • 随机访问慢（需从头遍历，O(n)）。

  • 实现了 Deque 接口，可作为队列或栈使用。

3. Vector

• 底层实现：与 ArrayList 类似，但所有方法用 synchronized 修饰。

• 缺点：性能差（锁粒度大），已被 CopyOnWriteArrayList 或 Collections.synchronizedList 取代。

---

二、哈希表结构

1. HashMap

• 底层实现（JDK 8+）：

  • 数组 + 链表/红黑树（Node<K,V>[] table）。

  • 链表长度超过 8 且数组长度 ≥ 64 时，链表转为红黑树；树节点数 ≤ 6 时退化为链表。

• 关键机制：

  • 哈希计算：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)（扰动函数减少哈希冲突）。

  • 扩容：默认负载因子 0.75，容量翻倍（newCap = oldCap << 1），重新哈希（JDK 8 优化：元素位置为原位置或原位置+旧容量）。

• 非线程安全，多线程下可能死循环（JDK 7 链表头插法导致）。

2. LinkedHashMap

• 底层实现：继承 HashMap，通过双向链表维护插入顺序或访问顺序（LRU 实现基础）。

• 用途：实现缓存淘汰策略（覆盖 removeEldestEntry 方法）。

3. ConcurrentHashMap

• 底层实现（JDK 8+）：

  • 分段锁 → 改为 Node 数组 + CAS + synchronized（锁单个链表头或树根节点）。

  • 支持高并发，读操作无锁。

• 关键优化：

  • size() 通过 baseCount 和 CounterCell[] 分片统计，避免竞争。

---

三、树形结构

1. TreeMap

• 底层实现：红黑树（自平衡二叉搜索树）。

• 特性：

  • 键按自然顺序或 Comparator 排序。

  • 插入/删除/查询时间复杂度 O(log n)。

• 用途：范围查询（ceilingKey(), floorKey()）。

2. PriorityQueue

• 底层实现：二叉堆（数组实现，Object[] queue）。

• 特性：

  • 堆顶元素为最小（默认小顶堆）或最大（通过 Comparator 定义）。

  • 插入（siftUp）和删除（siftDown）时间复杂度 O(log n)。

---

四、集合结构

1. HashSet

• 底层实现：基于 HashMap（所有值映射到同一个 PRESENT 对象）。

• 特性：

  • 元素唯一性（依赖 hashCode() 和 equals()）。

  • 无序，允许 null。

2. LinkedHashSet

• 底层实现：继承 HashSet，内部使用 LinkedHashMap 维护插入顺序。

3. TreeSet

• 底层实现：基于 TreeMap，元素按自然顺序或 Comparator 排序。

---

五、队列结构

1. ArrayDeque

• 底层实现：循环数组（Object[] elements）。

• 特性：

  • 双端队列（队头/队尾均可操作）。

  • 比 LinkedList 更高效（内存连续，缓存友好）。

2. BlockingQueue

• 实现类：ArrayBlockingQueue（数组）、LinkedBlockingQueue（链表）、PriorityBlockingQueue（堆）。

• 特性：

  • 线程安全，支持阻塞插入/取出（put(), take()）。

  • 用于生产者-消费者模型。

---

六、底层实现原理总结

数据结构	底层实现	时间复杂度（平均）	线程安全
ArrayList	动态数组	查询 O(1)，增删 O(n)	否
LinkedList	双向链表	查询 O(n)，增删 O(1)	否
HashMap	数组+链表/红黑树	增删查 O(1)	否
ConcurrentHashMap	数组+CAS+同步块	增删查 O(1)	是（分段锁）
TreeMap	红黑树	增删查 O(log n)	否
PriorityQueue	二叉堆	插入/删除 O(log n)	否

---

七、关键设计思想

1. 动态扩容：

   • ArrayList/HashMap 通过扩容平衡空间与时间。

   • 扩容需重新分配内存和复制数据，尽量初始化时预估容量（如 new ArrayList<>(100)）。

2. 哈希冲突解决：

   • 开放寻址法（如 ThreadLocalMap） vs 链地址法（如 HashMap）。

   • JDK 8 的 HashMap 通过红黑树优化链表过长问题。

3. 树化与退化：

   • 红黑树保证极端情况下（哈希冲突严重）查询效率仍为 O(log n)。

   • 树化阈值（8）基于泊松分布统计，冲突概率极低时避免过度优化。

4. 并发控制：

   • ConcurrentHashMap 通过 CAS + synchronized 降低锁粒度。

   • CopyOnWriteArrayList 通过写时复制实现读操作无锁。

---

八、使用场景建议

• 随机访问多 → ArrayList。

• 频繁插入/删除 → LinkedList。

• 键值对存储 → HashMap（无需排序）或 TreeMap（需排序）。

• 高并发场景 → ConcurrentHashMap 或 CopyOnWriteArrayList。

• 任务调度 → PriorityQueue（如定时任务按时间排序）。

理解底层实现能帮助开发者避免性能陷阱（如 HashMap 未设置初始容量导致频繁扩容），并合理选择数据结构。