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) | 否 |
七、关键设计思想
-
动态扩容：
-
ArrayList/HashMap通过扩容平衡空间与时间。 -
扩容需重新分配内存和复制数据，尽量初始化时预估容量（如
new ArrayList<>(100)）。
-
-
哈希冲突解决：
-
开放寻址法（如
ThreadLocalMap） vs 链地址法（如HashMap）。 -
JDK 8 的
HashMap通过红黑树优化链表过长问题。
-
-
树化与退化：
-
红黑树保证极端情况下（哈希冲突严重）查询效率仍为
O(log n)。 -
树化阈值（
8）基于泊松分布统计，冲突概率极低时避免过度优化。
-
-
并发控制：
-
ConcurrentHashMap通过CAS+synchronized降低锁粒度。 -
CopyOnWriteArrayList通过写时复制实现读操作无锁。
-
八、使用场景建议
-
随机访问多 →
ArrayList。 -
频繁插入/删除 →
LinkedList。 -
键值对存储 →
HashMap（无需排序）或TreeMap（需排序）。 -
高并发场景 →
ConcurrentHashMap或CopyOnWriteArrayList。 -
任务调度 →
PriorityQueue（如定时任务按时间排序）。
理解底层实现能帮助开发者避免性能陷阱（如 HashMap 未设置初始容量导致频繁扩容），并合理选择数据结构。