背景
本文是《Java 后端从小白到大神》修仙系列第六篇，正式进入Java后端世界，本篇文章主要聊Java基础中的高级数据结构。若想详细学习请点击首篇博文，我们开始吧。
章节概览
- 堆（Heap）
- 树（Tree）
- 树的基本概念
- 二叉树
- 二叉搜索树
- 红黑树
- 树的遍历
- 图（Graph）
- 其他数据结构
1. 堆（Heap）
1.1 堆的定义与特性
堆是一种特殊的完全二叉树，具有以下特性：
- 最小堆：每个父节点的值都小于或等于其子节点的值
- 最大堆：每个父节点的值都大于或等于其子节点的值
- 完全二叉树：除最后一层外，其他层的节点数都达到最大值，且最后一层的节点从左到右连续排列
1.2 堆的应用场景
- 优先级队列：用于处理具有优先级的任务
- 堆排序：一种高效的排序算法
- 图算法：如Dijkstra最短路径算法
- 内存管理：操作系统的内存分配
1.3 Java中的堆实现
Java通过PriorityQueue类实现堆结构，默认是最小堆。
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
import java.util.PriorityQueue;
import java.util.Comparator;
public class HeapExample {
public static void main(String[] args) {
// 最小堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(3);
minHeap.add(8);
minHeap.add(1);
System.out.println(minHeap.poll()); // 输出 1
System.out.println(minHeap.poll()); // 输出 3
// 最大堆（需自定义 Comparator）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(5);
maxHeap.add(3);
maxHeap.add(8);
maxHeap.add(1);
System.out.println(maxHeap.poll()); // 输出 8
System.out.println(maxHeap.poll()); // 输出 5
// 自定义对象的优先级队列
class Task {
String name;
int priority;
public Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
@Override
public String toString() {
return name + "(优先级: " + priority + ")";
}
}
// 按优先级降序排列的任务队列
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
Comparator.comparingInt(t -> t.priority).reversed()
);
taskQueue.add(new Task("任务1", 1));
taskQueue.add(new Task("任务2", 5));
taskQueue.add(new Task("任务3", 3));
while (!taskQueue.isEmpty()) {
System.out.println(taskQueue.poll());
}
// 输出：
// 任务2(优先级: 5)
// 任务3(优先级: 3)
// 任务1(优先级: 1)
}
}
|
1.4 堆的时间复杂度
| 操作 |
时间复杂度 |
| 插入元素 |
O(log n) |
| 删除堆顶元素 |
O(log n) |
| 查看堆顶元素 |
O(1) |
| 构建堆 |
O(n) |
2. 树（Tree）
2.1 树的基本概念
树是一种分层数据结构，由节点（Node）和边（Edge）组成，满足以下条件：
- 每个节点有零个或多个子节点
- 只有一个根节点（Root），无父节点
- 除根节点外，其他节点有且仅有一个父节点
基本术语：
- 节点：树的基本单位，包含数据和指向子节点的引用
- 根节点：树的顶部节点，没有父节点
- 叶子节点：没有子节点的节点
- 父节点：有子节点的节点
- 子节点：被父节点指向的节点
- 深度：从根节点到该节点的路径长度
- 高度：从该节点到最远叶子节点的路径长度
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class TreeNode<T> {
T data;
List<TreeNode<T>> children; // 子节点列表
public TreeNode(T data) {
this.data = data;
this.children = new ArrayList<>();
}
}
public class TreeExample {
// 迭代遍历树（深度优先）
public static <T> void traverseTree(TreeNode<T> root) {
if (root == null) {
return;
}
Stack<TreeNode<T>> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode<T> node = stack.pop();
System.out.print(node.data + " ");
// 逆序压入子节点，确保按顺序遍历
for (int i = node.children.size() - 1; i >= 0; i--) {
stack.push(node.children.get(i));
}
}
System.out.println();
}
// 递归遍历树（深度优先）
public static <T> void traverseTreeRecursive(TreeNode<T> node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
for (TreeNode<T> child : node.children) {
traverseTreeRecursive(child);
}
}
public static void main(String[] args) {
// 创建树
TreeNode<String> root = new TreeNode<>("Root");
TreeNode<String> child1 = new TreeNode<>("Child1");
TreeNode<String> child2 = new TreeNode<>("Child2");
TreeNode<String> grandchild1 = new TreeNode<>("Grandchild1");
TreeNode<String> grandchild2 = new TreeNode<>("Grandchild2");
root.children.add(child1);
root.children.add(child2);
child1.children.add(grandchild1);
child1.children.add(grandchild2);
System.out.println("迭代遍历：");
traverseTree(root); // 输出：Root Child1 Grandchild1 Grandchild2 Child2
System.out.println("递归遍历：");
traverseTreeRecursive(root); // 输出：Root Child1 Grandchild1 Grandchild2 Child2
System.out.println();
}
}
|
2.2 二叉树（Binary Tree）
二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。
常见类型：
- 完全二叉树：除最后一层外，其他层节点数达到最大，且最后一层节点向左对齐
- 满二叉树：所有层的节点数都达到最大
- 平衡二叉树：左右子树高度差不超过1的二叉搜索树
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
class BinaryTreeNode<T> {
T data;
BinaryTreeNode<T> left;
BinaryTreeNode<T> right;
public BinaryTreeNode(T data) {
this.data = data;
}
}
public class BinaryTreeExample {
// 前序遍历（根→左→右）
public static <T> void preorder(BinaryTreeNode<T> root) {
if (root == null) return;
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// 中序遍历（左→根→右）
public static <T> void inorder(BinaryTreeNode<T> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
// 后序遍历（左→右→根）
public static <T> void postorder(BinaryTreeNode<T> root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.data + " ");
}
public static void main(String[] args) {
// 创建二叉树
BinaryTreeNode<Integer> root = new BinaryTreeNode<>(10);
root.left = new BinaryTreeNode<>(5);
root.right = new BinaryTreeNode<>(15);
root.left.left = new BinaryTreeNode<>(3);
root.left.right = new BinaryTreeNode<>(7);
root.right.left = new BinaryTreeNode<>(12);
root.right.right = new BinaryTreeNode<>(18);
System.out.println("前序遍历：");
preorder(root); // 输出：10 5 3 7 15 12 18
System.out.println();
System.out.println("中序遍历：");
inorder(root); // 输出：3 5 7 10 12 15 18
System.out.println();
System.out.println("后序遍历：");
postorder(root); // 输出：3 7 5 12 18 15 10
System.out.println();
}
}
|
2.3 二叉搜索树（Binary Search Tree, BST）
二叉搜索树是一种特殊的二叉树，满足以下性质：
- 左子树所有节点的值都小于根节点的值
- 右子树所有节点的值都大于根节点的值
- 左子树和右子树也都是二叉搜索树
优点：
- 查找、插入、删除操作的平均时间复杂度为O(log n)
- 中序遍历可以得到有序序列
缺点：
- 如果插入的是有序数据，可能会退化为链表，时间复杂度变为O(n)
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
class BSTNode {
int value;
BSTNode left;
BSTNode right;
public BSTNode(int value) {
this.value = value;
}
}
public class BSTExample {
// 插入节点
public static BSTNode insert(BSTNode root, int value) {
if (root == null) {
return new BSTNode(value);
}
if (value < root.value) {
root.left = insert(root.left, value);
} else if (value > root.value) {
root.right = insert(root.right, value);
}
return root;
}
// 查找节点
public static BSTNode search(BSTNode root, int value) {
if (root == null || root.value == value) {
return root;
}
if (value < root.value) {
return search(root.left, value);
} else {
return search(root.right, value);
}
}
// 中序遍历
public static void inorderTraversal(BSTNode root) {
if (root != null) {
inorderTraversal(root.left);
System.out.print(root.value + " ");
inorderTraversal(root.right);
}
}
public static void main(String[] args) {
BSTNode root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
System.out.println("中序遍历（有序）：");
inorderTraversal(root); // 输出：20 30 40 50 60 70 80
System.out.println();
// 查找节点
BSTNode found = search(root, 40);
System.out.println("查找值为40的节点：" + (found != null ? "找到" : "未找到"));
found = search(root, 90);
System.out.println("查找值为90的节点：" + (found != null ? "找到" : "未找到"));
}
}
|
2.4 红黑树（Red-Black Tree）
红黑树是一种自平衡的二叉搜索树，通过以下规则保证树的平衡性：
- 根节点是黑色
- 每个叶子节点（NIL节点）是黑色
- 如果一个节点是红色，则其两个子节点都是黑色
- 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
优点：
- 保证树的高度始终为O(log n)
- 插入、删除、查找操作的时间复杂度均为O(log n)
- 避免了普通BST可能退化为链表的问题
Java中的应用：
TreeMap和TreeSet的底层实现ConcurrentHashMap在桶中使用红黑树优化链表性能
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
public class RedBlackTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
class Node {
int key;
Node left, right, parent;
boolean color;
Node(int key) {
this.key = key;
this.color = RED; // 新节点默认为红色
}
}
private Node root;
private Node nil; // 哨兵节点，代表空节点
public RedBlackTree() {
nil = new Node(0);
nil.color = BLACK;
root = nil;
}
// 左旋转
private void rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != nil) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == nil) {
root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
// 右旋转
private void rotateRight(Node y) {
Node x = y.left;
y.left = x.right;
if (x.right != nil) {
x.right.parent = y;
}
x.parent = y.parent;
if (y.parent == nil) {
root = x;
} else if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
x.right = y;
y.parent = x;
}
// 插入节点
public void insert(int key) {
Node z = new Node(key);
Node y = nil;
Node x = root;
// 找到插入位置
while (x != nil) {
y = x;
if (z.key < x.key) {
x = x.left;
} else {
x = x.right;
}
}
z.parent = y;
if (y == nil) {
root = z;
} else if (z.key < y.key) {
y.left = z;
} else {
y.right = z;
}
z.left = nil;
z.right = nil;
z.color = RED;
insertFixup(z);
}
// 插入后修复
private void insertFixup(Node z) {
while (z.parent.color == RED) {
if (z.parent == z.parent.parent.left) {
Node y = z.parent.parent.right;
if (y.color == RED) {
// 情况1：叔叔节点是红色
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
} else {
if (z == z.parent.right) {
// 情况2：叔叔节点是黑色，且z是右孩子
z = z.parent;
rotateLeft(z);
}
// 情况3：叔叔节点是黑色，且z是左孩子
z.parent.color = BLACK;
z.parent.parent.color = RED;
rotateRight(z.parent.parent);
}
} else {
// 对称情况
Node y = z.parent.parent.left;
if (y.color == RED) {
z.parent.color = BLACK;
y.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
} else {
if (z == z.parent.left) {
z = z.parent;
rotateRight(z);
}
z.parent.color = BLACK;
z.parent.parent.color = RED;
rotateLeft(z.parent.parent);
}
}
}
root.color = BLACK;
}
// 中序遍历
public void inorderTraversal() {
inorderHelper(root);
System.out.println();
}
private void inorderHelper(Node node) {
if (node != nil) {
inorderHelper(node.left);
System.out.print(node.key + " ");
inorderHelper(node.right);
}
}
public static void main(String[] args) {
RedBlackTree rbt = new RedBlackTree();
rbt.insert(10);
rbt.insert(20);
rbt.insert(30);
rbt.insert(15);
rbt.insert(5);
System.out.println("红黑树中序遍历：");
rbt.inorderTraversal(); // 输出：5 10 15 20 30
}
}
|
2.5 树的遍历
树的遍历是指按照一定的顺序访问树的所有节点，常见的遍历方式有：
2.5.1 深度优先遍历（Depth-First Search, DFS）
-
前序遍历：根 → 左 → 右
-
中序遍历：左 → 根 → 右
-
后序遍历：左 → 右 → 根
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class TreeTraversal {
// 前序遍历（递归）
public void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preorder(root.left);
preorder(root.right);
}
// 前序遍历（迭代）
public void preorderIterative(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val + " ");
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}
// 中序遍历（递归）
public void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
// 中序遍历（迭代）
public void inorderIterative(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
System.out.print(curr.val + " ");
curr = curr.right;
}
}
// 后序遍历（递归）
public void postorder(TreeNode root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.val + " ");
}
// 后序遍历（迭代，双栈法）
public void postorderIterative(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) stack1.push(node.left);
if (node.right != null) stack1.push(node.right);
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().val + " ");
}
}
public static void main(String[] args) {
// 创建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
TreeTraversal traversal = new TreeTraversal();
System.out.println("前序遍历（递归）：");
traversal.preorder(root); // 输出：1 2 4 5 3 6 7
System.out.println();
System.out.println("前序遍历（迭代）：");
traversal.preorderIterative(root); // 输出：1 2 4 5 3 6 7
System.out.println();
System.out.println("中序遍历（递归）：");
traversal.inorder(root); // 输出：4 2 5 1 6 3 7
System.out.println();
System.out.println("中序遍历（迭代）：");
traversal.inorderIterative(root); // 输出：4 2 5 1 6 3 7
System.out.println();
System.out.println("后序遍历（递归）：");
traversal.postorder(root); // 输出：4 5 2 6 7 3 1
System.out.println();
System.out.println("后序遍历（迭代）：");
traversal.postorderIterative(root); // 输出：4 5 2 6 7 3 1
System.out.println();
}
}
|
2.5.2 广度优先遍历（Breadth-First Search, BFS）
层序遍历：按层从上到下、每层从左到右访问节点
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
import java.util.LinkedList;
import java.util.Queue;
public class LevelOrderTraversal {
public void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
System.out.println(); // 按层换行
}
}
public static void main(String[] args) {
// 创建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
LevelOrderTraversal traversal = new LevelOrderTraversal();
System.out.println("层序遍历：");
traversal.levelOrder(root);
// 输出：
// 1
// 2 3
// 4 5 6 7
}
}
|
3. 图（Graph）
3.1 图的定义与特性
图是由顶点（Vertex）和边（Edge）组成的非线性结构，用于表示对象之间的关系。
基本术语：
- 顶点：图中的基本单位
- 边：连接两个顶点的线
- 有向图：边有方向的图
- 无向图：边无方向的图
- 权重：边上的数值，表示距离、成本等
- 路径：从一个顶点到另一个顶点的边序列
- 环：起点和终点相同的路径
3.2 图的表示方法
3.2.1 邻接矩阵
- 使用二维数组表示顶点之间的连接关系
- 优点：查询两个顶点是否相邻的时间复杂度为O(1)
- 缺点：空间复杂度为O(n²)，不适合稀疏图
3.2.2 邻接表
- 使用链表或数组列表表示每个顶点的邻接顶点
- 优点：空间复杂度为O(n+e)，适合稀疏图
- 缺点：查询两个顶点是否相邻的时间复杂度为O(n)
3.3 图的遍历
3.3.1 深度优先搜索（DFS）
- 从起始顶点开始，递归访问所有可达顶点
- 应用：检测环、拓扑排序、连通性判断
3.3.2 广度优先搜索（BFS）
- 从起始顶点开始，按层次访问所有可达顶点
- 应用：最短路径、网络爬虫、社交网络分析
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
import java.util.*;
public class GraphExample {
private Map<Integer, List<Integer>> adjList; // 邻接表
public GraphExample() {
adjList = new HashMap<>();
}
// 添加顶点
public void addVertex(int vertex) {
adjList.putIfAbsent(vertex, new ArrayList<>());
}
// 添加边（无向图）
public void addEdge(int source, int destination) {
adjList.putIfAbsent(source, new ArrayList<>());
adjList.putIfAbsent(destination, new ArrayList<>());
adjList.get(source).add(destination);
adjList.get(destination).add(source);
}
// 深度优先搜索
public void dfs(int startVertex) {
Set<Integer> visited = new HashSet<>();
dfsHelper(startVertex, visited);
System.out.println();
}
private void dfsHelper(int vertex, Set<Integer> visited) {
visited.add(vertex);
System.out.print(vertex + " ");
for (int neighbor : adjList.get(vertex)) {
if (!visited.contains(neighbor)) {
dfsHelper(neighbor, visited);
}
}
}
// 广度优先搜索
public void bfs(int startVertex) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.offer(startVertex);
visited.add(startVertex);
while (!queue.isEmpty()) {
int vertex = queue.poll();
System.out.print(vertex + " ");
for (int neighbor : adjList.get(vertex)) {
if (!visited.contains(neighbor)) {
queue.offer(neighbor);
visited.add(neighbor);
}
}
}
System.out.println();
}
public static void main(String[] args) {
GraphExample graph = new GraphExample();
// 添加顶点
for (int i = 1; i <= 6; i++) {
graph.addVertex(i);
}
// 添加边
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 6);
graph.addEdge(4, 5);
graph.addEdge(5, 6);
System.out.println("深度优先搜索（从顶点1开始）：");
graph.dfs(1); // 输出：1 2 4 5 6 3
System.out.println("广度优先搜索（从顶点1开始）：");
graph.bfs(1); // 输出：1 2 3 4 5 6
}
}
|
3.4 图的应用场景
- 社交网络：表示用户之间的关系
- 路由算法：寻找最短路径
- 网络分析：分析网络拓扑结构
- 推荐系统：基于用户关系的推荐
- 游戏开发：寻路算法
4. 其他数据结构
4.1 枚举（Enumeration）
枚举是一种特殊的类，用于定义固定的常量集合。
优点：
- 类型安全：编译时检查
- 代码清晰：常量有明确的类型
- 功能强大：可以添加方法和属性
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
// 基本枚举
enum Day {
MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY
}
// 带属性和方法的枚举
enum Season {
SPRING("春天", 1),
SUMMER("夏天", 2),
AUTUMN("秋天", 3),
WINTER("冬天", 4);
private final String name;
private final int value;
Season(String name, int value) {
this.name = name;
this.value = value;
}
public String getName() {
return name;
}
public int getValue() {
return value;
}
}
public class EnumExample {
public static void main(String[] args) {
// 使用基本枚举
Day today = Day.MONDAY;
System.out.println("今天是：" + today);
// 使用带属性和方法的枚举
Season currentSeason = Season.SPRING;
System.out.println("当前季节：" + currentSeason.getName() + "，值：" + currentSeason.getValue());
// 遍历枚举
System.out.println("所有季节：");
for (Season season : Season.values()) {
System.out.println(season.getName() + "(" + season.getValue() + ")");
}
}
}
|
4.2 位集合（BitSet）
BitSet是一种特殊的集合，用于存储位值（0或1），适合处理大量的布尔值。
优点：
- 空间效率高：每个元素只占用1位
- 支持位运算：与、或、异或等
- 动态大小：自动扩容
应用场景：
- 权限管理：每个权限对应一个位
- 位图索引：数据库中的高效索引
- 布隆过滤器：快速判断元素是否存在
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
import java.util.BitSet;
public class BitSetExample {
public static void main(String[] args) {
// 创建BitSet
BitSet bits = new BitSet(8); // 初始容量为8位
// 设置位
bits.set(0); // 设置第0位为1
bits.set(2); // 设置第2位为1
bits.set(4); // 设置第4位为1
// 检查位
System.out.println("第0位：" + bits.get(0)); // 输出：true
System.out.println("第1位：" + bits.get(1)); // 输出：false
System.out.println("第2位：" + bits.get(2)); // 输出：true
// 清除位
bits.clear(2);
System.out.println("清除后第2位：" + bits.get(2)); // 输出：false
// 位运算
BitSet bits2 = new BitSet(8);
bits2.set(1);
bits2.set(2);
bits2.set(3);
// 与运算
BitSet andResult = (BitSet) bits.clone();
andResult.and(bits2);
System.out.println("与运算结果：" + andResult); // 输出：{}
// 或运算
BitSet orResult = (BitSet) bits.clone();
orResult.or(bits2);
System.out.println("或运算结果：" + orResult); // 输出：{0, 1, 2, 3, 4}
// 异或运算
BitSet xorResult = (BitSet) bits.clone();
xorResult.xor(bits2);
System.out.println("异或运算结果：" + xorResult); // 输出：{0, 1, 2, 3, 4}
}
}
|
4.3 哈希表（Hashtable）
Hashtable是一种线程安全的键值对存储结构，继承自Dictionary类。
特点：
- 线程安全：所有方法都有synchronized修饰
- 不允许null键和null值
- 底层实现：哈希表
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
import java.util.Hashtable;
public class HashtableExample {
public static void main(String[] args) {
Hashtable<String, Integer> table = new Hashtable<>();
// 添加键值对
table.put("A", 1);
table.put("B", 2);
table.put("C", 3);
// 获取值
System.out.println("A的值：" + table.get("A")); // 输出：1
// 遍历
System.out.println("所有键值对：");
for (String key : table.keySet()) {
System.out.println(key + ": " + table.get(key));
}
// 检查键是否存在
System.out.println("是否包含键D：" + table.containsKey("D")); // 输出：false
// 删除键值对
table.remove("B");
System.out.println("删除后是否包含键B：" + table.containsKey("B")); // 输出：false
}
}
|
4.4 属性（Properties）
Properties是Hashtable的子类，专门用于处理配置文件（.properties）。
特点：
- 键和值都是字符串
- 支持从文件加载和保存到文件
- 支持默认值
应用场景：
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Properties;
public class PropertiesExample {
public static void main(String[] args) {
Properties props = new Properties();
// 设置属性
props.setProperty("user", "admin");
props.setProperty("password", "123456");
props.setProperty("url", "jdbc:mysql://localhost:3306/test");
// 获取属性
System.out.println("用户名：" + props.getProperty("user"));
System.out.println("密码：" + props.getProperty("password"));
System.out.println("URL：" + props.getProperty("url"));
// 获取属性（带默认值）
System.out.println("端口：" + props.getProperty("port", "3306"));
// 保存到文件
try (FileOutputStream fos = new FileOutputStream("config.properties")) {
props.store(fos, "Database Configuration");
System.out.println("配置已保存到config.properties文件");
} catch (IOException e) {
e.printStackTrace();
}
// 从文件加载
Properties loadedProps = new Properties();
try (FileInputStream fis = new FileInputStream("config.properties")) {
loadedProps.load(fis);
System.out.println("从文件加载的用户名：" + loadedProps.getProperty("user"));
} catch (IOException e) {
e.printStackTrace();
}
}
}
|
总结
| 数据结构 |
用途 |
典型实现类 |
时间复杂度 |
| 堆 |
优先级任务调度 |
PriorityQueue |
插入/删除：O(log n) |
| 二叉搜索树 |
有序数据存储 |
自定义实现 |
平均：O(log n)，最坏：O(n) |
| 红黑树 |
自平衡有序数据存储 |
TreeMap, TreeSet |
O(log n) |
| 图 |
网络关系建模 |
自定义邻接表/邻接矩阵 |
取决于表示方法 |
| 枚举 |
定义固定常量集合 |
enum |
O(1) |
| 位集合 |
高效位操作 |
BitSet |
O(1) |
| 哈希表 |
线程安全的键值存储 |
Hashtable |
平均：O(1) |
| 属性 |
配置文件读写 |
Properties |
O(1) |
数据结构选择指南
- 需要优先级管理 →
PriorityQueue（堆）
- 需要有序数据 →
TreeMap/TreeSet（红黑树）
- 需要快速查找 →
HashMap（哈希表）
- 需要线程安全 →
Hashtable/ConcurrentHashMap
- 需要位操作 →
BitSet
- 需要配置管理 →
Properties
- 需要固定常量 →
enum
- 需要网络关系 → 图结构
选择合适的数据结构是提高程序效率和可维护性的关键。在实际开发中，应根据具体需求和场景选择最适合的数据结构。