Java 数据结构详解：从栈、队列、链表到红黑树、B-Tree 与位图
·
数据结构解决的不是“怎么写一个容器”这么简单的问题，而是：数据应该按什么形态组织，才能让查询、插入、删除、遍历、排序、范围检索这些操作更稳定、更可控。
本文用 Java 讲解 8 类常见数据结构：
- 栈（Stack）
- 队列（Queue）
- 链表（Linked List）
- 散列表（Hash Table）
- 排序二叉树，也叫二叉搜索树（Binary Search Tree）
- 红黑树（Red-Black Tree）
- B-Tree
- 位图（Bitmap）
文中的代码以 Java 8 及以上版本为基础。Java 标准库部分以 JDK 官方文档为准：ArrayDeque 适合当作栈和普通队列使用，HashMap 是基于哈希表的 Map 实现，TreeMap 是基于红黑树的有序 NavigableMap 实现，BitSet 是动态增长的位集合。
一、先建立几个复杂度概念
分析数据结构时，最常问的是：
- 查找一个元素要多久？
- 插入一个元素要多久？
- 删除一个元素要多久？
- 是否保持顺序？
- 是否支持按范围查询？
- 内存占用是否可控？
- 最坏情况下会不会退化？
常见复杂度可以这样理解：
| 复杂度 | 直观理解 | 常见场景 |
|---|---|---|
O(1) | 数据量增长，操作次数基本不变 | 数组按下标访问、栈顶入栈出栈、哈希表平均查询 |
O(log n) | 每次排除一大部分数据 | 平衡树查询、二分查找 |
O(n) | 需要线性扫描 | 链表查找、数组遍历 |
O(n log n) | 常见高效排序水平 | 归并排序、堆排序、平均快速排序 |
O(n^2) | 双层循环级别 | 简单排序、某些暴力比较 |
还要注意三个词：
- 平均复杂度：通常情况下的成本，例如
HashMap的get、put平均接近O(1)。 - 最坏复杂度：极端情况下的成本，例如普通二叉搜索树退化成链表后查询会变成
O(n)。 - 摊还复杂度：把偶发的高成本分摊到多次操作上，例如动态数组扩容虽然一次可能是
O(n)，但连续追加的摊还成本通常仍接近O(1)。
二、栈（Stack）
1. 栈的核心思想
栈是一种 后进先出（LIFO，Last In First Out）的线性结构。
可以把它想成一摞盘子：
- 新盘子只能放到最上面；
- 拿盘子也只能从最上面拿；
- 最后放进去的，会最先被拿出来。
栈的核心操作如下：
| 操作 | 含义 | 复杂度 |
|---|---|---|
push | 入栈，把元素放到栈顶 | O(1) |
pop | 出栈，移除并返回栈顶元素 | O(1) |
peek | 查看栈顶元素但不删除 | O(1) |
isEmpty | 判断栈是否为空 | O(1) |
2. Java 中怎么选栈实现
Java 里有一个老类叫 java.util.Stack，但实际开发更推荐使用 Deque 接口配合 ArrayDeque：
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2
原因是：
Stack是早期同步容器，API 和继承设计都比较老；ArrayDeque是可增长数组实现，作为栈使用通常更轻量；ArrayDeque不允许存放null，这反而能减少“空值到底是数据还是无数据”的歧义；ArrayDeque不是线程安全容器，多线程共享时需要外部同步或改用并发容器。
3. 示例：括号匹配
括号匹配是栈最经典的应用。遇到左括号时，把期望匹配的右括号压栈；遇到右括号时，检查它是否等于栈顶。
import java.util.ArrayDeque;
import java.util.Deque;
public class StackParenthesesDemo {
public static boolean isValid(String text) {
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < text.length(); i++) {
char ch = text.charAt(i);
if (ch == '(') {
stack.push(')');
} else if (ch == '[') {
stack.push(']');
} else if (ch == '{') {
stack.push('}');
} else if (ch == ')' || ch == ']' || ch == '}') {
if (stack.isEmpty() || stack.pop() != ch) {
return false;
}
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("{[()]}")); // true
System.out.println(isValid("{[(])}")); // false
}
}
4. 栈适合什么场景
栈适合处理“最近发生的事情要先处理”的问题：
- 方法调用栈；
- 表达式求值；
- 括号匹配；
- 浏览器前进后退；
- 编辑器撤销操作；
- 深度优先搜索（DFS）；
- 单调栈问题，例如下一个更大元素。
栈的关键限制是：它只能高效访问栈顶。你不能指望它像数组一样按下标随机访问中间元素。
三、队列（Queue）
1. 队列的核心思想
队列是一种 先进先出（FIFO，First In First Out）的线性结构。
可以把它想成排队买票：
- 新来的人排到队尾；
- 最先来的人从队头离开；
- 队列保证处理顺序。
队列的核心操作如下：
| 操作 | 含义 | 复杂度 |
|---|---|---|
offer | 入队，放到队尾 | O(1) |
poll | 出队，移除并返回队头元素 | O(1) |
peek | 查看队头元素但不删除 | O(1) |
isEmpty | 判断队列是否为空 | O(1) |
Java 队列 API 有两组容易混淆的方法：
| 推荐用于普通业务 | 空队列或失败时 | 另一组方法 | 空队列或失败时 |
|---|---|---|---|
offer(e) | 返回 false | add(e) | 抛异常 |
poll() | 返回 null | remove() | 抛异常 |
peek() | 返回 null | element() | 抛异常 |
日常业务里通常优先用 offer、poll、peek，因为它们更适合显式处理空队列。
2. Java 中怎么选队列实现
常用选择如下：
| 场景 | 推荐实现 |
|---|---|
| 普通单线程 FIFO 队列 | ArrayDeque |
| 两端都要插入和删除 | ArrayDeque |
| 需要阻塞等待 | ArrayBlockingQueue、LinkedBlockingQueue |
| 需要优先级 | PriorityQueue |
| 需要线程安全且高吞吐非阻塞队列 | ConcurrentLinkedQueue |
注意：PriorityQueue 虽然名字里有 Queue，但它不是严格 FIFO，而是按优先级出队。
3. 示例：用队列实现 BFS
广度优先搜索（BFS）每次先处理离起点最近的一层节点，非常适合用队列。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
public class QueueBfsDemo {
public static List<Integer> bfs(List<List<Integer>> graph, int start) {
boolean[] visited = new boolean[graph.size()];
Deque<Integer> queue = new ArrayDeque<>();
List<Integer> order = new ArrayList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int current = queue.poll();
order.add(current);
for (int next : graph.get(current)) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
return order;
}
public static void main(String[] args) {
List<List<Integer>> graph = Arrays.asList(
Arrays.asList(1, 2),
Arrays.asList(3),
Arrays.asList(3, 4),
Arrays.asList(4),
Collections.<Integer>emptyList()
);
System.out.println(bfs(graph, 0)); // [0, 1, 2, 3, 4]
}
}
4. 队列适合什么场景
队列适合处理“先来的任务先处理”的问题：
- 消息队列；
- 请求排队；
- 线程池任务队列；
- BFS；
- 生产者消费者模型；
- 缓冲区；
- 限流削峰。
队列的关键限制是：普通队列只关心队头和队尾，不适合随机访问中间元素。
四、链表（Linked List）
1. 链表的核心思想
链表由一个个节点组成，每个节点保存数据，并通过引用指向下一个节点。
最简单的单向链表节点可以表示为：
class Node {
int value;
Node next;
}
链表和数组最大的区别是：
- 数组在内存中通常是连续空间，适合按下标访问；
- 链表通过节点引用连接，不要求连续空间；
- 链表访问第
i个元素时，通常必须从头节点一步步走过去； - 如果已经拿到某个节点的引用，在它后面插入或删除节点可以很快。
2. 链表的类型
| 类型 | 特点 |
|---|---|
| 单向链表 | 每个节点只指向下一个节点 |
| 双向链表 | 每个节点同时指向前一个和后一个节点 |
| 循环链表 | 尾节点指向头节点，适合环形调度 |
Java 标准库里的 LinkedList 是双向链表，并且同时实现了 List、Deque、Queue 等接口。
3. 链表复杂度
| 操作 | 单向链表复杂度 | 说明 |
|---|---|---|
| 头部插入 | O(1) | 改一下头指针 |
| 头部删除 | O(1) | 改一下头指针 |
| 尾部插入 | 有尾指针为 O(1)，无尾指针为 O(n) | 是否维护 tail 很关键 |
| 查找某个值 | O(n) | 需要逐个节点扫描 |
| 按下标访问 | O(n) | 不能像数组那样直接跳到下标 |
| 删除已知后继节点 | O(1) | 前提是已经拿到前驱节点 |
一句话总结：链表擅长“局部插入删除”，不擅长“随机访问”。
4. 示例：实现一个简单单向链表
import java.util.NoSuchElementException;
import java.util.Objects;
public class SinglyLinkedListDemo {
public static class SinglyLinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
private static class Node<E> {
private final E value;
private Node<E> next;
private Node(E value) {
this.value = value;
}
}
public void addFirst(E value) {
Node<E> node = new Node<>(value);
node.next = head;
head = node;
if (tail == null) {
tail = node;
}
size++;
}
public void addLast(E value) {
Node<E> node = new Node<>(value);
if (tail == null) {
head = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
size++;
}
public E removeFirst() {
if (head == null) {
throw new NoSuchElementException("list is empty");
}
E value = head.value;
head = head.next;
if (head == null) {
tail = null;
}
size--;
return value;
}
public boolean contains(E target) {
for (Node<E> current = head; current != null; current = current.next) {
if (Objects.equals(current.value, target)) {
return true;
}
}
return false;
}
public int size() {
return size;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder("[");
for (Node<E> current = head; current != null; current = current.next) {
if (current != head) {
builder.append(", ");
}
builder.append(current.value);
}
return builder.append(']').toString();
}
}
public static void main(String[] args) {
SinglyLinkedList<String> list = new SinglyLinkedList<>();
list.addLast("A");
list.addLast("B");
list.addFirst("Start");
System.out.println(list); // [Start, A, B]
System.out.println(list.contains("A")); // true
System.out.println(list.removeFirst()); // Start
System.out.println(list.size()); // 2
}
}
5. 使用链表的常见误区
不要看到“插入删除 O(1)”就默认链表一定比数组好。这个 O(1) 有前提：你已经拿到了要操作位置附近的节点。
如果业务代码经常这样写：
linkedList.get(i);
那就要警惕了。LinkedList 按下标访问需要从头或尾开始遍历，复杂度是 O(n)。如果你主要按下标访问，ArrayList 往往更合适。
链表还有两个实际成本：
- 每个节点都要额外保存引用，内存开销更大；
- 节点分散在堆上，CPU 缓存局部性通常不如数组。
五、散列表（Hash Table）
1. 散列表的核心思想
散列表通过哈希函数把 key 映射到数组下标，从而快速定位数据。
简化流程如下：
key -> hashCode -> 扰动/取模 -> bucket 下标 -> 找到对应元素
在 Java 中，最典型的散列表实现就是 HashMap 和 HashSet。
HashMap 存的是 key-value：
Map<String, Integer> map = new HashMap<>();
map.put("Java", 1);
System.out.println(map.get("Java"));
HashSet 只关心元素是否存在，本质上也是基于哈希思想：
Set<String> set = new HashSet<>();
set.add("Java");
System.out.println(set.contains("Java"));
2. 哈希冲突
不同 key 经过哈希计算后，可能落到同一个 bucket，这叫哈希冲突。
常见处理方式有：
- 链地址法：同一个 bucket 后面挂链表或树；
- 开放寻址法：冲突后继续探测下一个可用位置；
- 再哈希：换一个哈希函数或计算方式。
Java 的 HashMap 属于链地址法思路。具体实现会随着 JDK 版本演进，不建议把内部阈值当成业务代码的稳定契约。
3. HashMap 复杂度
| 操作 | 平均复杂度 | 最坏复杂度 |
|---|---|---|
put | O(1) | 可能退化 |
get | O(1) | 可能退化 |
remove | O(1) | 可能退化 |
| 遍历 | O(capacity + size) | 受容量和元素数量共同影响 |
散列表的性能依赖两个条件：
- hash 分布要尽量均匀；
- 冲突不能过于集中。
4. equals 与 hashCode 契约
在 Java 中，只要对象要当作 HashMap 的 key，就必须遵守：
- 如果
a.equals(b) == true，那么a.hashCode()必须等于b.hashCode()； - 如果两个对象
hashCode相同，它们不一定equals； - 作为 key 的字段最好不可变，否则放入
HashMap后字段变化，会导致后续查不到。
5. 示例：词频统计与自定义 key
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public class HashTableWordCountDemo {
private static final class UserKey {
private final long tenantId;
private final long userId;
private UserKey(long tenantId, long userId) {
this.tenantId = tenantId;
this.userId = userId;
}
@Override
public boolean equals(Object other) {
if (this == other) {
return true;
}
if (!(other instanceof UserKey)) {
return false;
}
UserKey that = (UserKey) other;
return tenantId == that.tenantId && userId == that.userId;
}
@Override
public int hashCode() {
return Objects.hash(tenantId, userId);
}
}
public static void main(String[] args) {
String text = "java hash map java tree map java";
Map<String, Integer> wordCount = new HashMap<>();
for (String word : text.split("\\s+")) {
wordCount.merge(word, 1, Integer::sum);
}
System.out.println(wordCount); // {java=3, tree=1, hash=1, map=2}
Map<UserKey, String> users = new HashMap<>();
users.put(new UserKey(1001L, 42L), "Alice");
System.out.println(users.get(new UserKey(1001L, 42L))); // Alice
}
}
6. 散列表适合什么场景
散列表适合通过 key 快速定位 value：
- 缓存；
- 字典；
- 去重；
- 计数；
- 索引；
- 对象映射；
- 判断元素是否存在。
不适合的场景：
- 需要按 key 排序：用
TreeMap； - 需要稳定插入顺序：用
LinkedHashMap； - 需要范围查询：用
TreeMap或数据库索引； - 多线程高并发写：用
ConcurrentHashMap或外部同步。
六、排序二叉树（Binary Search Tree）
1. 排序二叉树的核心思想
排序二叉树更常见的名字是 二叉搜索树（BST，Binary Search Tree）。
它满足一个关键性质：
- 左子树所有节点都小于当前节点；
- 右子树所有节点都大于当前节点；
- 左右子树本身也都是二叉搜索树。
例如：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
如果按中序遍历（左 -> 根 -> 右）访问这棵树，会得到有序序列：
1, 3, 4, 6, 7, 8, 10, 13, 14
2. BST 复杂度
| 操作 | 平均复杂度 | 最坏复杂度 |
|---|---|---|
| 查询 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
| 中序遍历 | O(n) | O(n) |
最坏情况发生在树严重倾斜时，例如按递增顺序插入：
1
\
2
\
3
\
4
这时 BST 退化成链表，查询就变成 O(n)。
3. 示例：实现插入、查询、删除、中序遍历
下面示例采用“重复值忽略”的策略。实际业务里也可以改成保存计数，或者把重复值放到固定一侧。
import java.util.ArrayList;
import java.util.List;
public class BinarySearchTreeDemo {
private Node root;
private static class Node {
private int value;
private Node left;
private Node right;
private Node(int value) {
this.value = value;
}
}
public void insert(int value) {
root = insert(root, value);
}
private Node insert(Node node, int value) {
if (node == null) {
return new Node(value);
}
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
}
return node;
}
public boolean contains(int value) {
Node current = root;
while (current != null) {
if (value == current.value) {
return true;
}
current = value < current.value ? current.left : current.right;
}
return false;
}
public void delete(int value) {
root = delete(root, value);
}
private Node delete(Node node, int value) {
if (node == null) {
return null;
}
if (value < node.value) {
node.left = delete(node.left, value);
} else if (value > node.value) {
node.right = delete(node.right, value);
} else {
if (node.left == null) {
return node.right;
}
if (node.right == null) {
return node.left;
}
Node successor = min(node.right);
node.value = successor.value;
node.right = delete(node.right, successor.value);
}
return node;
}
private Node min(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
public List<Integer> inOrder() {
List<Integer> values = new ArrayList<>();
inOrder(root, values);
return values;
}
private void inOrder(Node node, List<Integer> values) {
if (node == null) {
return;
}
inOrder(node.left, values);
values.add(node.value);
inOrder(node.right, values);
}
public static void main(String[] args) {
BinarySearchTreeDemo tree = new BinarySearchTreeDemo();
int[] values = {8, 3, 10, 1, 6, 14, 4, 7, 13};
for (int value : values) {
tree.insert(value);
}
System.out.println(tree.contains(6)); // true
System.out.println(tree.inOrder()); // [1, 3, 4, 6, 7, 8, 10, 13, 14]
tree.delete(3);
System.out.println(tree.inOrder()); // [1, 4, 6, 7, 8, 10, 13, 14]
}
}
4. BST 适合什么场景
BST 适合理解有序结构和树形查找，但普通 BST 在生产里有明显风险：数据插入顺序不理想时会退化。
因此实际开发中，如果你需要有序映射或范围查询，通常直接使用基于平衡树的 TreeMap、TreeSet，而不是手写普通 BST。
七、红黑树（Red-Black Tree）
1. 为什么需要红黑树
普通 BST 的问题是可能退化成链表。红黑树就是为了解决这个问题：它通过颜色规则和旋转操作，让树在插入、删除后仍然保持近似平衡。
红黑树不是“绝对平衡”的树。它不像 AVL 树那样严格要求左右子树高度差很小，而是用相对宽松的规则换取更少的旋转成本。
2. 红黑树的核心规则
红黑树是一棵二叉搜索树，同时满足以下规则：
- 每个节点要么是红色，要么是黑色；
- 根节点是黑色；
- 所有叶子空节点可以看作黑色；
- 红色节点不能有红色子节点，也就是不能出现连续两个红节点；
- 从任意节点到其所有后代叶子空节点的路径上，黑色节点数量相同。
这些规则保证红黑树不会过度倾斜，因此查询、插入、删除都能维持 O(log n)。
3. 红黑树如何保持平衡
插入或删除节点后，红黑树可能破坏规则。修复手段主要有两类：
- 变色：调整节点颜色；
- 旋转：改变局部父子关系，包括左旋和右旋。
左旋示意：
x y
\ / \
y -> x c
/ \ \
b c b
右旋示意：
y x
/ / \
x -> a y
/ \ /
a b b
旋转不会破坏二叉搜索树的有序性，只是改变树的形态。
4. Java 中的红黑树：TreeMap 与 TreeSet
Java 标准库中的 TreeMap 是基于红黑树的 NavigableMap 实现。它按 key 的自然顺序或构造时传入的 Comparator 排序，并保证 containsKey、get、put、remove 等操作的 log(n) 时间成本。
TreeSet 底层也可以理解为基于有序树结构来维护元素顺序。
5. 示例：用 TreeMap 做范围查询
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;
public class TreeMapRedBlackTreeDemo {
public static void main(String[] args) {
TreeMap<Integer, String> events = new TreeMap<>();
events.put(900, "start work");
events.put(930, "daily meeting");
events.put(1030, "code review");
events.put(1400, "release");
Map.Entry<Integer, String> floor = events.floorEntry(1000);
Map.Entry<Integer, String> ceiling = events.ceilingEntry(1000);
NavigableMap<Integer, String> morning = events.subMap(900, true, 1200, true);
System.out.println(floor); // 930=daily meeting
System.out.println(ceiling); // 1030=code review
System.out.println(morning); // {900=start work, 930=daily meeting, 1030=code review}
}
}
6. 红黑树适合什么场景
红黑树适合既要查询，又要维护顺序的场景：
- 有序 Map；
- 有序 Set；
- 排行榜；
- 时间线索引；
- 范围查询；
- 查找小于等于某值的最大 key；
- 查找大于等于某值的最小 key。
如果只需要根据 key 精确查询，HashMap 通常更快；如果还需要有序遍历和范围查询，TreeMap 更合适。
八、B-Tree
1. B-Tree 的核心思想
B-Tree 是一种多路平衡搜索树。它不是二叉树，一个节点可以保存多个 key，也可以有多个子节点。
一个 B-Tree 节点大致长这样：
[10 | 20 | 30]
/ | | \
<10 10-20 20-30 >30
为什么要这么设计？
因为在磁盘、SSD、数据库页、文件系统索引这类场景中，一次读取通常不是只读一个整数，而是读取一整页数据。B-Tree 让一个节点容纳多个 key，可以降低树高，从而减少 I/O 次数。
2. B-Tree 的性质
以最小度数 t 的 B-Tree 为例：
- 每个节点最多有
2t - 1个 key； - 每个非根节点至少有
t - 1个 key； - 每个内部节点的子节点数量等于 key 数量加 1；
- 节点内部 key 保持有序；
- 所有叶子节点位于同一层；
- 查找时根据 key 所在区间决定进入哪个子节点。
3. B-Tree 复杂度
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 查询 | O(log n) | 更准确地说和树高有关，分支越多树越矮 |
| 插入 | O(log n) | 可能触发节点分裂 |
| 删除 | O(log n) | 可能触发借位或合并 |
| 范围遍历 | O(log n + k) | 先定位起点，再顺序取 k 个元素 |
B-Tree 的价值不是把理论复杂度从 O(log n) 变成 O(1)，而是显著降低树高，减少磁盘或页读取次数。
4. 插入和删除的基本动作
B-Tree 插入时：
- 先找到应该插入的叶子节点；
- 如果节点未满，直接插入并保持节点内有序；
- 如果节点已满，就把中间 key 提升到父节点，把原节点拆成左右两个节点；
- 分裂可能继续向上传播，甚至导致根节点分裂。
B-Tree 删除时更复杂：
- 如果删除叶子节点中的 key，直接删除或做局部修复；
- 如果删除内部节点中的 key，通常用前驱或后继替换；
- 如果某个节点 key 数量太少，需要向兄弟节点借 key；
- 如果兄弟也不够借，就合并节点。
5. 示例：B-Tree 节点内查找核心逻辑
完整 B-Tree 插入和删除实现较长，业务开发一般不建议手写。下面只展示“节点内查找 + 选择子树”的核心逻辑，用于理解 B-Tree 如何定位 key。
public class BTreeSearchDemo {
private static final class Node {
private final int[] keys;
private final Node[] children;
private final boolean leaf;
private Node(int[] keys, boolean leaf, Node... children) {
this.keys = keys;
this.leaf = leaf;
this.children = children;
}
private boolean contains(int target) {
int index = 0;
while (index < keys.length && target > keys[index]) {
index++;
}
if (index < keys.length && target == keys[index]) {
return true;
}
if (leaf) {
return false;
}
return children[index].contains(target);
}
}
public static void main(String[] args) {
Node left = new Node(new int[]{1, 5, 8}, true);
Node middle = new Node(new int[]{12, 17}, true);
Node right = new Node(new int[]{21, 25, 30}, true);
Node root = new Node(new int[]{10, 20}, false, left, middle, right);
System.out.println(root.contains(17)); // true
System.out.println(root.contains(19)); // false
}
}
6. B-Tree 与 B+Tree 的区别
数据库索引里更常听到的是 B+Tree。二者常见区别如下：
| 对比项 | B-Tree | B+Tree |
|---|---|---|
| 数据保存位置 | 内部节点和叶子节点都可能保存数据 | 数据通常集中在叶子节点 |
| 范围查询 | 可以做，但叶子不一定天然串联 | 叶子节点通常通过链表连接，更适合范围扫描 |
| 内部节点 | 既做索引，也可能保存数据 | 主要做索引 |
| 常见使用 | 文件系统、索引结构 | 数据库索引更常见 |
实际数据库实现会有页结构、压缩、MVCC、锁、日志、缓存等额外设计，不能把教科书 B+Tree 和某个数据库实现简单画等号。
7. B-Tree 适合什么场景
B-Tree 适合大规模、有序、面向块存储的数据：
- 数据库索引；
- 文件系统索引；
- 存储引擎；
- 磁盘页索引；
- 需要范围扫描的大数据量有序结构。
在普通 Java 应用层，如果只是维护内存里的有序 Map，优先用 TreeMap。如果需要持久化索引，通常交给数据库、搜索引擎或成熟存储库。
九、位图（Bitmap）
1. 位图的核心思想
位图用一个 bit 表示一个整数是否存在。
例如，要表示用户 ID 是否出现过：
bit[0] 表示 ID 0 是否存在
bit[1] 表示 ID 1 是否存在
bit[2] 表示 ID 2 是否存在
...
如果某个 ID 出现，就把对应 bit 置为 1；没有出现就是 0。
2. 位图为什么省内存
如果用 boolean[] 存 1 亿个状态，理论上每个 boolean 至少占 1 字节级别空间，还不算对象头等开销。
如果用位图，1 个状态只需要 1 bit：
100,000,000 bit / 8 = 12,500,000 byte，约 11.92 MiB
这就是位图的优势：当 key 是非负整数，并且范围相对可控时，它非常省内存。
3. Java 中的 BitSet
Java 标准库提供了 BitSet：
- bit 下标必须是非负整数；
- 默认所有 bit 都是
false； - 可以动态增长；
- 支持
set、get、clear、and、or、xor等操作； - 不是线程安全容器，多线程共享时需要外部同步。
4. 示例：去重、成员判断、交集
import java.util.BitSet;
public class BitSetDemo {
public static void main(String[] args) {
BitSet activeUsers = new BitSet();
int[] loginUserIds = {1, 2, 5, 7, 7, 9};
for (int userId : loginUserIds) {
activeUsers.set(userId);
}
System.out.println(activeUsers.get(7)); // true
System.out.println(activeUsers.get(8)); // false
System.out.println(activeUsers.cardinality()); // 5
BitSet paidUsers = new BitSet();
paidUsers.set(2);
paidUsers.set(7);
paidUsers.set(10);
BitSet activeAndPaid = (BitSet) activeUsers.clone();
activeAndPaid.and(paidUsers);
for (int userId = activeAndPaid.nextSetBit(0);
userId >= 0;
userId = activeAndPaid.nextSetBit(userId + 1)) {
System.out.println(userId); // 2, 7
}
}
}
5. 位图适合什么场景
位图适合处理整数集合：
- 用户签到；
- 活跃用户标记；
- 去重；
- 黑名单、白名单；
- 权限位；
- 标签集合；
- 交集、并集、差集；
- 大范围整数是否存在。
6. 位图的限制
位图不是万能的：
- 只适合整数下标，字符串需要先映射成整数；
- 只适合范围相对可控的数据，如果最大 ID 极大但实际数据很稀疏，可能浪费空间；
- 默认只能表示“有没有”，不能表示次数；
- 负数需要做偏移映射；
- 位图是精确结构，和 Bloom Filter 不同。Bloom Filter 更省空间，但存在误判概率。
十、八种数据结构对比速查
| 数据结构 | 核心顺序 | 查询 | 插入 | 删除 | 典型 Java 实现 | 适合场景 |
|---|---|---|---|---|---|---|
| 栈 | 后进先出 | 只能看栈顶 O(1) | 栈顶 O(1) | 栈顶 O(1) | ArrayDeque | 撤销、括号匹配、DFS |
| 队列 | 先进先出 | 只能看队头 O(1) | 队尾 O(1) | 队头 O(1) | ArrayDeque、阻塞队列 | 任务排队、BFS、生产者消费者 |
| 链表 | 节点连接顺序 | O(n) | 已知位置 O(1) | 已知位置 O(1) | LinkedList | 局部插入删除、双端队列 |
| 散列表 | 无稳定排序保证 | 平均 O(1) | 平均 O(1) | 平均 O(1) | HashMap、HashSet | key-value 查询、缓存、去重 |
| 排序二叉树 | key 有序 | 平均 O(log n)，最坏 O(n) | 平均 O(log n) | 平均 O(log n) | 通常手写用于学习 | 理解树形查找、中序排序 |
| 红黑树 | key 有序 | O(log n) | O(log n) | O(log n) | TreeMap、TreeSet | 有序 Map、范围查询 |
| B-Tree | 多路有序 | O(log n) | O(log n) | O(log n) | 通常由数据库/存储库实现 | 数据库索引、文件系统索引 |
| 位图 | 整数下标顺序 | O(1) | O(1) | O(1) | BitSet | 整数集合、状态标记、集合运算 |
十一、怎么选择合适的数据结构
可以按问题特征来选：
| 问题特征 | 推荐数据结构 |
|---|---|
| 最近加入的先处理 | 栈 |
| 先来的任务先处理 | 队列 |
| 需要频繁在头尾操作 | ArrayDeque 或链表 |
| 需要按下标随机访问 | 数组或 ArrayList |
| 需要根据 key 快速查 value | HashMap |
| 需要去重且不关心顺序 | HashSet |
| 需要按 key 排序遍历 | TreeMap |
| 需要范围查询 | TreeMap、数据库索引 |
| 数据量大且在磁盘/页上组织 | B-Tree 或 B+Tree |
| 整数范围可控，只判断存在性 | 位图 |
再给几个判断口径：
- 如果只要精确 key 查询，优先考虑散列表；
- 如果既要查询又要有序，优先考虑红黑树实现，例如
TreeMap； - 如果只在一端进出，考虑栈；
- 如果一端进另一端出，考虑队列；
- 如果要处理密集整数集合，考虑位图；
- 如果数据在数据库里，不要把应用层集合当数据库索引用。
十二、常见面试追问
1. HashMap 为什么平均是 O(1)
因为哈希函数能把 key 均匀分散到不同 bucket 时，定位 bucket 的成本接近常数，bucket 内需要比较的元素也很少。
但这个结论依赖哈希分布。大量 key 落到同一个 bucket 时，性能会下降。
2. HashMap 和 TreeMap 怎么选
只需要按 key 精确查找，通常选 HashMap。
需要 key 有序、范围查询、找最近的较大或较小 key，选 TreeMap。
3. ArrayDeque 和 LinkedList 都能做队列，怎么选
普通队列优先选 ArrayDeque。它基于数组，缓存局部性好，额外对象少。
LinkedList 每个元素都要一个节点对象，内存和 GC 成本更高。只有在你确实需要链表节点特性时，才优先考虑链表。
4. 红黑树和普通 BST 的区别
普通 BST 不保证平衡，最坏会退化成链表。
红黑树通过颜色规则、变色和旋转保持近似平衡，能保证查询、插入、删除是 O(log n)。
5. B-Tree 为什么适合数据库索引
因为 B-Tree 是多路树，一个节点能容纳多个 key，树高低，磁盘页读取次数少。数据库更关心 I/O 次数，而不仅仅是 CPU 比较次数。
6. 位图和 HashSet 有什么区别
HashSet<Integer> 保存的是整数对象或包装后的结构，通用但内存更重。
位图用一个 bit 表示一个整数是否存在，内存非常省，但要求整数范围相对可控，且默认只能表达存在与否。
十三、总结
数据结构的选择，本质上是在时间、空间、顺序、范围查询、实现复杂度之间做权衡。
- 栈和队列是最基础的访问顺序控制；
- 链表强调节点连接，适合局部插入删除，但随机访问弱；
- 散列表追求平均
O(1)的 key 查询； - 排序二叉树用于理解有序树，但生产中容易被平衡树替代；
- 红黑树在有序性和更新成本之间取得平衡；
- B-Tree 面向页和磁盘，是数据库索引的重要基础；
- 位图用极低空间成本表达整数集合。
实际 Java 开发中，不要急着手写复杂结构。优先掌握标准库的能力和边界：ArrayDeque、HashMap、HashSet、LinkedList、TreeMap、TreeSet、BitSet。真正需要自研数据结构时，再根据读写比例、数据规模、并发要求和内存预算做设计。
参考资料
- Java SE 25 API：
ArrayDeque
https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/ArrayDeque.html - Java SE 25 API：
LinkedList
https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/LinkedList.html - Java SE 25 API：
HashMap
https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/HashMap.html - Java SE 25 API：
TreeMap
https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/TreeMap.html - Java SE 25 API：
BitSet
https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/BitSet.html
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)