boxmoe_header_banner_img

困困小猫の秘密基地

加载中

文章导读

数组、字符串与 Hash 表:从算法到工程与安全(1)


avatar
kunkunxiaomao 2026年9月16日 65

前言

最近,总想着提升自己,既然Web黑盒已经到了瓶颈。与其如此,不如慢慢的发展代码审计和安全工具开发,于是乎又翻开了从前上课的那本算法与数据结构,熟悉是必然的,可也多了不一样的角度看待这些算法。

数组、字符串与 Hash 表看似是三块独立的入门知识,实际解决的是同一件事:如何表示数据、快速定位状态,并在数据持续变化时保持正确的边界。

本文从刷题中的数据结构选择出发,连接 Java 实现、爬虫等工程场景,并落到代码审计时真正需要关注的资源、权限与输入边界。今天,我们就先了解一下基础的数据结构吧

目录


一、先建立一张选择地图

很多人一开始背了数组、String、HashMap 的 API,却仍会在题目里犹豫“该用哪个”。更实用的判断方式是先问:我需要按位置、按文本,还是按键来访问状态?

我想解决的问题优先考虑原因
第 i 个元素、连续区间、范围固定的计数数组下标就是直接定位,访问快且紧凑
文本的比较、匹配、截取、窗口字符串数据本身有顺序与编码语义
是否出现过、出现次数、值对应位置/状态HashSet / HashMap通过 key 快速查询状态
字符范围固定为 a-zint[26]边界明确,没有碰撞和对象开销
URL、用户 ID、单词等开放键空间HashMap / HashSet无需预先分配可能无限大的数组

这不是“谁更高级”的问题:

范围小且边界明确,用数组;键空间开放或稀疏,用 Hash 表;数据带有文本语义时,先把它当字符串处理。


二、数组:当范围和位置都明确

数组是一段有序数据,通过下标直接访问元素:

index:  0   1   2   3
value: 10  20  30  40

它的优势是按位置读写 O(1);代价是长度固定,中间插入、删除通常要移动元素。

操作数组的典型成本
按下标读取/修改O(1)
遍历O(n)
中间插入/删除O(n)
按值查找O(n)

Java 中的数组与 ArrayList

int[] scores = new int[100];
List<String> urls = new ArrayList<>();

原生数组长度固定;ArrayList 是基于数组实现的动态列表,容量不足时会扩容并复制元素。因此它适合尾部追加和按下标读取,不适合高频在头部插入。

使用时需要记住几件小事:

  • array.length 是字段,list.size() 是方法;
  • 数组和 ArrayList 都是可变的,跨模块传递时要考虑共享修改;
  • subList() 是原列表的视图,并不是完全独立的副本;
  • 大小来自外部输入时,先校验再分配,不能直接 new byte[clientLength]。

数组最常用的三种思路

1. 双指针:两端向中间靠拢,或快慢指针在同一数组上协作。适用于有序数组配对、原地去重、移动零等。

int left = 0, right = nums.length - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return 1;
    if (sum < target) left++;
    else right--;
}
return 0;

2. 滑动窗口:维护一个连续区间 [left, right]。右边界负责把数据纳入窗口,窗口不合法时移动左边界。

3. 前缀和:预处理后快速查询连续区间的和。注意使用 long 防止数据规模稍大时 int 溢出。

long[] prefix = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}
long rangeSum = prefix[right] - prefix[left]; // [left, right)

三、字符串:从字符序列到不可信输入

算法中,字符串是有顺序的字符序列;工程中,它还可能是 URL、路径、JSON、Cookie、日志字段、用户名或 token。它最终会被谁解释,决定了它是否安全。

Java String 的三个基本事实

不可变:String 不能原地修改,拼接会产生新对象。循环构建长文本使用 StringBuilder:

StringBuilder builder = new StringBuilder();
for (String part : parts) {
    builder.append(part);
}
String result = builder.toString();

内容比较用 equals:== 比较的是引用。业务角色、用户名、状态等文本应使用内容比较:

boolean isAdmin = "admin".equals(role);

编码是语义的一部分:String.length() 是 UTF-16 code unit 数,不等于“用户看见的字符数”。字节转换显式指定字符集:

byte[] bytes = text.getBytes(StandardCharsets.UTF_8);
String decoded = new String(bytes, StandardCharsets.UTF_8);

字符串算法的常见切入点

  • 从两端比较:回文、反转、忽略无关字符;
  • 在连续区间里维护状态:最长无重复子串、最小覆盖子串;
  • 统计字符频率:异位词、包含关系;
  • 查找模式:子串匹配、前后缀、重复结构。

如果字符范围确定为小写字母,频率统计可用数组:

int[] count = new int[26];
for (char c : text.toCharArray()) {
    count[c - 'a']++;
}

这段代码的前提是输入已经确认属于 a-z。面对开放字符集或不可信输入,应该改用 Map,或先完成明确校验。


四、Hash 表:把状态变成可查询索引

Hash 表将 key -> value 保存起来。它先计算 key 的哈希,再将结果定位到某个桶,因此大多数查询和写入能在平均 O(1) 内完成。

key: "alice"
  ↓ hash
bucket[?]
  ↓
value: 用户资料 / 次数 / 下标 / 状态

它在题目里通常扮演三种角色

角色常见结构典型问题
集合HashSet是否出现过、去重
计数器HashMap<T, Integer>出现次数、词频、窗口频率
索引HashMap<T, Info>两数之和、最后位置、状态定位

Java HashMap:理解到什么程度

不同 key 可能落入同一个桶,这叫碰撞。现代 Java HashMap 通常以数组作为桶表:碰撞较少时桶内是链表,碰撞节点很多时可转为红黑树,以降低极端查找退化风险。

真正应记住的不是阈值,而是以下结论:

  • O(1) 是平均复杂度;碰撞、扩容和糟糕的 key 会带来额外成本;
  • equals() 为 true 的两个对象必须具有相同的 hashCode();
  • 放入 Map/Set 后,不要修改参与 equals/hashCode 的字段,否则对象可能再也查不出来;
  • HashMap 不是通用并发容器;多线程共享状态要从容器和业务原子性两方面考虑。

两数之和的思维

不要对每个数再遍历一遍找搭档。遍历到当前值时,查询“目标差值是否出现过”,再记录当前值的位置:

Map<Integer, Integer> indexByValue = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int need = target - nums[i];
    if (indexByValue.containsKey(need)) {
        return new int[] {indexByValue.get(need), i};
    }
    indexByValue.put(nums[i], i);
}

核心不是背模板,而是把“之前见过的数据”变成可以快速查询的状态。


五、三种高频算法模式

数组、字符串和 Hash 表最常在下面三种模式中组合出现。

1. 频率计数:元素 → 次数

Map<Character, Integer> freq = new HashMap<>();
for (char c : text.toCharArray()) {
    freq.put(c, freq.getOrDefault(c, 0) + 1);
}

它适合判断重复、比较字符构成、统计状态码、记录失败次数。若 key 范围有限,则用数组替代 Map。

2. 滑动窗口:维护连续区间的状态

窗口可以理解为一把移动的尺子:

s = a b c a b c b b
    L-----R

右指针扩展窗口,左指针在约束被破坏时缩小窗口。窗口内的信息可能是元素和、频率表,或者“字符最后出现的位置”。

Map<Character, Integer> lastIndex = new HashMap<>();
int left = 0, answer = 0;

for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    if (lastIndex.containsKey(c)) {
        left = Math.max(left, lastIndex.get(c) + 1);
    }
    lastIndex.put(c, right);
    answer = Math.max(answer, right - left + 1);
}

这里的 Math.max 防止左边界倒退,是理解这类题的典型边界点。

3. 前缀和 + Hash 表:历史状态 → 出现次数

当问题从“连续区间是什么”变成“某个历史累计状态以前出现过几次”时,前缀和与 Hash 表经常配合。Map 保存前缀和的出现次数,当前前缀和减目标值后查询 Map。

Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1);
int prefix = 0, answer = 0;

for (int num : nums) {
    prefix += num;
    answer += prefixCount.getOrDefault(prefix - k, 0);
    prefixCount.put(prefix, prefixCount.getOrDefault(prefix, 0) + 1);
}

六、从算法题走进工程

刷题给出了明确的 n 和输入范围;工程面对的是持续增长、来自外部、可能不可信的数据。因此相同的数据结构,在工程里还要补上生命周期、并发和资源上限。

爬虫中的 URL 去重

URL 去重最直观的形式是:

Set<String> seenUrls = new HashSet<>();
boolean shouldFetch(String normalizedUrl) {
    return seenUrls.add(normalizedUrl);
}

但关键在 normalizedUrl,而不是 HashSet:fragment、默认端口、域名大小写等是否应归为同一资源,必须由协议与业务规则定义。单机内存 Set 也不能无限增长;长期任务需要设计容量、过期、持久化或外部存储。

频率表、缓存与幂等

场景可映射的结构工程补充问题
错误码/域名统计数组或 Map 计数器统计周期、并发更新、内存上限
本地缓存Map<key, value>TTL、淘汰、敏感数据、跨实例一致性
请求幂等requestId -> state原子性、失败恢复、状态保留期
限流主体 -> 窗口计数key 的可信性、过期、代理链
批量处理数组/List最大批次、分页、部分失败、内存

一个重要的工程判断

算法题中,int[26]、int[n] 之类的数组通常是最优答案,因为边界题目已定义。工程中,客户端可能提交一个声称“有几十亿元素”的长度,也可能持续制造新的 URL、ID、标签和缓存 key。

因此工程代码除了选对结构,还要明确:

最大多少?保存多久?谁能写入?并发时是否正确?


七、Java 代码审计:从容器和字符串发现问题

代码审计不应只从危险函数开始。看到数组、List、Map、Set 或关键字符串时,也能先定位一批高价值问题。

先问四个问题

  1. 数据从哪来? 请求参数、Header、Cookie、JSON、数据库、消息还是可信配置?
  2. 数据会变多大? 有无长度、条数、频率、深度和生命周期限制?
  3. 数据最终去哪里? 数据库、HTML、文件系统、HTTP 客户端、日志、缓存还是权限判断?
  4. 谁拥有这个状态? 当前用户/租户、当前请求、单实例内存,还是多机共享状态?

数组与 List:长度、下标、共享

模式风险检查方向
new byte[clientLength]内存拒绝服务分配前校验非负和业务最大值,优先流式处理
list.get(requestIndex)越权或异常探测先按主体授权过滤资源,不以 index 代表权限
offset + limit整数溢出、超量查询用更大类型校验并限制分页上限
返回内部数组/List外部篡改内部状态防御性复制或不可变视图

Hash 表:无界增长与错误的安全语义

private static final Set<String> processedTaskIds = ConcurrentHashMap.newKeySet();

这段代码看起来是在做幂等,审计时要追问:taskId 是否由外部控制?集合会不会永远保留?多实例是否一致?处理失败后状态怎么办?

并发场景还要警惕“先查再写”:

if (!records.containsKey(requestId)) {
    executeSideEffect();
    records.put(requestId, "DONE");
}

即便 records 是 ConcurrentHashMap,这组业务操作也不是一个原子事务,仍可能重复执行副作用。

权限缓存的 key 也需要完整上下文。只用 userId 缓存权限,可能遗漏租户、角色版本或资源域,进而导致串租或撤权后仍可访问。

字符串:沿 Source → Transform → Sink 追踪

字符串安全问题关键在“解释上下文”。面对关键字符串,追踪:

Source(输入来源)
  ↓
Transform(解码、拼接、规范化、模板渲染)
  ↓
Sink(SQL、HTML、路径、URL、命令、日志、权限判断)
常见模式风险正确方向
拼接 SQLSQL 注入参数化查询
拼接 HTML/JSXSS与上下文匹配的输出编码/模板转义
拼接文件路径路径遍历解析、规范化后验证仍在基目录
用户输入构造请求 URLSSRF解析后校验协议、主机、端口和解析 IP
动态复杂正则ReDoS限制长度,避免高回溯表达式
记录完整请求/异常敏感信息泄露字段级脱敏与最小化日志

不要靠 contains("../") 或 startsWith("https://trusted") 这类字符串黑名单做安全判断。先按协议解析成结构,再对规范化后的结构做白名单校验。

数据结构哈希 ≠ 密码学哈希

hashCode() 的目标是容器分桶,不能用于密码保存、认证、签名或安全唯一标识。密码应使用专用密码派生算法;消息认证使用 HMAC 或签名方案;业务身份与权限必须依赖服务端可信的认证和授权逻辑。


八、模板与复盘清单

三个最值得记住的模板

去重:元素是否首次出现

Set<T> seen = new HashSet<>();
for (T item : items) {
    if (seen.add(item)) {
        // 第一次出现
    }
}

频率:元素 → 次数

Map<T, Integer> count = new HashMap<>();
for (T item : items) {
    count.put(item, count.getOrDefault(item, 0) + 1);
}

窗口:扩张、收缩、更新答案

int left = 0;
for (int right = 0; right < data.length; right++) {
    // 纳入 data[right]
    while (/* 窗口不合法 */) {
        // 移除 data[left]
        left++;
    }
    // 更新合法窗口的答案
}

一道题写完后,复盘这五件事


九、算法示例

442. 数组中重复的数据

我们先来读一遍题:给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 最多两次 。请你找出所有出现 两次 的整数,并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间(不包括存储输出所需的空间)的算法解决此问题。

其实,题目的边界是很清晰的:

  1. ums 的所有整数都在范围 [1, n] 内;
  2. 时间复杂度为O(n);
  3. 空间复杂度为O(1);

重复意味着什么呢?这道题便就有两个思路:1. 我们去遍历数组,然后标记他,如果对应数字是2那不就是重复了两次——也就是频率计数法;2.利用标记来进行(因为数组的范围是[1,n],所以不会出现999-1后没有对应的情况)

我第一次写的时候,没有注意到仅使用常量额外空间(不包括存储输出所需的空间),于是很自然的写出了hash算法,为什么?因为时间复杂度是O(n),可写入Hash后,空间花销会很大。

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();

        Map<Integer,Integer> map = new HashMap<>();
        for (int i=0;i < nums.length; i++){
            if (map.containsKey(nums[i])){
                duplicates.add(nums[i]);
            }else{
                map.put(nums[i],1);
            }
        }
        return duplicates;
    }
}

于是第一次跑完,发现时间花销很大,且空间不满足,于是便采用了数组,因为有界。于是,便有了如下的算法

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
    
        for (int i=0;i < nums.length; i++){
            int index = Math.abs(nums[i]) - 1;

            if (nums[index] < 0){
                duplicates.add(index + 1);
            }else{
                nums[index] = -nums[index];
            }
        }
        return duplicates;
    }
}

3. 无重复字符的最长子串

我们先读一下题目:给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。

我们确定一下边界:

  1. 一个字符串包含英文、数字、符号,所以采用ASCII就可表示(实际工程中可能还会有其他字符,所以就扩展到Unicode),所以有界为128

而一段最长子串里会发生什么呢,举个例子abcabcd,很自然的就会想到双指针去表示对不对?为什么,因为只有这样才可以标记出连续的子串——于是自然而然想到了滑窗。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] windows = new int[128];
        int left = 0,right = 0;
        int result = 0;

        while (right < s.length()){
            char c = s.charAt(right);
            windows[c]++;
            right++;

            while(windows[c]>1){
                windows[s.charAt(left)]--;
                left++;
            }
            result = Math.max(result,right-left);
        }
        return result;
    }
}

结语

数组让我们按位置快速访问,字符串让我们处理有顺序且有语义的文本,Hash 表让我们按 key 查询历史状态。

刷题时,把它们用来降低复杂度;工程中,把它们用来组织数据流;安全审计时,再多问一步:这个数据是否可信、是否有边界、最终会被谁解释,以及状态是否属于当前主体。

当这三层能连起来,算法就不再只是题库里的模板,而会成为写工程、做爬虫和审计代码时自然的判断工具。

Java


评论(0)

查看评论列表

暂无评论


发表评论

表情 颜文字
插入代码

欢迎来到小站哦~

avatar

困困小猫

常年看番、打游戏,宅属性满分。不过偶尔也会出去玩啦 我在这里还是个新手,各位大佬来访还请轻一点喷~orz 欢迎光临! 还有一定要看隐私政策哦!!!

66
文章
4
评论
2
用户