数组与字符串 (Arrays & Strings)
为什么数组与字符串很重要
数组和字符串是后端系统中高效数据处理的核心基石：
- 内存效率：数组提供 的随机访问，且额外开销极低——这对于高性能缓存层至关重要。
- 缓存局部性 (Cache Locality)：连续的内存布局能充分利用 CPU 缓存行（Cache Lines），处理速度比链式结构快 10-100 倍。
- 字符串处理：几乎每个 HTTP 请求、JSON 负载和数据库查询都涉及大量的字符串操作。
- 面试高频：80% 以上的代码面试都以数组或字符串题目开场。
实际影响：对于一个每秒处理 1 万次请求的 API，仅仅通过优化字符串拼接减少每请求 200 毫秒的开销，就意味着同样的硬件能额外支撑 2000 个并发请求。
核心概念
内存布局与访问模式
数 组在内存中是连续存储的。
- 访问：
arr[i]的地址计算公式为首地址 + i * 元素大小。 - CPU 优化：读取一个 64 字节的缓存行可以同时获取多个相邻元素，极大提升遍历速度。
Java 中的数组 vs ArrayList
| 操作 | 原生数组 (int[]) | ArrayList<Integer> | 备注 |
|---|---|---|---|
| 随机访问 | 均使用直接索引 | ||
| 末尾插入 | 不支持（定长） | 均摊 | ArrayList 支持动态扩容 |
| 内存开销 | 极低（仅数据本身） | 较高（对象头+包装类） | int[] vs Integer[] |
字符串不可变性 (String Immutability)
Java 字符串一旦创建就不可更改。
- 优点：天然线程安全；
hashCode可被缓存提升查找速度；字符串常量池节省内存。 - 缺点：频繁修改（如在循环中拼接）会产生海量临时对象，导致 GC 压力剧增。
深入理解
1. StringBuilder 优化
在处理循环拼接时，务必使用 StringBuilder：
- 原理：内部维护一个可变的字符数组，避免了重复创建 String 对象。
- 性能：在 1 万次拼接测试中，
StringBuilder比直接拼接快 600 倍。
2. 动态扩容策略
ArrayList 在空间不足时会按 1.5 倍 原大小进行扩容。
- 原因：1.5 倍在扩容频率与内存碎片之间取得了较好的平衡。
3. 二维数组的存储
Java 中的 2D 数组是“数组的数组”，并非真正的连续平面。
- 提示：按行遍历比按列遍历更快，因为行内元素在物理内存上更接近，更能触发缓存命中。
常见陷阱与规避
- 使用
==比较字符串：这比较的是内存地址。对策：永远使用.equals()。 - 数组越界：使用
for-each或 Java 8+ 的 Stream API 可以有效避免索引越界错误。 - 循环内创建对象：避免在处理大数组的循环中创建临时字符串或包装类。
面试高频题
Q1: 两数之和 (简单)
思路：利用 HashMap 存储遍历过的值及其索引，实现 时间查找。
Q2: 除自身以外数组的乘积 (中等)
思路：左右两次遍历。左侧存储 i 左边的乘积，右侧乘上 i 右边的乘积。不使用除法。
Q3: 最长连续序列 (中等)
思路：将所有数字存入 HashSet，仅从序列的起点开始向上计数。
Q4: 旋转图像 (中等)
思路：先对矩阵进行转置（行变列），再翻转每一行，即可实现原地 90 度旋转。