如何用JavaScript在百万级多维数组B中快速查找数组A？

Great question! When dealing with multi-dimensional arrays that scale to millions of elements, a naive linear scan can quickly become a bottleneck. Let’s walk through an optimized approach to find your target array efficiently, plus a working implementation tailored to your example.

Core Approach: Hashing for Fast Lookups #

Instead of checking every subarray in B one by one (which has a time complexity of O(N*M), where N is the number of subarrays and M is their length), we can use hashing to cut down lookup time to nearly O(1) after an initial preprocessing step:

• First, convert each subarray in B into a unique, consistent hash value (like a string or numeric code) and store these hashes in a map/dictionary, paired with the original subarray.
• When searching for array A, generate its hash and check if it exists in the map—this lets us instantly retrieve the matching subarray (or confirm it doesn’t exist).

Working JavaScript Implementation #

Using your example data, here’s a function that returns the matching subarray if found, or false otherwise:

function findTargetArray(A, multiArray) {
    // Preprocess the large array into a hash map
    const subarrayMap = new Map();
    for (const subarray of multiArray) {
        // Use JSON.stringify for a consistent hash (adjust for your element types)
        const hashKey = JSON.stringify(subarray);
        // Store the subarray (overwrites duplicates; use an array if you need all matches)
        subarrayMap.set(hashKey, subarray);
    }

    // Generate hash for the target array
    const targetHash = JSON.stringify(A);
    
    // Return the match or false if not found
    return subarrayMap.get(targetHash) || false;
}

// Test with your sample data
const A = ["A0", "B0", "C0", "D2", "E2", "F0", "G2"];
const B = [
    ["X0", "O0", "I0", "Z2", "T2", "L0", "V2"],
    ["I0", "V2", "O0", "T0", "L4", "X0", "Z3"],
    ["A0", "B0", "C0", "D2", "E2", "F0", "G2"],
    ["Z2", "L7", "T0", "I1", "V3", "X0", "O0"],
    ["Z3", "I1", "O0", "T3", "X0", "L2", "V2"],
    ["O0", "X0", "I1", "T2", "V0", "Z3", "L2"],
    ["I0", "Z0", "L7", "X0", "V3", "O0", "T3"],
    ["L3", "X0", "I1", "O0", "V0", "Z1", "T1"]
];

console.log(findTargetArray(A, B)); // Output: ["A0", "B0", "C0", "D2", "E2", "F0", "G2"]
console.log(findTargetArray(["NotHere"], B)); // Output: false

Optimizations for Million-Scale Data #

If your B has millions of subarrays, tweak the implementation for better performance:

• Faster hashing: JSON.stringify is convenient but not the fastest. For string-only subarrays, use subarray.join('|') (just ensure your elements don’t contain the separator |).
• Memory savings: If you only need a boolean result (not the actual subarray), store true in the map instead of the full subarray.
• Incremental preprocessing: If B is built dynamically, add each subarray to the map as it’s created instead of processing the entire array at once.

Edge Cases to Handle #

• Duplicate subarrays: The function above returns the last occurrence. To get all matches, store an array of subarrays/indexes in the map instead of a single value.
• Empty subarrays: Ensure your hashing method handles empty arrays correctly (both in A and B).
• Non-string elements: If subarrays contain numbers or objects, JSON.stringify still works, but custom join methods will need adjustments (e.g., convert elements to strings first).

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