从数组到集合：一篇文章搞懂Java数据结构的核心奥秘（万字讲解）

数据结构中表和集合有什么联系

在数据结构中，表（List）和集合（Set）都是用于存储和组织数据的基本结构，它们在概念上有明显的区别，但也存在紧密的联系。

简单来说，集合在数学逻辑上是一种特殊的表，但在计算机的实现中，集合通常是通过表（或其他更复杂的数据结构）来构建的。

下面从几个维度详细拆解它们的联系与区别：

1. 核心区别：定义与约束

• 表（List）：关注顺序与可重复性
  • 定义：一个有序的序列，元素按照插入的顺序（或指定的索引）排列。
  • 核心特征：
    1. 有序：每个元素都有一个确定的位置（索引）。
    2. 可重复：同一个值可以在表中出现多次。
    3. 操作：通常支持通过索引访问、在任意位置插入或删除。
  • 生活中的例子：购物清单（牛奶可以买两瓶，且记录的顺序重要）。
• 集合（Set）：关注唯一性与成员关系
  • 定义：一个包含互不相同元素的集。
  • 核心特征：
    1. 无序：大多数集合的实现（如数学意义上的集合）不关心元素的顺序，只关心元素是否在里面。不过也有有序集合（如LinkedHashSet）。
    2. 唯一性：不允许重复元素。
    3. 操作：核心是增删查以及集合运算（并集、交集、差集）。
  • 生活中的例子：身份证号码库（不允许重复，且通常不关心入库的顺序）。

2. 内在联系：集合是表的约束与抽象 尽管它们用途不同，但在数据结构的世界里，它们的关系非常紧密：

1. 集合是去重后的表
   • 如果你把一个表里所有重复的元素去掉，不考虑顺序，它就变成了一个集合。因此，集合可以看作是施加了“唯一性约束”的表。
   • 技术实现：很多编程语言提供的集合库，其底层实现依赖于我们熟悉的表结构。例如：
     • 基于哈希表的集合（如 HashSet）：内部其实是一个哈希表（一种特殊的“键-值”对表），只利用键的部分来存储元素。
     • 基于树的集合（如 TreeSet）：内部是一棵平衡树（如红黑树），这也可以看作是一种具有排序功能的特殊链表变种。
2. 表是集合的基础容器
   • 很多集合在初始化的过程中，经常需要一个表作为输入源。例如：Set<String> mySet = new HashSet<>(myList);。这行代码的本质就是把一个表（myList）转换成了一个集合（去除了重复，并打乱了顺序）。
3. 有序集合是两者的桥梁
   • 有一种数据结构叫有序集合，它试图结合两者的优点：既保持元素的唯一性（集合特性），又能按照某种规则（如插入顺序或自然排序）遍历元素（表特性）。
   • 例如 Java 的 LinkedHashSet 或 Python 3.7+ 的 dict（以及基于此的集合），它们在内部使用了哈希表 + 双向链表（一种表结构）来实现。

3. 联系对比表

总结

表和集合不是互斥的概念，而是处于不同抽象层次的数据结构。

• 表 更侧重于存储形态（怎么排列，怎么访问）。
• 集合 更侧重于逻辑约束（不能重复，是否属于）。

在计算机中，我们往往利用表的具体物理存储方式（数组、链表）作为砖瓦，去构建出符合集合数学定义的房屋。

在java中的数据结构体现

我们之所以在Java中没听说过“表”这个概念，根本原因在于：在Java的官方容器框架（Collection Framework）中，并没有一个直接叫做“表”的接口或类。 我们听到的“表”其实来自于数据结构理论这个通用领域。 简单来说，数据结构是教科书语言，Java集合框架是编程语言实现。 它们在命名上存在一个“翻译”或“映射”的过程。 下面详细解释一下这个映射关系：

1. 理论上的“表”对应Java中的“列表” 在数据结构理论中，我们讨论线性表（List）。而在Java中，用来实现线性表的就是 java.util.List 接口以及它的实现类。

• 数据结构理论叫法：线性表（简称表）
• Java中的名字：List（列表）

所以，我们天天用的 ArrayList、LinkedList，在数据结构教科书里，就是表的两种具体实现方式。

• ArrayList：教科书里叫顺序表（基于数组实现）。
• LinkedList：教科书里叫链表（基于节点链接实现）。

2. Java中的“集合”有广义和狭义之分 你提到的Java中的“集合”，其实包含两个层面的意思：

• 广义的集合 （Collection）：
  • 指整个Java集合框架（Collection Framework）。它包含了List、Set、Queue、Map等所有用于存储对象的容器。这是你平时最常说的“Java集合”。
• 狭义的集合 （Set）：
  • 特指 java.util.Set 接口。这就是我们上一轮对话中讨论的那个强调唯一性的数据结构。

3. 用一张图看懂Java中的关系

如果你把Java的集合框架（广义）画出来，就一目了然了：

text

Collection （接口，广义集合的根）
│
├── List （接口）  <—— 这就是数据结构理论里的 “线性表”
│    ├── ArrayList  （顺序表）
│    └── LinkedList （链表）
│
├── Set （接口）   <—— 这就是数据结构理论里的 “集合”
│    ├── HashSet    （基于哈希表的集合）
│    └── TreeSet    （基于树的集合）
│
└── Queue （接口）  <—— 队列，也是一种特殊的线性表
     └── ...

关键点：

• List 就是你要找的那个“表”。
• Set 就是那个强调唯一的“集合”。
• 它们都继承自共同的父接口 Collection。

4. 为什么Java要这样命名？

• 历史原因：Java在设计之初，为了更贴近开发者的理解，采用了 List（列表）这个名称，而不是更学术化的“表”。列表听起来更直观，就是一系列项目的罗列。
• 避免混淆：如果Java里既有 Set，又有一个叫 Table 的东西，可能会和数据库的“表”或者GUI的“表格”混淆。而 List 在编程中是一个非常通用且无歧义的术语。

总结 当你在Java文档中看到 java.util.List 时，它就是数据结构理论中线性表的Java实现。

• 你的疑惑：“Java里只有集合，没有表？”
• 实际情况：Java的集合（Collection）是一个大家庭。在这个家庭里：
  • List 扮演着“表”的角色（有序、可重复）。
  • Set 扮演着“集合”的角色（无序、唯一）。

所以，我们其实一直在使用“表”，只是它在Java中的身份证名字叫 List 而已。

1. 核心概念：什么是“表的简单数组实现”？

一句话解释：就是用数组这种结构，去实现表（List）这种接口的功能。

• 数组：是存储在连续内存空间中的一组数据。它的特点是长度固定（一旦创建，大小不能变），但访问速度极快（通过下标直接定位）。
• 表（List）：是一种抽象的数据结构，要求能存储一系列元素，并且支持增加、删除、修改、查询等操作。它不关心底层是怎么存的，只关心能做什么。
• 简单数组实现：意思就是——在底层用一个数组来装数据，然后通过编写代码逻辑，让这个原本固定长度的数组，看起来像一个可以无限伸缩、可以在中间插入删除的“表”。

2. 在 Java 中的具体对应：ArrayList

在 Java 中天天用的 ArrayList，就是“表的简单数组实现”最典型的例子。

// 你平时用的这个，就是“表的数组实现”
ArrayList<String> list = new ArrayList<>();

它的内部原理大致是这样：

1. 底层存储：它内部维护了一个 Object[] elementData 数组。
2. 自动扩容：当你往里面添加元素，数组满了怎么办？
   • ArrayList 会新创建一个更大的数组（比如原数组的 1.5 倍），然后把旧数组里的所有数据复制到新数组里，最后把新数组赋值给底层的数组变量。
   • 对你（使用者）来说，你完全感觉不到这个“换数组”的过程，你只觉得这个“表”可以无限加东西。
3. 操作的实现：
   • 查（get）：直接返回 elementData[index]。非常快，这就是数组的优势。
   • 增/删（add/remove）：如果在中间插入或删除，需要把插入点后面的所有元素，统统往后（或往前）移动一位。这比较慢，因为涉及到大量元素的移动。

3. 数组、集合、表三者的关系图解

为了帮你理清这三者的关系，我们可以把它们放在一个坐标轴上看：

它们三者的联系可以这样理解：

• 联系 1：集合包含表
  • Java 的集合框架（Collection）是一个大家族。这个家族里有三兄弟：大哥 List（表）、二哥 Set（集）、三弟 Queue（队列）。
  • 所以，表（List）只是 Java 集合框架中的一个分支。
• 联系 2：数组是表的“建筑材料”
  • ArrayList（表的一种）在底层就是用数组盖起来的。
  • HashSet（集合的一种）在底层是用哈希表（一种特殊的数组+链表）盖起来的。
  • 所以，数组是最基础的砖块，集合（包括表）是利用这些砖块搭建出来的、功能更强大的房子。
• 联系 3：数组可以看作“裸奔”的表
  • 如果你非要较真，一个普通的数组 String[] arr = new String[10]，其实也勉强算是一种“表”——它是一种功能受限的、原始的表。
  • 它具备表的基本特征：有序、有索引。
  • 但它功能太弱了：不能自动扩容，没有 add、remove 这些方便的方法。所以 Java 才在集合框架里帮我们封装了 ArrayList，让你用得更顺手。

总结

• 表的简单数组实现：就是用数组这种底层结构，通过代码逻辑（如扩容、移动元素）来模拟出表的行为。在 Java 里就是 ArrayList。
• 数组 vs 集合：数组是工具，集合是工具箱。数组只管存数据，集合在数组的基础上提供了丰富的操作方法。
• 数组 vs 表 vs 集合：
  • 数组是原材料。
  • 表是设计图纸（接口）。
  • 集合是装满各种工具（包括表）的仓库。

1. 什么是链表？

链表也是一种数据结构，用来存储一系列的元素（也就是实现“表”的功能）。但它存储元素的方式和数组截然不同。

• 数组：在内存里找一块连续的空间，把元素一个一个挨着放进去。
• 链表：在内存里零散地放元素，每个元素节点里都存着下一个节点在哪里的“线索”，通过这个线索把它们串起来。

生活中的例子：

• 数组：像电影院的连座，大家挨着坐，座位号是连续的。你要找第5排的人，直接走过去就行。
• 链表：像寻宝游戏。你找到第一个人，他告诉你第二个人在哪儿；你找到第二个人，他告诉你第三个人在哪儿……你必须从第一个人开始，一个一个问下去，才能找到最后那个人。

链表 vs 数组（ArrayList）：有什么不一样？

这是面试常考题，也是理解数据结构的关键。我们来对比一下：

回到之前的三个概念：数组、集合、表

现在可以把链表也放进那张关系图里了：

• 数组：原材料之一（连续内存）。
• 链表：原材料之二（零散内存 + 指针）。
• 表 （List接口）：设计图纸（要求有顺序，能存重复元素）。
• 集合框架：大仓库。

在这个大仓库里：

• ArrayList：是用数组这种原材料造出来的“表”。
• LinkedList：是用链表这种原材料造出来的“表”。

它们俩都实现了 List 接口，所以它们都能当“表”来用，都能存东西、取东西。但因为原材料不同，所以性能特点截然不同。

总结

• 链表是另一种实现“表”的方式。
• 它在 Java 里的名字叫 LinkedList。
• 它的核心优势是插入和删除快（不需要移动元素，只需要改指针）。
• 它的劣势是查找慢（需要从头遍历）。
• 它和你之前问的数组、集合的关系是：数组和链表是实现“表”的两种底层手段，而“集合”是包含这两者的容器框架。

在java中 ArrayList 既是集合又不是集合？

1. 广义的集合（大写的 Collection）

在 Java 官方文档和日常开发中，所有放在 java.util 包里的这些容器，都叫"集合框架"。

java

// 这些都是"集合"（广义）
ArrayList<String> list = new ArrayList<>();     // ✅ 是集合
HashSet<String> set = new HashSet<>();          // ✅ 是集合
LinkedList<String> queue = new LinkedList<>();  // ✅ 是集合
HashMap<String, String> map = new HashMap<>();  // ✅ 虽然不是Collection的子接口，但也属于集合框架

在这个意义上，ArrayList 绝对是集合——它是集合框架的重要成员。

2. 狭义的集合（小写的 Set）

但在数据结构理论中，我们区分两种不同的逻辑结构：

• List（表/列表）：有序、可重复
• Set（集合）：无序、不可重复

在这个意义上：

java

ArrayList<String> list = new ArrayList<>();  // 这是 List（表），不是 Set（集合）
HashSet<String> set = new HashSet<>();       // 这才是 Set（集合）

二、用一张图看懂 Java 的继承体系

Iterable (接口)
    │
    └── Collection (接口)  <—— 这就是"广义集合"的根
         ├── List (接口)      <—— 表/列表
         │    ├── ArrayList   <—— 表的数组实现
         │    └── LinkedList  <—— 表的链表实现
         │
         ├── Set (接口)       <—— 狭义的集合
         │    ├── HashSet
         │    └── TreeSet
         │
         └── Queue (接口)     <—— 队列
              └── ...

关键点：

• ArrayList 继承自 List 接口
• List 继承自 Collection 接口
• 所以：ArrayList 是 Collection 的子子孙孙

三、打个比方帮你理解

把这个关系想象成一个家族谱系：

• Collection：是整个家族的姓氏（所有容器都姓 Collection）
• List：是大房这一支（特点是按顺序排）
• Set：是二房这一支（特点是孩子都是独一无二的）
• ArrayList：是 List 这支的一个具体孩子

所以：

• 问：ArrayList 是 Collection 家族的吗？ ✅ 是
• 问：ArrayList 是 List 这一支的吗？ ✅ 是
• 问：ArrayList 是 Set 那一支的吗？ ❌ 不是

四、为什么会有这种混淆？

这其实是术语在不同语境下的含义不同造成的：

五、总结一下

你之所以会觉得混淆，是因为：

1. 在 Java 技术语境中：ArrayList 是集合框架的一部分，所以大家都叫它"集合类"
2. 在数据结构理论中：ArrayList 是List（表），不是 Set（集合）

所以最准确的说法是： ArrayList 是 Java 集合框架中的一个 List 接口的实现类。 这样说既承认了它是集合家族的一员，又准确指出了它实际上是"表"而不是"数学集合"。

Java Collection API 中的“表”就是 List

在 Java 的官方集合框架（Collection API）中，并没有一个叫做“Table”或“表”的接口。数据结构理论中的“表”，在 Java 里对应的就是 List 接口。 也就是说：

• 理论术语：线性表（简称表）
• Java术语：List（列表）

List 在 Java Collection API 中的准确定义

打开 Java 官方文档，List 的定义是这样的：

List 是一个有序的集合（sequence）。用户可以精确控制列表中每个元素的插入位置，可以通过整数索引访问元素，并且可以搜索列表中的元素。

核心特征：

1. 有序：元素按照插入的顺序排列
2. 可重复：相同的元素可以出现多次
3. 有索引：可以通过下标访问（如 list.get(0)）

List 在 Collection API 中的位置

text

Java Collection API 结构
│
├── Collection (接口)
│   ├── List (接口)  <—— 这就是你要找的"表"
│   │   ├── ArrayList
│   │   ├── LinkedList
│   │   ├── Vector (古老实现)
│   │   └── Stack
│   │
│   ├── Set (接口)
│   │   └── ...
│   │
│   └── Queue (接口)
│       └── ...
│
└── Map (接口，独立分支)
    └── ...

List 的两种主要实现

在 Java Collection API 中，List 接口有两大经典实现，对应了数据结构中表的两种底层实现方式：

1. ArrayList —— 表的数组实现

java

List<String> list = new ArrayList<>();

• 底层：动态数组
• 特点：查得快，改得慢（中间插入/删除需要移动元素）
• 对应：数据结构中的顺序表

2. LinkedList —— 表的链表实现

java

List<String> list = new LinkedList<>();

• 底层：双向链表
• 特点：插入/删除快，查得慢（需要遍历）
• 对应：数据结构中的链表

为什么 Java API 不直接叫“Table”？

这是一个很好的观察。Java 在设计命名时，选择了更贴近程序员日常语言的词汇：

如果 Java 里既有 Set，又有一个叫 Table 的接口，可能会和数据库的"表"或者 GUI 的"表格"（如 JTable）混淆。而 List 在编程中是一个非常通用且无歧义的术语。

实际开发中怎么用 List

既然 List 就是 Java 里的表，那我们在日常开发中就是这样用的：

java

// 创建一个表（列表）
List<String> students = new ArrayList<>();

// 表的操作
students.add("张三");     // 添加元素
students.add("李四");
students.add("王五");
students.add(1, "赵六");  // 在指定位置插入
String name = students.get(0);  // 通过索引访问
students.remove(2);       // 删除元素

// 遍历表
for (String s : students) {
    System.out.println(s);
}

一句话总结

在 Java Collection API 的语境下：

"表"就是 List 接口，它定义了有序、可重复、有索引的元素序列。而 ArrayList 和 LinkedList 是这张表的两种具体实现方式。

当你看到 List、ArrayList、LinkedList 这些词时，就可以把它们理解为 Java 世界里的"表"。

List 的核心特点

ArrayList 类（表的数组实现）

是什么？

ArrayList 是 List 接口的数组实现。底层用一个动态数组来存储元素。

java

// 创建 ArrayList
List<String> list = new ArrayList<>();  // 默认容量10
List<String> list2 = new ArrayList<>(100);  // 指定初始容量

特点总结

适用场景

• ✅ 频繁查找、随机访问（如排行榜、数据展示）
• ✅ 主要在尾部添加/删除
• ❌ 频繁在中间插入/删除

三、LinkedList 类（表的链表实现）

是什么？

LinkedList 是 List 接口的链表实现。底层用双向链表来存储元素。

java

// 创建 LinkedList
List<String> list = new LinkedList<>();
// LinkedList 还实现了 Queue 接口，所以也可以当队列用
Queue<String> queue = new LinkedList<>();
Deque<String> deque = new LinkedList<>();  // 双端队列

特点总结

适用场景

• ✅ 频繁在头部或尾部操作（如队列、栈）
• ✅ 频繁在中间插入/删除（一旦找到位置）
• ❌ 频繁随机访问（查找太慢）

ArrayList vs LinkedList 对比表

内部类：

一句话总结

内部类就是把一个类定义在另一个类内部，主要有四种形式：

• 成员内部类：像成员变量一样，可以访问外部类所有成员
• 静态内部类：像静态成员，只能访问外部类静态成员
• 局部内部类：定义在方法内，只能在方法内用
• 匿名内部类：没有名字，一次性使用，最常用于事件处理和线程创建

它们让代码更内聚（相关的类放一起）、更封装（隐藏实现细节）、更简洁（匿名内部类），但要小心内存泄漏问题！

嵌套类对比内部类：