Hash Table – PHP implementation, O(1) lookup, deduplication and grouping

A hash table is a data structure with O(1) for insert, lookup and delete on average. PHP uses it internally for arrays – every PHP array is effectively a hash map. But knowing how it works under the hood lets you write more efficient code and understand why certain operations are fast and others surprisingly slow.

How a hash table works

A hash table stores key-value pairs. The key is transformed by a hash function into an index of the internal array (bucket). On collision (two keys produce the same index) one of two techniques is used: chaining (linked list in the bucket) or open addressing (searching for the next free slot). PHP uses chaining.

Key "sku"   -> hash() -> 42 -> bucket[42] -> "SKU-001"
Key "price" -> hash() -> 17 -> bucket[17] -> 99.99
Key "name"  -> hash() -> 42 -> bucket[42] -> collision! -> list: "SKU-001" -> "Widget"

PHP implementation

<?php

declare(strict_types=1);

class HashTable
{
    private array $buckets;
    private int   $size;
    private int   $count = 0;

    private const LOAD_FACTOR = 0.75;

    public function __construct(int $initialSize = 16)
    {
        $this->size    = $initialSize;
        $this->buckets = array_fill(0, $initialSize, null);
    }

    private function hash(string $key): int
    {
        // djb2 - simple but good hash function
        $hash = 5381;
        $len  = strlen($key);
        for ($i = 0; $i < $len; $i++) {
            $hash = (($hash << 5) + $hash) + ord($key[$i]);
            $hash &= 0x7FFFFFFF;
        }
        return $hash % $this->size;
    }

    public function set(string $key, mixed $value): void
    {
        if ($this->count / $this->size >= self::LOAD_FACTOR) {
            $this->resize();
        }

        $index   = $this->hash($key);
        $current = $this->buckets[$index];

        while ($current !== null) {
            if ($current['key'] === $key) {
                $current['value'] = $value;
                return;
            }
            $current = $current['next'];
        }

        $this->buckets[$index] = [
            'key'   => $key,
            'value' => $value,
            'next'  => $this->buckets[$index],
        ];
        $this->count++;
    }

    public function get(string $key): mixed
    {
        $index   = $this->hash($key);
        $current = $this->buckets[$index];

        while ($current !== null) {
            if ($current['key'] === $key) return $current['value'];
            $current = $current['next'];
        }

        return null;
    }

    public function delete(string $key): bool
    {
        $index = $this->hash($key);

        if ($this->buckets[$index] === null) return false;

        if ($this->buckets[$index]['key'] === $key) {
            $this->buckets[$index] = $this->buckets[$index]['next'];
            $this->count--;
            return true;
        }

        $prev = $this->buckets[$index];
        while ($prev['next'] !== null) {
            if ($prev['next']['key'] === $key) {
                $prev['next'] = $prev['next']['next'];
                $this->count--;
                return true;
            }
            $prev = $prev['next'];
        }

        return false;
    }

    private function resize(): void
    {
        $oldBuckets    = $this->buckets;
        $this->size   *= 2;
        $this->buckets = array_fill(0, $this->size, null);
        $this->count   = 0;

        foreach ($oldBuckets as $bucket) {
            while ($bucket !== null) {
                $this->set($bucket['key'], $bucket['value']);
                $bucket = $bucket['next'];
            }
        }
    }

    public function count(): int { return $this->count; }
}

Practical uses in PHP

<?php

// 1. Deduplication - O(n) instead of O(n²) via array_unique
function deduplicateSkus(array $skus): array
{
    $seen   = [];
    $result = [];
    foreach ($skus as $sku) {
        if (!isset($seen[$sku])) {  // isset on array = O(1) lookup
            $seen[$sku] = true;
            $result[]   = $sku;
        }
    }
    return $result;
}

// 2. Group products by category - O(n)
function groupByCategory(array $products): array
{
    $grouped = [];
    foreach ($products as $product) {
        $grouped[$product['category']][] = $product;
    }
    return $grouped;
}

// 3. Lookup table instead of loop - O(1) instead of O(n)
$statusLabels = [
    'pending'    => 'Pending payment',
    'processing' => 'Processing',
    'complete'   => 'Complete',
    'cancelled'  => 'Cancelled',
];

$label = $statusLabels[$orderStatus] ?? 'Unknown';  // O(1)

When PHP array (hash table) has worse O(1)

<?php

// PHP array has a fixed overhead per element: ~80 bytes (64-bit)
// 1,000,000 elements = ~80 MB just for the structure
// For very large sets - consider SplFixedArray (much less memory)

$fixed = new SplFixedArray(1000000);  // fixed-size array
// $fixed uses ~8 MB instead of ~80 MB for 1M ints

// array_key_exists vs isset - both O(1), but different result for null:
$a = ['key' => null];
isset($a['key']);             // false (null = does not exist for isset)
array_key_exists('key', $a); // true

Summary

Hash table is the foundation of PHP performance – every PHP array is an optimised hash map. Key lookup is O(1). Grouping, deduplication and building indexes through associative arrays are faster than loops with comparisons. Keep in mind the memory overhead with large datasets and the difference between isset and array_key_exists for null values.