Java 集合框架对比：ArrayList / LinkedList / HashMap 底层

学完这篇，你能说清 ArrayList、LinkedList、HashMap 三者的底层结构差异，并在写代码时不再凭感觉选容器。

Java 集合的面试题和线上问题，八成绕不开这三个类。很多人背过“ArrayList 查得快、LinkedList 增删快”，但真到写代码时还是会用错。下面从底层结构一层层拆开看。

第一步：ArrayList 就是会自己变长的数组

打开 java.util.ArrayList 源码，核心只有一行：

transient Object[] elementData;

所有元素都存在这个 Object[] 里。size 是实际元素个数，elementData.length 是数组容量，两者不是一回事。

容量从哪来？ 用 new ArrayList<>() 创建时，数组是空的（DEFAULTCAPACITY_EMPTY_ELEMENTDATA），并没有立刻分配 10 个格子。只有第一次 add 时才扩容到 DEFAULT_CAPACITY = 10。这叫懒加载，避免创建一堆空集合时浪费内存。

怎么扩容？ 关键在 grow()：

int newCapacity = oldCapacity + (oldCapacity >> 1); // 约 1.5 倍
elementData = Arrays.copyOf(elementData, newCapacity);

10 → 15 → 22 → 33……每次扩容都要把老数组整个复制一遍，Arrays.copyOf 底层是 System.arraycopy，是内存级拷贝，但元素多了照样有成本。

所以：

• get(index) 直接 elementData[index]，O(1)
• 尾部 add 均摊 O(1)
• 中间 add(index, e) 或 remove(index) 要 System.arraycopy 挪动后面所有元素，O(n)

注意：如果能预估元素数量，就写 new ArrayList<>(1000)。这一行能省掉十几轮扩容和数组复制，是性价比最高的优化之一。

注意：ArrayList 有 modCount 做 fail-fast 检查。用 for-each 遍历时调 list.remove() 会抛 ConcurrentModificationException，要用 Iterator.remove() 或 removeIf()。

第二步：LinkedList 是双向链表，不是“更快的 List”

LinkedList 的节点长这样：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

每个元素都包在一个 Node 里，多出两个引用（前后指针）。同样存 100 万个 Integer，LinkedList 的内存占用明显高于 ArrayList。

它真的增删快吗？ 要看增删发生在哪里。addFirst / addLast / removeFirst 是 O(1)，因为 first、last 两个指针直接定位。但 add(index, e) 得先找到位置，get(index) 也得从头或尾遍历：

Node<E> node(int index) {
    if (index < (size >> 1)) { // 前半段从头找
        ...
    } else {                   // 后半段从尾找
        ...
    }
}

所以 list.get(500000) 这种操作是 O(n)。**“LinkedList 增删快”说的是已经拿到节点引用的场景，而 List 接口根本给不了你节点引用。**

另外，链表节点在堆上分散分配，CPU 缓存命中率差；ArrayList 连续内存对缓存友好。实际压测中，ArrayList 在中间插入时经常反超 LinkedList。

注意：LinkedList 同时实现了 Deque，需要队列或栈时用它（offer/poll/push/pop）才是它真正的主场，别拿它当随机访问的 List 用。

第三步：HashMap 是数组 + 链表 + 红黑树

JDK 8 之后，HashMap 的 table 是一个 Node<K,V>[] 数组，每个槽位挂一条链表，链表过长会转成红黑树。

下标怎么算？ 两步：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 定位：tab[(n - 1) & hash]

高 16 位异或到低 16 位，叫扰动函数，目的是让高位也参与运算，减少碰撞。因为数组长度 n 总是 2 的幂，(n-1) & hash 等价于取模但快得多。

什么时候树化？ 链表长度达到 TREEIFY_THRESHOLD = 8 时，会先检查数组长度：如果 table.length < 64，优先 resize() 扩容而不是树化（扩容能打散冲突）；长度够 64 才真正转红黑树。反过来，树节点数量降到 6 以下会退化成链表。

扩容规则： 默认容量 16，负载因子 0.75，threshold = capacity * loadFactor，元素超过 12 个就扩容到 32，容量翻倍。JDK 8 扩容时用 loHead/hiHead 把链表拆成两条，元素要么留在原位置，要么移动到「原位置 + 旧容量」，不需要重新计算 hash。

注意：JDK 7 的 HashMap 在并发扩容时用头插法，会形成环形链表导致 CPU 打满 100%。JDK 8 改成尾插修掉了环，但 HashMap 依然不是线程安全的，并发场景请用 ConcurrentHashMap。

注意：key 必须用不可变对象（String、Integer 这类），并且如果自定义类做 key，一定要正确重写 hashCode() 和 equals()。用可变对象当 key 且改了字段，等于把自己埋进槽位里再也找不回来。

第四步：怎么选，一张表看完

具体建议：

• 90% 的 List 场景用 ArrayList，包括读多写少、甚至中等频率的中间插入
• 需要队列/栈语义、频繁头尾操作，用 LinkedList（或 ArrayDeque，通常更快）
• 按 key 存取用 HashMap；如果 key 是枚举，用 EnumMap 更省内存；如果 key 是整数且范围集中，考虑数组或 IntStream 思路
• 并发场景：ConcurrentHashMap、CopyOnWriteArrayList

小结

• ArrayList 底层是 Object[]，无参构造不分配空间，首次 add 才到 10，扩容约 1.5 倍，扩容靠数组复制
• ArrayList 的瓶颈是中间插入删除的元素搬移，不是“容量满了”
• LinkedList 是双向链表，get(index) 会折半遍历，随机访问 O(n)，它的优势在头尾操作
• HashMap 定位靠 (n-1) & hash，hash 经过高 16 位扰动；容量恒为 2 的幂
• 树化门槛是链表长度 8 且 数组长度 ≥ 64，退化阈值是 6
• HashMap 非线程安全，JDK 7 头插法成环是老版本的经典事故
• 预估容量、用不可变对象做 key，是两个最省事的实践