Boost PHP Array Intersection and Union Performance with Hash Tables

Introduction

Array intersection and union operations are common in PHP, particularly when working with large data sets. However, these operations can become performance bottlenecks. This article explores how to optimize them using hash tables, reducing the time complexity from O(n * m) to O(n + m).

What Is a Hash Table?

A hash table is a data structure that stores data in key-value pairs. Its main advantage is the ability to perform fast lookups and inserts, typically in constant time. This makes it a great fit for optimizing array operations like intersections and unions in PHP.

Optimizing Array Intersection

The traditional method uses in_array to check if elements exist in another array, which has a time complexity of O(n * m). Here's how it can be optimized using a hash table:

function intersect_hash($arr1, $arr2) {
  $lookup = [];

  foreach ($arr1 as $value) {
    $lookup[$value] = true;
  }

  $result = [];
  foreach ($arr2 as $value) {
    if (isset($lookup[$value])) {
      $result[] = $value;
    }
  }

  return $result;
}

This optimized version only loops through each array once, resulting in a time complexity of O(n + m).

Optimizing Array Union

Array unions can be optimized similarly. You can use a hash table to store all unique elements from both arrays:

function union($arr1, $arr2) {
  $lookup = [];

  foreach ($arr1 as $value) {
    $lookup[$value] = true;
  }

  foreach ($arr2 as $value) {
    $lookup[$value] = true;
  }

  $result = array_keys($lookup);
  return $result;
}

Just like the intersection function, this approach runs in O(n + m) time, efficiently removing duplicates.

Performance Comparison

Here’s a performance test using two arrays of 100,000 and 50,000 elements respectively. The table below compares the average execution time between the traditional and optimized implementations:

As shown, the hash table approach dramatically improves performance for both operations.

Conclusion

Using hash tables to optimize array intersection and union operations in PHP is a simple yet powerful technique. It significantly boosts performance, especially with large datasets, and is easy to implement in real-world applications.