数组 vs 链表：物理存储的底层逻辑，如何锁死 Java 集合 90% 的性能上限？

果酱带你啃java

发布于 2026-04-14 14:30:46

380

数组vs链表：物理存储的底层逻辑，如何锁死Java集合90%的性能上限？

在Java开发中，我们每天都在和ArrayList、LinkedList、HashMap这些集合打交道，但很少有人深究：为什么ArrayList查得快、插得慢？为什么HashMap要搞“数组+链表+红黑树”的混合结构？其实答案藏在最基础的数组与链表的物理存储差异里——这两种数据结构的内存布局，直接决定了Java集合的性能天花板。

本文将从内存底层讲透数组和链表的本质差异，结合Java集合的源码实现和性能实测，让你彻底搞懂“为什么集合性能会有天壤之别”，并能在实战中精准选型。

一、先搞懂：内存里的“数组”到底是什么？

数组是连续内存块上的线性存储结构，这是它最核心的特征。我们可以把内存想象成一排编号的储物柜，数组就是“一口气占了连续的N个柜子”，每个柜子里放一个元素。

1. 数组的物理存储本质

假设我们有一个int[] arr = new int[3]，在内存中它的布局是这样的：

arr[0]存放在地址0x100（假设），int类型占4字节；
arr[1]必然在0x104（0x100 + 4）；
arr[2]必然在0x108（0x104 + 4）。

这种“连续性”带来了两个关键特性：

（1）随机访问的“绝对优势”

数组的索引本质是内存地址的偏移量，通过公式元素地址 = 数组起始地址 + 索引 × 元素大小，可以O(1)时间直接定位到任意元素。比如想拿arr[100]，CPU不需要遍历，直接算地址就能取到——这就是ArrayList.get(index)快的根本原因。

（2）插入/删除的“天然缺陷”

如果要在数组中间插入元素（比如arr[1]位置插一个数），后面的arr[1]、arr[2]…都得往后挪一位，腾出空间；删除同理，后面的元素要往前补。这个“移动元素”的操作是O(n)时间——元素越多，耗时越长。

（3）固定容量与扩容开销

数组一旦创建，长度固定。Java的ArrayList之所以能“动态扩容”，是因为它底层会维护一个数组，当容量不足时：

计算新容量（默认newCapacity = oldCapacity + (oldCapacity >> 1)，即1.5倍）；
创建新数组；
把原数组的元素复制到新数组（System.arraycopy）。

这个复制过程是O(n)时间的性能开销——这也是为什么我们建议初始化ArrayList时指定容量（比如new ArrayList<>(1000)），避免频繁扩容。

二、再看透：链表的内存布局，和数组“反着来”

链表是非连续内存块上的链式存储结构，它不要求内存连续，而是靠“指针”把零散的节点串起来。每个节点包含两部分：数据域（存元素）和指针域（存下一个/上一个节点的地址）。

Java中的LinkedList是双向链表，节点结构如下（简化版）：

private static class Node<E> {
    E item;
    Node<E> next; // 后继节点指针
    Node<E> prev; // 前驱节点指针

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

1. 链表的物理存储本质

链表的节点可以散落在内存的任意位置，比如：

节点A在0x100，存着数据"a"和下一个节点B的地址0x200；
节点B在0x200，存着数据"b"和下一个节点C的地址0x305；
节点C在0x305，存着数据"c"和null（末尾）。

这种“离散性”也带来两个关键特性：

（1）随机访问的“致命短板”

想找链表的第100个元素？没有捷径——只能从头节点开始，顺着指针一个一个数，直到找到第100个。这个过程是O(n)时间——这就是LinkedList.get(index)慢到离谱的原因（哪怕是中间位置，也得遍历一半节点）。

（2）插入/删除的“绝对优势”

链表插入元素时，只需要改两个指针：

找到要插入位置的前驱节点prev和后继节点next；
让prev.next指向新节点，新节点的next指向next。

整个过程不需要移动任何元素，是O(1)时间（前提是已经找到目标节点）。删除同理，只需要把前驱节点的指针跳过要删除的节点就行。

（3）空间的“额外开销”

每个节点都要存指针，比如双向链表每个节点要多存两个引用（prev和next）——这是链表的“空间换时间”代价。

三、核心差异对比：数组vs链表，到底差在哪？

特性	数组	链表
存储方式	连续内存块	非连续内存块（节点+指针）
随机访问	O(1)（直接算地址）	O(n)（遍历指针）
插入/删除（中间）	O(n)（移动元素）	O(1)（改指针，已找到节点）
空间开销	无额外开销（仅存数据）	有额外开销（存指针）
容量特性	固定容量，需扩容	动态容量，无需扩容
缓存友好性	好（连续内存，CPU缓存命中率高）	差（离散内存，缓存命中率低）

注：CPU缓存会预加载连续的内存数据，数组的连续存储能充分利用缓存；链表的离散存储会导致缓存频繁失效——这也是数组实际运行速度比链表快的重要原因（哪怕理论复杂度相同）。

四、Java集合里的“数组与链表”：源码级拆解

1. ArrayList：纯数组实现的“查询王者”

ArrayList的底层就是一个Object[] elementData数组，核心操作的源码逻辑如下：

（1）get操作：直接索引访问

public E get(int index) {
    Objects.checkIndex(index, size); // 检查索引合法性
    return elementData(index); // 直接返回数组元素
}

E elementData(int index) {
    return (E) elementData[index]; // O(1)时间
}

（2）add操作：尾部快、中间慢

尾部添加：如果容量足够，直接elementData[size++] = e（O(1)）；
中间添加：需要System.arraycopy移动元素（O(n)）：

public void add(int index, E element) {
    rangeCheckForAdd(index); // 检查索引
    ensureCapacityInternal(size + 1); // 确保容量
    // 把index后的元素往后挪一位，空出位置
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element; // 插入新元素
    size++;
}

（3）扩容逻辑：1.5倍扩容

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新容量 = 旧容量 + 旧容量/2（右移1位等价于除以2）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 超过最大容量则用Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制原数组到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2. LinkedList：纯双向链表实现的“增删王者”

LinkedList的底层是双向链表，核心操作的源码逻辑如下：

（1）get操作：遍历找节点

public E get(int index) {
    checkElementIndex(index); // 检查索引
    return node(index).item; // 找到节点后返回数据
}

Node<E> node(int index) {
    // 优化：判断index在链表前半段还是后半段，减少遍历次数
    if (index < (size >> 1)) { // 前半段：从头开始找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else { // 后半段：从尾开始找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

哪怕是找中间节点，也得遍历size/2次——这就是LinkedList.get性能拉胯的根源。

（2）add操作：头尾快、中间慢（找节点慢）

头部添加：直接改头节点指针（O(1)）：

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

中间添加：先node(index)找节点（O(n)），再改指针（O(1)）：

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element); // 尾部添加
    else
        linkBefore(element, node(index)); // 中间添加：先找节点
}

3. HashMap：数组+链表+红黑树的“混合体”

HashMap的底层是哈希桶数组+链表（解决哈希冲突）+红黑树（优化长链表查询），它把数组和链表的优势结合到了极致：

（1）哈希桶数组：查询的“基石”

HashMap维护一个Node[] table数组（哈希桶），每个桶对应一个链表/红黑树。通过key的哈希值计算索引：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 扰动函数
}

int index = hash(key) & (table.length - 1); // 等价于取模，更高效

数组的随机访问特性，让HashMap的查询、插入、删除的平均时间复杂度达到O(1)。

（2）链表：解决哈希冲突

当两个key的哈希值计算出的索引相同时（哈希冲突），就用链表把这些节点串起来。但链表太长会导致查询变慢（O(n)），所以HashMap规定：

当链表长度≥8且数组长度≥64时，链表转为红黑树（查询时间复杂度降为O(logn)）；
当红黑树节点数≤6时，转回链表（节省空间）。

（3）扩容机制：2倍扩容

HashMap默认初始容量16，负载因子0.75。当size > capacity × loadFactor时，数组扩容为2倍——这样index = hash & (newCapacity - 1)能保持哈希分布均匀。

五、性能实测：ArrayList vs LinkedList，差距有多大？

光说不练假把式，我们用代码实测两者的核心操作性能（JDK 17，测试数据量10000，循环1000次取平均）。

1. 测试代码

package com.jam.demo.collection;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.CollectionUtils;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 数组与链表性能对比测试类
 * @author ken
 */
@Slf4j
publicclass CollectionPerformanceTest {

    privatestaticfinalint TEST_SIZE = 10000;
    privatestaticfinalint LOOP_TIMES = 1000;

    /**
     * 测试get操作性能（中间位置）
     */
    public static void testGetPerformance() {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // 初始化数据
        for (int i = 0; i < TEST_SIZE; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        // ArrayList get测试
        long arrayListGetTime = 0;
        for (int i = 0; i < LOOP_TIMES; i++) {
            long start = System.nanoTime();
            arrayList.get(TEST_SIZE / 2);
            long end = System.nanoTime();
            arrayListGetTime += (end - start);
        }
        double arrayListAvg = arrayListGetTime / (double) LOOP_TIMES;

        // LinkedList get测试
        long linkedListGetTime = 0;
        for (int i = 0; i < LOOP_TIMES; i++) {
            long start = System.nanoTime();
            linkedList.get(TEST_SIZE / 2);
            long end = System.nanoTime();
            linkedListGetTime += (end - start);
        }
        double linkedListAvg = linkedListGetTime / (double) LOOP_TIMES;

        log.info("=== Get操作（中间位置）===");
        log.info("ArrayList平均耗时：{}纳秒", arrayListAvg);
        log.info("LinkedList平均耗时：{}纳秒", linkedListAvg);
        log.info("LinkedList耗时是ArrayList的{}倍", linkedListAvg / arrayListAvg);
    }

    /**
     * 测试add操作性能（头部/尾部/中间）
     */
    public static void testAddPerformance() {
        List<Integer> arrayListHead = new ArrayList<>();
        List<Integer> linkedListHead = new LinkedList<>();
        List<Integer> arrayListTail = new ArrayList<>();
        List<Integer> linkedListTail = new LinkedList<>();
        List<Integer> arrayListMiddle = new ArrayList<>();
        List<Integer> linkedListMiddle = new LinkedList<>();

        // 初始化基础数据
        for (int i = 0; i < TEST_SIZE; i++) {
            arrayListHead.add(i);
            linkedListHead.add(i);
            arrayListTail.add(i);
            linkedListTail.add(i);
            arrayListMiddle.add(i);
            linkedListMiddle.add(i);
        }

        // 头部添加
        long arrayListHeadTime = 0;
        long linkedListHeadTime = 0;
        for (int i = 0; i < LOOP_TIMES; i++) {
            long start = System.nanoTime();
            arrayListHead.add(0, -i);
            arrayListHeadTime += (System.nanoTime() - start);

            start = System.nanoTime();
            linkedListHead.add(0, -i);
            linkedListHeadTime += (System.nanoTime() - start);
        }

        // 尾部添加
        long arrayListTailTime = 0;
        long linkedListTailTime = 0;
        for (int i = 0; i < LOOP_TIMES; i++) {
            long start = System.nanoTime();
            arrayListTail.add(i);
            arrayListTailTime += (System.nanoTime() - start);

            start = System.nanoTime();
            linkedListTail.add(i);
            linkedListTailTime += (System.nanoTime() - start);
        }

        // 中间添加
        long arrayListMiddleTime = 0;
        long linkedListMiddleTime = 0;
        for (int i = 0; i < LOOP_TIMES; i++) {
            long start = System.nanoTime();
            arrayListMiddle.add(TEST_SIZE / 2, i);
            arrayListMiddleTime += (System.nanoTime() - start);

            start = System.nanoTime();
            linkedListMiddle.add(TEST_SIZE / 2, i);
            linkedListMiddleTime += (System.nanoTime() - start);
        }

        log.info("\n=== Add操作 ===");
        log.info("头部添加 - ArrayList：{}纳秒/次 | LinkedList：{}纳秒/次",
                arrayListHeadTime / LOOP_TIMES, linkedListHeadTime / LOOP_TIMES);
        log.info("尾部添加 - ArrayList：{}纳秒/次 | LinkedList：{}纳秒/次",
                arrayListTailTime / LOOP_TIMES, linkedListTailTime / LOOP_TIMES);
        log.info("中间添加 - ArrayList：{}纳秒/次 | LinkedList：{}纳秒/次",
                arrayListMiddleTime / LOOP_TIMES, linkedListMiddleTime / LOOP_TIMES);
    }

    public static void main(String[] args) {
        testGetPerformance();
        testAddPerformance();
    }
}

2. 测试结果（示例）

=== Get操作（中间位置）===
ArrayList平均耗时：15.2纳秒
LinkedList平均耗时：8923.5纳秒
LinkedList耗时是ArrayList的587倍

=== Add操作 ===
头部添加 - ArrayList：12045.3纳秒/次 | LinkedList：32.1纳秒/次
尾部添加 - ArrayList：18.5纳秒/次 | LinkedList：25.3纳秒/次
中间添加 - ArrayList：6120.8纳秒/次 | LinkedList：4560.2纳秒/次

3. 结果分析

get操作：ArrayList完胜，LinkedList慢了近600倍——这是数组随机访问的绝对优势；
头部添加：LinkedList快（改指针），ArrayList慢（移动所有元素）；
尾部添加：ArrayList和LinkedList差不多（ArrayList容量足够时直接加）；
中间添加：LinkedList略快，但差距不大（因为找中间节点要遍历）。

六、实战场景选型：什么时候用数组？什么时候用链表？

1. 优先选ArrayList的场景

频繁查询、少增删：比如电商商品列表、用户分页数据；
遍历操作多：ArrayList的连续内存更友好，遍历速度快；
已知数据量：初始化时指定容量，避免扩容开销。

2. 优先选LinkedList的场景

频繁头尾增删：比如队列（Queue）、栈（Deque）场景（LinkedList实现了Deque接口）；
数据量动态变化大：不需要考虑扩容，内存更灵活；
中间增删极频繁且数据量小：数据量小时，LinkedList的遍历开销可以忽略。

3. HashMap的选型要点

键值对存储：HashMap是首选（平均O(1)性能）；
避免哈希冲突：重写hashCode()和equals()时要保证哈希分布均匀；
大数量场景：初始化时指定容量（比如new HashMap<>(1000)），减少扩容次数。

七、易混淆点澄清：这些坑别踩！

1. “LinkedList增删快”是有前提的

LinkedList的增删快，前提是已经找到目标节点。如果是add(int index, E e)，需要先node(index)遍历找节点——数据量大时，这个遍历的开销可能超过ArrayList的移动元素开销。

2. ArrayList的“线程不安全”问题

ArrayList不是线程安全的，多线程环境下会出现ConcurrentModificationException。解决方案：

用Vector（线程安全，但性能差，不推荐）；
用CopyOnWriteArrayList（写时复制数组，读多写少场景推荐）；
用Collections.synchronizedList(new ArrayList<>())（加锁，性能一般）。

3. 红黑树不是“万能的”

HashMap的链表转红黑树有两个条件：链表长度≥8且数组长度≥64。如果数组长度不足64，会先扩容数组，而不是转红黑树——因为扩容能更高效地减少哈希冲突。

八、总结：底层逻辑决定性能上限

Java集合的性能，从来不是“凭空设计”的——它完全依赖于数组和链表的物理存储特性：

数组的连续内存赋予了ArrayList的查询优势；
链表的指针链式结构赋予了LinkedList的增删优势；
HashMap的“数组+链表+红黑树”则是对两者优势的极致融合。

作为开发者，我们不需要死记硬背“哪个集合快”，而是要理解底层存储如何影响操作效率——这才是解决性能问题的根本。毕竟，搞懂了内存里的“柜子”是怎么摆的，才能真正选对工具、写对代码。

最后记住一句话：数据结构的物理存储，是所有性能优化的起点。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2026-02-03，如有侵权请联系 cloudcommunity@tencent.com 删除

性能

本文分享自果酱带你啃java 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

数组 vs 链表：物理存储的底层逻辑，如何锁死 Java 集合 90% 的性能上限？

数组 vs 链表：物理存储的底层逻辑，如何锁死 Java 集合 90% 的性能上限？

数组vs链表：物理存储的底层逻辑，如何锁死Java集合90%的性能上限？

一、先搞懂：内存里的“数组”到底是什么？

1. 数组的物理存储本质

（1）随机访问的“绝对优势”

（2）插入/删除的“天然缺陷”

（3）固定容量与扩容开销

二、再看透：链表的内存布局，和数组“反着来”

1. 链表的物理存储本质

（1）随机访问的“致命短板”

（2）插入/删除的“绝对优势”

（3）空间的“额外开销”

三、核心差异对比：数组vs链表，到底差在哪？

四、Java集合里的“数组与链表”：源码级拆解

1. ArrayList：纯数组实现的“查询王者”

（1）get操作：直接索引访问

（2）add操作：尾部快、中间慢

（3）扩容逻辑：1.5倍扩容

2. LinkedList：纯双向链表实现的“增删王者”

（1）get操作：遍历找节点

（2）add操作：头尾快、中间慢（找节点慢）

3. HashMap：数组+链表+红黑树的“混合体”

（1）哈希桶数组：查询的“基石”

（2）链表：解决哈希冲突

（3）扩容机制：2倍扩容

五、性能实测：ArrayList vs LinkedList，差距有多大？

1. 测试代码

2. 测试结果（示例）

3. 结果分析

六、实战场景选型：什么时候用数组？什么时候用链表？

1. 优先选ArrayList的场景

2. 优先选LinkedList的场景

3. HashMap的选型要点

七、易混淆点澄清：这些坑别踩！

1. “LinkedList增删快”是有前提的

2. ArrayList的“线程不安全”问题

3. 红黑树不是“万能的”

八、总结：底层逻辑决定性能上限

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐