Java 数据结构练习：从数组到散列表

数组

数组是所有数据结构的起点。它在内存中是一段连续的空间，每个元素大小相同。

特征：

• 随机访问 O(1)：通过下标直接计算内存地址
• 插入/删除 O(n)：需要移动后续元素
• 连续内存，CPU 缓存友好

// 基本操作
int[] arr = new int[10];
arr[0] = 1;              // 写入
int val = arr[0];        // 读取 O(1)
int len = arr.length;    // 长度

// 遍历
for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); }
for (int x : arr) { System.out.println(x); }

// 二分查找（有序数组）
int idx = Arrays.binarySearch(arr, target);

常见数组算法

算法	思路	时间复杂度
冒泡排序	相邻比较交换	O(n²)
选择排序	每次选最小的放前面	O(n²)
插入排序	把元素插入已排序部分	O(n²) ~ O(n)
归并排序	分治：拆到最小再合并	O(n log n)
快速排序	选枢轴分区	O(n log n) ~ O(n²)
双指针	一快一慢或一左一右	O(n)

从数组到高级结构

理解数组是理解所有更高级集合的基础：

• ArrayList：数组实现的动态扩容列表
• HashMap：数组存储桶，每个桶是链表/红黑树
• String：内部就是 char[]（JDK 9+ 为 byte[]）
• 数组栈/队列：通过头尾指针在数组上模拟

// HashMap 原理简化：数组 + 链表
// 1. 根据 hashCode 计算桶的位置
int index = (n - 1) & hash;  // n 是 2 的幂
// 2. 如果该位置为空，直接放
// 3. 如果不为空，遍历链表检查 key 是否存在
// 4. 如果链表长度 > 8，转红黑树

练习建议

如果刚开始刷题，建议的顺序：

1. 数组遍历、反转、去重（双指针）
2. 链表反转、合并、检测环（快慢指针）
3. 栈和队列（括号匹配、表达式计算）
4. 哈希表（两数之和、字母异位词）
5. 树（遍历、最大深度、验证 BST）

每种数据结构掌握 3-5 道典型题，基本就能覆盖面试和工程中 90% 的场景。