PHP多维数组双列查重：两种算法性能对比及更优方案

我有SQL和Sharepoint两个多维数组，需要基于两列（数组索引0和1对应的列）检测重复项。目前已经有两种可行的实现算法，但不清楚哪种速度更快，也想了解是否存在更高效的实现方式。

算法1 #

foreach($SQL as $data1) {    
  foreach($Sharepoint as $data2) {     
    if( ($data1[0] === $data2[0]) && ($data1[1] === $data2[1])) $duplicate = true;
 }
}

• 性能特点：时间复杂度为O(n*m)，n是SQL数组长度，m是Sharepoint数组长度。每遍历一个SQL元素，就要完整遍历一次Sharepoint数组，数据量增大时速度会断崖式下降，只适合极小数据量场景。

算法2 #

foreach($SQL as $data1) {    

  $keys = array_keys(array_column($Sharepoint, 0), $data1[0]);
  $tmp1 = array_map(function($k) use ($Sharepoint){return $Sharepoint[$k];}, $keys);
  $keys = array_keys(array_column($tmp1 , 1), $data1[1]); 
  $tmp2 = array_map(function($k) use ($tmp1 ){return $tmp1 [$k];}, $keys);
  if (count($tmp2) > 0) $duplicate = true;
}

• 性能特点：时间复杂度为O(n*(m + k))，k是第一次筛选后的数组长度。通过两次列筛选缩小范围，比算法1高效，但每次循环都要重复处理Sharepoint数组，仍有不必要的计算损耗，数据量大时性能提升有限。

最优思路是先对其中一个数组（比如Sharepoint）做哈希表预处理，用两列的组合值作为键，后续查询重复项的时间复杂度可降至O(1)，整体时间复杂度变为O(n + m)，性能提升显著。

示例代码：

// 预处理Sharepoint数组，生成两列组合为键的哈希表
$sharepointMap = [];
foreach($Sharepoint as $data) {
    // 用不会冲突的分隔符拼接两列值作为唯一键，避免值包含分隔符的话可换用其他方式
    $key = $data[0] . '|' . $data[1];
    $sharepointMap[$key] = true;
}

// 遍历SQL数组快速检测重复
$duplicate = false;
foreach($SQL as $data) {
    $key = $data[0] . '|' . $data[1];
    if(isset($sharepointMap[$key])) {
        $duplicate = true;
        // 找到重复后直接跳出循环，减少不必要的遍历
        break;
    }
}

• 注意：如果两列的值可能包含拼接用的分隔符（比如"|"），可以改用serialize([$data[0], $data[1]])或hash('sha256', $data[0] . $data[1])生成唯一键，不过拼接分隔符的方式性能最优。

1. 算法1：实现最简单，但效率最低，仅适合极小数据量。
2. 算法2：比算法1高效，但仍有重复计算，数据量大时表现一般。
3. 哈希表预处理方案：效率最高，线性时间复杂度，适合绝大多数场景，尤其是数据量较大的情况。

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