跳到主要内容

Java 与数据结构

Java 的集合框架把数据结构课上的抽象类型做成了接口和实现。会用 ArrayList、HashMap 只是第一步，知道它们背后是动态数组、双向链表、桶数组 + 红黑树、环形数组和二叉堆，才能解释「为什么扩容是 1.5 倍」「为什么 HashMap 的容量是 2 的幂」「为什么 LinkedList 随机访问慢」。

1. 一张总表​

抽象数据结构Java 载体底层实现关键复杂度典型场景
动态数组ArrayListObject[] elementData + size，按 1.5 倍扩容索引 O(1)，尾部追加均摊 O(1)，中间插入/删除 O(n)结果集、列表展示
双向链表LinkedListNode 的 prev/next/item两端增删 O(1)，按下标访问 O(n)双端队列、LRU 的手写实现
哈希表HashMap桶数组 + 链表/红黑树查找/插入/删除平均 O(1)；树化后 O(log n)，未树化时最坏 O(n)配置、缓存、计数
哈希集合HashSet内部就是一个 HashMap成员判断平均 O(1)去重、集合运算
有序哈希表LinkedHashMapHashMap + 双向链表增删查平均 O(1)，可保持插入/访问顺序LRU、有序输出
红黑树TreeMap平衡二叉搜索树查找/插入/删除 O(log n)，天然有序排名、区间查询
双端队列ArrayDeque环形数组 + head/tail两端增删 O(1)栈、队列、BFS
优先队列PriorityQueue数组存储的二叉堆堆顶 O(1)，入队/出队 O(log n)Top K、任务调度
并发哈希表ConcurrentHashMapCAS + 桶级 synchronized读几乎无锁，写只锁单个桶的头节点并发缓存、计数器
写时复制列表CopyOnWriteArrayList写时复制整个数组读 O(1)，写 O(n)读多写少的监听器列表

2. ArrayList：动态数组​

2.1 内存布局​

ArrayList
  elementData ──► [ Object[0] ][ Object[1] ][ Object[2] ][ null ][ null ] ...
  size = 3

ArrayList 内部就是一个 Object[]，所以：

  • get(i) 直接算地址，O(1)；
  • add(e) 在尾部写下一个槽位，容量够就是 O(1)，不够才扩容；
  • add(index, e)、remove(index) 要把后面的元素整体移动，O(n)。

2.2 扩容：1.5 倍​

// JDK 里的核心逻辑（简化）
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);   // 1.5 倍
elementData = Arrays.copyOf(elementData, newCapacity);
  • 默认容量是 10，但第一次 add 才分配（懒加载）。
  • 按比例扩容让 n 次追加的总搬移量保持在 O(n)，所以追加是均摊 O(1)，单次触发扩容仍可能是 O(n)。
  • 已知数据量时用 new ArrayList<>(expectedSize)；构造器会按给定值精确分配初始数组，后续装满才按 1.5 倍 grow()。
List<String> list = new ArrayList<>(1000);
list.add("a");
System.out.println(list.size());        // 1
System.out.println(list.get(0));        // a

2.3 常见坑​

// 1. Arrays.asList 返回定长列表，add/remove 会抛 UnsupportedOperationException
List<Integer> fixed = Arrays.asList(1, 2, 3);
// fixed.add(4);   // 运行时异常

// 2. List.of 是不可变列表
List<Integer> immutable = List.of(1, 2, 3);
// immutable.set(0, 9);   // UnsupportedOperationException

// 3. subList 是视图，不是拷贝
List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
List<Integer> sub = list.subList(0, 2);
sub.set(0, 99);           // 原 list 也会变：list.get(0) == 99

需要独立副本时用 new ArrayList<>(list) 或 List.copyOf(list)。

3. LinkedList：双向链表​

first ──► [prev|null][item][next] ◄──► [prev][item][next] ◄──► ...
last  ────────────────────────────────────────────────────────┘
  • 每个元素是一个 Node，多存 prev、next 两个引用，内存开销比 ArrayList 大。
  • addFirst/addLast/removeFirst/removeLast 是 O(1)；
  • get(index) 要从头或尾走，O(n)；
  • 实现了 Deque，可以当栈和队列，但性能通常不如 ArrayDeque。

内存开销也要算：LinkedList 每个元素是一个 Node 对象（对象头 + item/next/prev 三个引用），ArrayDeque 只维护一个 Object[]；元素多时前者通常更费内存。

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque.pollFirst());   // 1

LinkedList 适合「频繁在两端增删、很少按下标访问」的场景；Java 里这种场景大多已经被 ArrayDeque 取代。

4. HashMap：桶数组 + 链表/红黑树​

4.1 结构​

table ──► [ bucket0 ] [ bucket1 ] [ bucket2 ] ... [ bucket15 ]
              │
              ▼
          Node(hash, key, value, next) ──► Node ──► ...
  • 默认容量 16，负载因子 0.75；元素数超过 capacity × 0.75 就扩容为 2 倍。
  • 容量始终是 2 的幂，这样 (n - 1) & hash 等价于取模，但更快。
  • 哈希扰动：(h = key.hashCode()) ^ (h >>> 16)，让高位也参与低位索引。
  • 冲突用链表；当链表长度 ≥ 8 且 table 长度 ≥ 64 时，转成红黑树；节点数降到 6 个及以下再转回链表。
  • Java 8 扩容时会把一条链表拆成 lo/hi 两条，保持相对顺序，避免旧版本的头插法成环问题。
Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.merge("a", 1, Integer::sum);        // 计数：a -> 2
map.computeIfAbsent("b", k -> 0);       // 不存在才放 0
System.out.println(map.getOrDefault("c", -1));  // -1

4.2 equals 与 hashCode 的契约​

HashMap 用 hashCode 找桶，用 equals 在桶内比较：

  • a.equals(b) 为 true，则 a.hashCode() == b.hashCode() 必须成立；
  • 重写 equals 必须重写 hashCode；
  • 作为 key 的对象在放入后不要修改参与哈希的字段，否则再也找不到。
record User(String id) {}     // record 自动生成 equals/hashCode

Map<User, String> map = new HashMap<>();
map.put(new User("1"), "alice");
System.out.println(map.get(new User("1")));   // alice

4.3 容量与性能​

HashMap 的容量是 2 的幂，构造时传的 initialCapacity 会被 tableSizeFor 向上取整。如果预估有 1000 个元素，直接 new HashMap<>(1000) 仍可能扩容，因为阈值是 capacity × 0.75；更稳妥的是 new HashMap<>((int) (1000 / 0.75f) + 1)。

4.4 线程安全​

HashMap 不是线程安全的。并发写入可能导致数据丢失、size 不准，旧版本甚至会出现链表成环。并发场景用：

  • ConcurrentHashMap：读几乎无锁，写只锁桶；
  • Collections.synchronizedMap：全表锁，简单但吞吐低；
  • 只读场景：发布后不再修改，可以安全共享。

5. HashSet、LinkedHashMap、TreeMap​

5.1 HashSet​

HashSet 内部就是一个 HashMap，元素作为 key，value 是一个固定的 PRESENT 对象。所以去重、contains 的复杂度和 HashMap 一致。

Set<String> set = new HashSet<>();
set.add("a");
System.out.println(set.contains("a"));   // true

5.2 LinkedHashMap：插入顺序与 LRU​

LinkedHashMap 在 HashMap 的节点上再加 before/after，维护一条双向链表：

  • accessOrder = false：按插入顺序遍历（默认）；
  • accessOrder = true：按访问顺序遍历，get/put 会把节点移到尾部。
class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruCache(int capacity) {
        super(capacity, 0.75f, true);   // accessOrder = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

生产环境更常用 Caffeine，但理解 LinkedHashMap 是理解 LRU 的基础。

5.3 TreeMap：红黑树​

TreeMap 用红黑树保持 key 有序，查找/插入/删除都是 O(log n)，并实现了 NavigableMap：

TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(1, "a");
tm.put(3, "c");
tm.put(5, "e");

System.out.println(tm.floorKey(4));     // 3
System.out.println(tm.ceilingKey(4));   // 5
System.out.println(tm.subMap(1, true, 5, false));  // {1=a, 3=c}

key 必须实现 Comparable，或者构造时传 Comparator；不允许 null key（自然排序时）。

6. ArrayDeque：环形数组​

ArrayDeque 用环形数组保存元素，head 指向队首，tail 指向下一个空位：

elements: [ ][b][c][d][ ][ ][ ][ ]
              ^        ^
            head      tail
  • addFirst/addLast/pollFirst/pollLast 都是 O(1)；
  • 容量不足时按 2 倍扩容；
  • 不允许 null 元素；
  • 不是线程安全的。
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop());    // 2

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.poll());   // 1

ArrayDeque 通常比 LinkedList 更快、更省内存，是 Java 里栈和队列的默认选择。

7. PriorityQueue：二叉堆​

PriorityQueue 用数组存完全二叉树，默认是小顶堆：

queue[0] 最小
left  = 2*i + 1
right = 2*i + 2
parent = (i - 1) / 2
  • offer/poll：O(log n)；
  • peek：O(1)；
  • 用集合构造器 new PriorityQueue<>(collection) 批量建堆：内部 heapify，O(n)；
  • 迭代顺序不保证有序，只有堆顶最小。
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(9);
System.out.println(minHeap.poll());   // 1

// 大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Top K：维护大小为 k 的小顶堆
PriorityQueue<Integer> topK = new PriorityQueue<>();
for (int x : nums) {
    topK.offer(x);
    if (topK.size() > k) topK.poll();
}

元素必须可比较，或者传 Comparator；不允许 null；不是线程安全的，并发场景用 PriorityBlockingQueue。

8. 并发容器​

容器特点适用
ConcurrentHashMap读无锁，写锁桶；不允许 null key/value并发缓存、计数器
CopyOnWriteArrayList写时复制整个数组，读不加锁读多写少的监听器列表
ArrayBlockingQueue有界数组队列，支持公平锁线程池任务队列、生产者-消费者
LinkedBlockingQueue链表队列，可有界高吞吐任务队列
SynchronousQueue不存储元素，直接移交newCachedThreadPool
PriorityBlockingQueue无界优先队列带优先级的任务

ConcurrentHashMap 的 computeIfAbsent 是原子的，适合做本地缓存：

ConcurrentHashMap<String, User> cache = new ConcurrentHashMap<>();
User user = cache.computeIfAbsent(id, this::loadUser);

注意：computeIfAbsent 的映射函数里不要做耗时 I/O 或递归更新同一个 map，可能长时间占住桶锁。

9. 选型决策​

需要按下标随机访问、尾部追加？       → ArrayList
需要两端增删、当栈/队列？             → ArrayDeque
需要按 key 查找、去重？               → HashMap / HashSet
需要保持插入顺序或实现 LRU？          → LinkedHashMap
需要按 key 排序、区间查询？           → TreeMap
需要每次取最小/最大？                 → PriorityQueue
需要并发读写？                        → ConcurrentHashMap
读多写少、事件监听？                  → CopyOnWriteArrayList
需要阻塞式生产者-消费者？             → BlockingQueue

Java 21 起，List/Deque 等实现了 SequencedCollection，统一提供 getFirst()、getLast()、reversed()；写新代码时可以用这组接口，不必在 list.get(0) 和 list.get(size-1) 之间来回算下标。

10. 常见坑​

  • Arrays.asList 是定长列表：add/remove 抛 UnsupportedOperationException。
  • List.of 不可变：set 也不行。
  • subList 是视图：修改子列表会影响原列表；原列表结构变化后子列表可能失效。
  • HashMap 的 key 可变：放入后修改参与哈希的字段，get 找不到。
  • 只重写 equals 不重写 hashCode：两个相等对象落到不同桶。
  • 遍历时 list.remove：抛 ConcurrentModificationException；用 Iterator.remove() 或 removeIf。
  • LinkedList 随机访问：get(i) 是 O(n)，循环里用下标访问会变成 O(n²)。
  • PriorityQueue 迭代无序：需要完整排序用 Arrays.sort 或 TreeMap。
  • ConcurrentHashMap 不允许 null：get 返回 null 不能区分「不存在」和「值为 null」。
  • 自动装箱的 ==：Integer 在 -128..127 有缓存，范围外 == 比较的是引用。

11. 动手实验​

import java.util.*;

public class CollectionLab {
    public static void main(String[] args) {
        // 1. ArrayList 扩容
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 20; i++) {
            list.add(i);
        }
        System.out.println(list.size());

        // 2. 随机访问：ArrayList vs LinkedList
        int n = 100_000;
        List<Integer> array = new ArrayList<>();
        List<Integer> linked = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            array.add(i);
            linked.add(i);
        }

        long t0 = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < n; i++) sum += array.get(i);
        long t1 = System.nanoTime();
        for (int i = 0; i < n; i++) sum += linked.get(i);
        long t2 = System.nanoTime();

        System.out.printf("ArrayList get: %.2f ms%n", (t1 - t0) / 1e6);
        System.out.printf("LinkedList get: %.2f ms%n", (t2 - t1) / 1e6);
        System.out.println(sum);

        // 3. HashMap 计数
        Map<String, Integer> freq = new HashMap<>();
        for (String s : List.of("a", "b", "a")) {
            freq.merge(s, 1, Integer::sum);
        }
        System.out.println(freq);

        // 4. 小顶堆 Top K
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int x : new int[]{5, 1, 9, 3, 7}) {
            heap.offer(x);
            if (heap.size() > 2) heap.poll();
        }
        System.out.println(heap);   // [7, 9]（顺序不保证）
    }
}

想要严肃的微基准，用 JMH，不要用 System.nanoTime() 直接下结论；JIT 预热、逃逸分析、死代码消除都会影响结果。

12. 小结​

  • ArrayList 是动态数组，扩容 1.5 倍，尾部快、中间慢。
  • LinkedList 是双向链表，两端快、随机访问慢，通常被 ArrayDeque 取代。
  • HashMap 是桶数组 + 链表/红黑树，容量为 2 的幂，负载因子 0.75；key 的 equals/hashCode 必须一致。
  • LinkedHashMap 用双向链表维护顺序，可实现 LRU；TreeMap 用红黑树保持有序。
  • ArrayDeque 是环形数组，是栈/队列的默认选择；PriorityQueue 是二叉堆，只保证堆顶最小。
  • 选型的本质是先问「数据怎么访问、怎么修改」，再找匹配的底层布局；并发场景优先用 java.util.concurrent 里的容器。
加载评论中...