先分两大块：

  1. 底层物理数据结构（计算机基础：数组、链表、栈、队列、哈希表、树、跳表）
  2. Java 集合封装好的数据结构（基于上面底层封装，开发直接用：List/Set/Queue/Map）

一、基础物理底层数据结构（所有集合的根基）

1. 数组 Array

特点
  1. 一段连续内存，下标随机访问 O (1)；
  2. 长度固定，不能自动扩容；
  3. 中间插入 / 删除需要整体移位，效率低 O (n)；
  4. 支持重复元素、有序。
通俗例子

电影院一排连续座位，座位号就是下标，找座位直接报号很快；但中间有人离场，后面所有人要往前挪。

java

运行

public class ArrayDemo {
    public static void main(String[] args) {
        // 固定长度数组，只能存3个
        int[] arr = new int[3];
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;

        // 随机访问极快
        System.out.println(arr[1]); // 20

        // 缺点：长度固定，存第4个直接报错
        // arr[3] = 40; // ArrayIndexOutOfBoundsException
    }
}

2. 链表 LinkedList（单向 / 双向链表）

特点
  1. 内存不连续，每个节点存「数据 + 下一个节点地址」；
  2. 无固定长度，随时新增删除；
  3. 头尾增删 O (1)，根据下标查找 O (n)；
  4. 双向链表可向前、向后遍历。
通俗例子

一串珠子，每颗珠子连着下一颗，拿掉中间一颗只需要改前后两颗的连线，不用移动整串；但想找到第 5 颗珠子必须从头一颗一颗数。

java

运行

// 手写单向链表节点
class Node {
    int val;
    Node next;
    Node(int val) { this.val = val; }
}

public class LinkDemo {
    public static void main(String[] args) {
        // 1 -> 2 -> 3
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        n1.next = n2;
        n2.next = n3;

        // 遍历链表，必须从头开始
        Node cur = n1;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }
}

3. 栈 Stack（后进先出 LIFO）

特点

只允许一端存、一端取，最后放进去的最先拿出来。 操作：push 入栈、pop 出栈、peek 查看栈顶。

通俗例子

快递箱子堆叠：最后放上去的箱子，要先拿出来才能碰下面的；浏览器前进后退、函数调用栈。

java

运行

import java.util.ArrayDeque;

public class StackDemo {
    public static void main(String[] args) {
        // 官方推荐ArrayDeque代替老旧Stack类
        ArrayDeque<String> stack = new ArrayDeque<>();
        stack.push("页面1");
        stack.push("页面2");
        stack.push("页面3");

        System.out.println("当前栈顶：" + stack.peek()); // 页面3
        System.out.println("取出：" + stack.pop()); // 页面3
        System.out.println("取出：" + stack.pop()); // 页面2
    }
}

4. 队列 Queue（先进先出 FIFO）

特点

一端存（队尾）、一端取（队头），先放进去的先消费。

通俗例子

排队打饭，先来的人先打饭；消息队列、线程池任务排队。

java

运行

import java.util.ArrayDeque;

public class QueueDemo {
    public static void main(String[] args) {
        ArrayDeque<String> queue = new ArrayDeque<>();
        queue.offer("顾客A");
        queue.offer("顾客B");
        queue.offer("顾客C");

        System.out.println(queue.poll()); // 顾客A 先排队先走
        System.out.println(queue.poll()); // 顾客B
    }
}

5. 哈希表 Hash Table

特点

底层 = 数组 + 链表 / 红黑树； 通过哈希函数把 key 换算成数组下标，读写接近 O (1)； 存在哈希碰撞（多个 key 算出同一个下标，用链表挂载）。

通俗例子

储物柜：每个钥匙 (key) 对应一个柜子编号 (哈希值)，直接找到柜子；两把钥匙分到同一个柜子就放一层链表。 Java 中 HashMap、HashSet 底层都是哈希表。

6. 树 Tree（重点：二叉树、二叉搜索树、红黑树）

6.1 普通二叉树

每个节点最多两个子节点（左、右）。

6.2 二叉搜索树 BST

左子树全部 <当前节点，右子树全部> 当前节点；中序遍历有序。 缺陷：极端情况退化成链表，查询变慢。

6.3 红黑树（平衡二叉搜索树）

自平衡，左右子树高度差不会太大，查询 / 插入 / 删除稳定 O (logn)； TreeMap、TreeSet、HashMap 扩容后链表过长都会转为红黑树。

通俗例子

有序字典，二分查找，找中间值快速缩小范围。

7. 跳表 SkipList

多层有序链表，相当于给普通链表建立多层 “索引”； 查询效率媲美红黑树，插入删除更简单，无锁并发友好； 对应集合：ConcurrentSkipListMap / ConcurrentSkipListSet。

二、Java 封装好的集合数据结构（开发直接使用）

分两大类：Collection 单列集合（存单个对象）、Map 双列集合（键值对）

（一）List 列表：有序、可重复、带索引

底层：动态数组 / 双向链表

1. ArrayList 动态数组

底层：Object 数组，自动 1.5 倍扩容 适用：查询多、遍历多、尾部新增，极少中间删插

java

运行

import java.util.ArrayList;

public class ArrayListTest {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("苹果");
        list.add("香蕉");
        list.add("橘子");

        // 根据下标快速查询
        System.out.println(list.get(0));
        // 尾部添加效率极高
        list.add("葡萄");
        System.out.println(list);
    }
}

2. LinkedList 双向链表

底层：双向链表 适用：频繁头部 / 尾部增删，很少按下标查询；可做队列、栈

java

运行

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.addFirst(1); // 头部插入快
        list.addLast(99); // 尾部插入快
        System.out.println(list);
    }
}

3. CopyOnWriteArrayList 写时复制数组

底层：数组，修改时复制新数组，读不加锁，线程安全 适用：并发场景，读多写极少（系统白名单、常量配置）

java

运行

import java.util.concurrent.CopyOnWriteArrayList;

public class CopyListTest {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> whiteIp = new CopyOnWriteArrayList<>();
        whiteIp.add("127.0.0.1");
        // 多线程并发读取无并发修改异常
        new Thread(() -> System.out.println(whiteIp.contains("127.0.0.1"))).start();
    }
}

4. Vector（过时）

同步动态数组，所有方法加synchronized，性能差，新项目禁用。

（二）Set 集：不可重复，无索引

依靠 hashCode+equals 去重

1. HashSet 哈希表（无序）

底层：HashMap 哈希表，存取顺序不一致，允许 1 个 null 场景：批量数据去重、判断元素是否存在

java

运行

import java.util.HashSet;

public class HashSetTest {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();
        set.add(10);
        set.add(20);
        set.add(10); // 重复自动丢弃
        System.out.println(set); // [10,20] 无序
    }
}

2. LinkedHashSet 哈希表 + 双向链表（插入有序）

场景：去重同时保留插入顺序

java

运行

import java.util.LinkedHashSet;

public class LinkedHashSetTest {
    public static void main(String[] args) {
        LinkedHashSet<String> log = new LinkedHashSet<>();
        log.add("登录");
        log.add("下单");
        log.add("登录");
        System.out.println(log); // [登录, 下单] 和插入顺序一致
    }
}

3. TreeSet 红黑树（自动排序）

场景：自动排序、区间筛选、排行榜

java

运行

import java.util.TreeSet;

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet<Integer> score = new TreeSet<>();
        score.add(85);
        score.add(60);
        score.add(95);
        System.out.println(score); // [60,85,95] 自动升序
        System.out.println(score.last()); // 最高分95
    }
}

4. ConcurrentSkipListSet 跳表（并发有序 Set）

多线程环境需要有序去重数据时使用。

（三）Queue / Deque 队列、双端队列

1. ArrayDeque 循环数组（栈 / 普通队列首选）

性能比 LinkedList 高，不允许 null

java

运行

import java.util.ArrayDeque;

public class ArrayDequeTest {
    public static void main(String[] args) {
        // 队列用法
        ArrayDeque<String> queue = new ArrayDeque<>();
        queue.offer("任务1");
        queue.offer("任务2");
        System.out.println(queue.poll()); // 任务1

        // 栈用法
        ArrayDeque<String> stack = new ArrayDeque<>();
        stack.push("首页");
        stack.push("详情页");
        System.out.println(stack.pop()); // 详情页
    }
}

2. PriorityQueue 优先队列（最小堆）

不是 FIFO，按自定义优先级取出，用于 TopK、任务优先级调度

java

运行

import java.util.PriorityQueue;

public class PriorityQueueTest {
    public static void main(String[] args) {
        // 默认小顶堆，数字小优先取出
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(5);
        pq.add(1);
        pq.add(3);
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " "); // 1 3 5
        }
    }
}

3. 并发阻塞队列（多线程生产者消费者）

  1. ArrayBlockingQueue：有界固定长度阻塞队列
  2. LinkedBlockingQueue：无界 / 有界链表阻塞队列（线程池默认）
  3. DelayQueue：延迟队列（订单超时、定时清理）
  4. ConcurrentLinkedQueue：无锁 CAS 高并发非阻塞队列

（四）Map 键值对存储，Key 唯一

1. HashMap 哈希表（单线程首选，无序）

key 允许 1 个 null，读写 O (1)，非线程安全

java

运行

import java.util.HashMap;

public class HashMapTest {
    public static void main(String[] args) {
        HashMap<Long, String> userMap = new HashMap<>();
        userMap.put(1001L, "小明");
        userMap.put(1002L, "小红");
        System.out.println(userMap.get(1001L)); // 小明
    }
}

2. LinkedHashMap 哈希 + 双向链表（插入有序 / LRU 缓存）

java

运行

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheTest {
    public static void main(String[] args) {
        // LRU缓存，最多存2个，淘汰最久未访问
        Map<String, String> cache = new LinkedHashMap<>(2, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > 2;
            }
        };
        cache.put("k1", "v1");
        cache.put("k2", "v2");
        cache.get("k1"); // k1变为最新访问
        cache.put("k3", "v3"); // 淘汰k2
        System.out.println(cache); // {k1=v1, k3=v3}
    }
}

3. TreeMap 红黑树（key 自动排序）

支持区间查询，key 不能为 null

java

运行

import java.util.TreeMap;

public class TreeMapTest {
    public static void main(String[] args) {
        TreeMap<Integer, String> levelMap = new TreeMap<>();
        levelMap.put(80, "良好");
        levelMap.put(60, "及格");
        levelMap.put(90, "优秀");
        System.out.println(levelMap); // 按键升序
    }
}

4. ConcurrentHashMap 并发哈希表（多线程 Map 首选）

线程安全，性能远超老旧 Hashtable，key/value 不允许 null

java

运行

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentMapTest {
    public static void main(String[] args) throws InterruptedException {
        ConcurrentHashMap<Integer, String> onlineUser = new ConcurrentHashMap<>();
        // 多线程并发写入不会报错
        new Thread(() -> onlineUser.put(1, "用户1")).start();
        new Thread(() -> onlineUser.put(2, "用户2")).start();
        Thread.sleep(100);
        System.out.println(onlineUser);
    }
}

5. ConcurrentSkipListMap 跳表（高并发有序 Map）

多线程场景需要有序键值映射使用。

6. Properties 配置文件专用 Map

继承 Hashtable，只存字符串，读取.properties配置文件。

三、所有数据结构选型极简总结

  1. 简单有序列表、查询多 → ArrayList
  2. 频繁头尾增删、队列栈 → ArrayDeque / LinkedList
  3. 去重无序 → HashSet；去重有序 → LinkedHashSet；去重排序 → TreeSet
  4. 普通键值缓存单线程 → HashMap；有序键值 → LinkedHashMap；排序键值 → TreeMap
  5. 多线程读写 Map → ConcurrentHashMap
  6. 任务按优先级执行 → PriorityQueue
  7. 多线程排队生产消费 → ArrayBlockingQueue
  8. 延迟过期任务 → DelayQueue
  9. 并发读多写少列表 → CopyOnWriteArrayList
  10. 高并发且需要有序集合 → ConcurrentSkipListSet / ConcurrentSkipListMap
# java # 数据结构 # 开发语言
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

WRF2405S-10WR2 与钡特电源 WF10-24S05S 国产工业 DC-DC 模块电源参数规格全拆解

avatar 亚马逊云科技技术品牌专区
cover

人工智能服务器PCB选型避坑指南：猎板工程师实测解析

avatar 亚马逊云科技技术品牌专区
cover

现有的GPU硬件，可以创造出真正的人工智能吗？

avatar 亚马逊云科技技术品牌专区