Hash Table – implementacja w PHP, O(1) lookup, deduplikacja i grupowanie

Tablica haszująca (hash table) to struktura danych z O(1) dla wstawiania, wyszukiwania i usuwania w przypadku średnim. PHP używa jej wewnętrznie dla tablic – każda tablica PHP to de facto hash mapa. Ale wiedza o tym jak działa pod spodem pozwala pisać wydajniejszy kod i rozumieć dlaczego pewne operacje są szybkie a inne zaskakująco wolne.

Jak działa hash table

Hash table przechowuje pary klucz-wartość. Klucz jest przekształcany przez funkcję hashującą w indeks tablicy wewnętrznej (bucket). Przy kolizji (dwa klucze dają ten sam indeks) używa się jednej z technik: łańcuchowania (lista połączona w buckecie) lub otwartego adresowania (szukanie kolejnego wolnego miejsca). PHP używa łańcuchowania.

Klucz "sku"    -> hash() -> 42 -> bucket[42] -> "SKU-001"
Klucz "price"  -> hash() -> 17 -> bucket[17] -> 99.99
Klucz "name"   -> hash() -> 42 -> bucket[42] -> kolizja! -> lista: "SKU-001" -> "Widget"

Implementacja w PHP

<?php

declare(strict_types=1);

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

    private const LOAD_FACTOR = 0.75; // maksymalne wypełnienie przed rehash

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

    private function hash(string $key): int
    {
        // djb2 - prosta ale dobra funkcja hashująca
        $hash = 5381;
        $len  = strlen($key);
        for ($i = 0; $i < $len; $i++) {
            $hash = (($hash << 5) + $hash) + ord($key[$i]);
            $hash &= 0x7FFFFFFF; // utrzymaj 31 bitów
        }
        return $hash % $this->size;
    }

    public function set(string $key, mixed $value): void
    {
        // Rehash jeśli load factor przekroczony
        if ($this->count / $this->size >= self::LOAD_FACTOR) {
            $this->resize();
        }

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

        // Sprawdź czy klucz już istnieje (aktualizacja)
        while ($current !== null) {
            if ($current['key'] === $key) {
                $current['value'] = $value;
                return;
            }
            $current = $current['next'];
        }

        // Nowy węzeł na początku łańcucha (chaining)
        $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; // klucz nie istnieje
    }

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

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

        // Usuń z początku listy
        if ($this->buckets[$index]['key'] === $key) {
            $this->buckets[$index] = $this->buckets[$index]['next'];
            $this->count--;
            return true;
        }

        // Usuń ze środka lub końca listy
        $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;

        // Przepisz wszystkie elementy z nowym hashem
        foreach ($oldBuckets as $bucket) {
            while ($bucket !== null) {
                $this->set($bucket['key'], $bucket['value']);
                $bucket = $bucket['next'];
            }
        }
    }

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

Praktyczne zastosowania w PHP

<?php

// 1. Deduplikacja - O(n) zamiast O(n²) przez array_unique
function deduplicateSkus(array $skus): array
{
    $seen   = [];
    $result = [];
    foreach ($skus as $sku) {
        if (!isset($seen[$sku])) {  // isset na tablicy = O(1) lookup
            $seen[$sku]   = true;
            $result[]     = $sku;
        }
    }
    return $result;
}

// 2. Grupowanie produktów po kategorii - O(n)
function groupByCategory(array $products): array
{
    $grouped = [];
    foreach ($products as $product) {
        $grouped[$product['category']][] = $product;
        // Dostęp do $grouped[$category] to O(1) - PHP array = hash table
    }
    return $grouped;
}

// 3. Lookup table zamiast pętli - O(1) zamiast O(n)
$statusLabels = [
    'pending'    => 'Oczekujące',
    'processing' => 'W realizacji',
    'complete'   => 'Zakończone',
    'cancelled'  => 'Anulowane',
];

// Zamiast:
// foreach ($statuses as $s) { if ($s['code'] === $status) return $s['label']; }
// Użyj:
$label = $statusLabels[$orderStatus] ?? 'Nieznany';  // O(1)

Kiedy PHP array (hash table) ma gorsze O(1)

<?php

// Kolizje hashów mogą degradować do O(n) - ale PHP to obsługuje dobrze
// Bardziej praktyczny problem: rozmiar tablicy i zużycie pamięci

// PHP array ma stały overhead per element: ~80 bajtów (64-bit)
// 1 000 000 elementów = ~80 MB tylko na strukturę
// Dla bardzo dużych zbiorów - rozważ SplFixedArray (dużo mniej pamięci)

$fixed = new SplFixedArray(1000000);  // tablica o stałym rozmiarze
// $fixed używa ~8 MB zamiast ~80 MB dla 1M intów

// array_key_exists vs isset - oba O(1), ale różny wynik dla null:
$a = ['key' => null];
isset($a['key']);            // false (null = nie istnieje dla isset)
array_key_exists('key', $a); // true

Podsumowanie

Hash table to fundament wydajności PHP – każda tablica PHP to zoptymalizowana hash mapa. Lookup po kluczu to O(1). Grupowanie, deduplikacja i budowanie indeksów przez tablice asocjacyjne są szybsze niż pętle z porównaniami. Warto pamiętać o overhead pamięciowym przy dużych zbiorach i o różnicy między isset a array_key_exists przy wartościach null.