为何O(n²)复杂度的字母异位词映射算法比O(n)的更快？

给定两个列表A和B，其中B是A的字母异位词（即B由A的元素随机排列而成），且两列表可能包含重复元素。我们需要找到从A到B的索引映射P，P[i] = j表示A的第i个元素出现在B的第j个位置。例如：

A = [12, 28, 46, 32, 50]，B = [50, 12, 32, 46, 28]，应返回[1, 4, 3, 2, 0]

我实现了一个时间复杂度为O(n²)的算法：

public int[] anagramMappings(int[] A, int[] B) { 
    int[] result = new int[100]; 
    int count = 0; 
    for (int i = 0; i < A.length; i++) { 
        for (int j = 0; j < B.length; j++) { 
            if (A[i] == B[j]) { 
                result[i] = j; 
                count++; 
                break; 
            } 
        } 
    } 
    int[] tempArray = new int[count]; 
    for (int i = 0; i < count; i++) { 
        tempArray[i] = result[i]; 
    } 
    return tempArray; 
}

还有一个我认为时间复杂度为O(n)的更高效算法：

public int[] anagramMappingsx(int[] A, int[] B) { 
    int[] res = new int[A.length]; 
    int index = 0; 
    Map<Integer, Integer> map = new HashMap<>(); 
    for (int i = 0; i < B.length; i++) { 
        if (!map.containsKey(B[i])) { 
            map.put(B[i], i); 
        } 
    } 
    for (Integer i : A) { 
        if (map.containsKey(i)) { 
            res[index++] = map.get(i); 
        } 
    } 
    return res; 
}

但测试发现O(n²)的算法几乎总是执行得更快，我想知道这一现象的原因。

其实这种现象在小规模数据场景下非常常见，主要有以下几个原因：

• 额外开销的抵消：虽然HashMap的时间复杂度是O(n)，但它带来了不少额外开销：比如哈希值的计算、Integer类型的装箱拆箱（因为你用了Map<Integer, Integer>，而数组元素是int基本类型，每次put和get都会自动完成基本类型和包装类型的转换，产生临时对象）、哈希冲突的处理（哪怕冲突很少，也会有分支判断的开销）。而当数组长度n不大时，O(n²)的双重循环总操作次数其实非常有限（比如n=100时最多10000次简单的整数比较），这些额外开销加起来反而超过了双重循环的成本。

• JVM对数组循环的极致优化：Java的基本类型数组循环会被JVM做大量优化，比如循环展开（把多次循环合并成一次，减少循环判断次数）、消除数组边界检查（JVM能判断出你的循环不会越界，从而跳过每次的边界校验）、甚至直接编译成接近原生机器码的指令，执行效率极高。而HashMap的put和get方法包含大量分支逻辑，会干扰CPU的分支预测，降低执行效率。

• 缓存友好性的差异：数组是连续的内存块，CPU在访问数组元素时，会自动把相邻的元素预读到高速缓存中，缓存命中率非常高；而HashMap的底层是桶数组加链表/红黑树，元素的内存地址是分散的，缓存命中率低，每次访问都可能需要从主内存读取，带来更高的延迟。

另外还要提一下，你的HashMap实现存在一个小问题：如果B中包含重复元素，这个实现只会存储每个元素最后一次出现的索引，比如B=[2,2]、A=[2,2]时，返回的结果会是[1,1]，但实际上符合要求的映射应该是[0,1]或者[1,0]，不过这并不影响我们讨论执行速度的问题。

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