如何判断两个无序长字符串数组是否完全相等？

嘿，这个问题我太有发言权了——之前做过一个批量处理超长文本的工具，一开始用排序对比差点把服务器跑崩，后来折腾出几个靠谱的优化方案，给你唠唠：

1. 哈希统计法（性能最优，优先选） #

核心思路就是把超长字符串的对比转换成短哈希值的统计对比，毕竟对比100位的字符串和对比一个8位的哈希值，性能差了不止一个量级。

具体步骤：

• 给每个字符串计算一个唯一的哈希值（可以用轻量的自定义多项式哈希，也可以用MD5/SHA这类加密哈希，前者更快）
• 分别统计两个数组中每个哈希值出现的次数
• 如果两个统计结果完全一致，就认为数组相等

为什么好用？ #

• 哈希计算只需要对每个字符串做一次O(k)的遍历（k是字符串长度），后续所有对比都是O(1)的哈希值对比，整体时间复杂度是O(n*k)，比排序的O(n log n *k)快太多
• 就算数组里有大量重复字符串，哈希统计也能高效处理

注意点：哈希碰撞怎么办？ #

概率极低，但如果是对正确性要求极高的场景，可以：

• 用双重哈希：同时计算两个不同的哈希值（比如一个多项式哈希+一个MD5），用组合键作为统计的key，碰撞概率几乎为0
• 或者在哈希统计一致后，对每个哈希对应的原字符串做一次抽样/全量对比（只在哈希匹配时才做，所以额外开销很小）

示例代码（JavaScript） #

// 自定义轻量多项式哈希，比加密哈希更快
function computeLightHash(str) {
    let hash = 0;
    const MOD = 10**9 + 7;
    const BASE = 911382629;
    for (let i = 0; i < str.length; i++) {
        hash = (hash * BASE + str.charCodeAt(i)) % MOD;
    }
    return hash.toString();
}

function areArraysEqual(arr1, arr2) {
    if (arr1.length !== arr2.length) return false;

    const hashCount1 = new Map();
    // 统计第一个数组的哈希出现次数
    for (const str of arr1) {
        const hash = computeLightHash(str);
        hashCount1.set(hash, (hashCount1.get(hash) || 0) + 1);
    }

    // 遍历第二个数组，实时校验计数
    for (const str of arr2) {
        const hash = computeLightHash(str);
        if (!hashCount1.has(hash)) return false;
        const currentCount = hashCount1.get(hash) - 1;
        if (currentCount < 0) return false;
        hashCount1.set(hash, currentCount);
    }

    // 确保所有哈希的计数都清零了
    return [...hashCount1.values()].every(count => count === 0);
}

2. 计数分组法（适合字符串种类少的场景） #

如果你的数组里重复的字符串种类不多（比如就几种超长字符串反复出现），可以直接用原字符串作为键，统计出现次数：

• 遍历第一个数组，用Map记录每个字符串的出现次数
• 遍历第二个数组，每遇到一个字符串就把对应计数减1，一旦遇到不存在的字符串或者计数变负，直接返回false
• 最后检查所有计数是否都为0

这种方法不用算哈希，但如果字符串种类多，用超长字符串作为Map键的开销还是会比哈希大，所以只适合特定场景。

3. 排序优化：先哈希再排序哈希数组 #

如果一定要用排序的思路，那别直接排序原字符串，先把每个字符串转成哈希值，排序哈希数组，再对比排序后的哈希数组是否一致。

常规排序需要O(n log n)次字符串对比（每次O(k)），而这个只需要O(n log n)次哈希对比（每次O(1)），加上O(n*k)的哈希计算时间，整体性能比原方法提升很多。

内容的提问来源于stack exchange，提问作者TBXark VFanx