Hash table w PHP – in_array vs isset, SplQueue, SplFixedArray

Tablica w PHP to jeden z najczęściej używanych typów danych, ale mało kto zastanawia się jak działa pod spodem. PHP array to w rzeczywistości hash table – struktura danych, która pozwala na dostęp do elementów w czasie O(1). Pokazuję jak to działa, jakie ma konsekwencje praktyczne i gdzie tablice PHP zaskakują swoją wydajnością.

Czym jest hash table?

Hash table to struktura danych przechowująca pary klucz-wartość. Gdy zapisujesz element pod kluczem, funkcja haszująca zamienia klucz na indeks w wewnętrznej tablicy. Gdy chcesz odczytać wartość – ta sama funkcja wyznacza indeks w O(1).

<?php

// PHP array jako hash table - dostęp O(1) niezależnie od rozmiaru
$users = [
    'jan.kowalski' => ['id' => 1, 'role' => 'admin'],
    'anna.nowak'   => ['id' => 2, 'role' => 'user'],
    'piotr.wisz'   => ['id' => 3, 'role' => 'user'],
];

// O(1) - bez względu na to czy masz 3 czy 300 000 wpisów
$user = $users['jan.kowalski'];

in_array() vs isset() – O(n) vs O(1)

To jeden z najczęstszych błędów wydajnościowych w PHP. in_array() przeszukuje tablicę liniowo – sprawdza każdy element po kolei. isset() na tablicy asocjacyjnej korzysta z hash table – jest O(1):

<?php

$allowedSkus = ['SKU-001', 'SKU-002', 'SKU-003', /* ... 10 000 SKU */];

// O(n) - w najgorszym przypadku sprawdza wszystkie elementy
if (in_array('SKU-999', $allowedSkus)) {
    // ...
}

// Przepisz na tablicę asocjacyjną - O(1) zawsze
$allowedSkusMap = array_flip($allowedSkus);
// ['SKU-001' => 0, 'SKU-002' => 1, ...]

if (isset($allowedSkusMap['SKU-999'])) {
    // O(1) - natychmiastowy dostęp przez hash
}

Przy 10 elementach różnica jest niezauważalna. Przy 10 000 elementach sprawdzanych w pętli po każdym requeście – już bardzo realna. W Magento 2 taki wzorzec pojawia się np. przy walidacji SKU, sprawdzaniu uprawnień czy filtrowaniu kolekcji produktów w pamięci.

PHP array jako kolejka i stos

PHP array implementuje też interfejsy kolejki (FIFO) i stosu (LIFO) przez wbudowane funkcje:

<?php

// Stos (LIFO) - push/pop
$stack = [];
array_push($stack, 'pierwszy');
array_push($stack, 'drugi');
array_push($stack, 'trzeci');

echo array_pop($stack); // 'trzeci' - ostatni wchodzi, pierwszy wychodzi
echo array_pop($stack); // 'drugi'

// Krótszy zapis dla stosu
$stack[] = 'element'; // push
$last = array_pop($stack); // pop

// Kolejka (FIFO) - enqueue/dequeue
$queue = [];
array_push($queue, 'pierwsze zadanie');
array_push($queue, 'drugie zadanie');

echo array_shift($queue); // 'pierwsze zadanie' - FIFO
echo array_shift($queue); // 'drugie zadanie'

Uwaga: array_shift() jest O(n) – po usunięciu pierwszego elementu PHP przenumerowuje wszystkie klucze numeryczne. Jeśli potrzebujesz wydajnej kolejki na tysiącach elementów, rozważ SplQueue z biblioteki SPL.

SplStack i SplQueue – gdy wydajność ma znaczenie

<?php

// SplStack - O(1) dla push i pop
$stack = new \SplStack();
$stack->push('pierwszy');
$stack->push('drugi');
echo $stack->pop(); // 'drugi'

// SplQueue - O(1) dla enqueue i dequeue
$queue = new \SplQueue();
$queue->enqueue('zadanie 1');
$queue->enqueue('zadanie 2');
echo $queue->dequeue(); // 'zadanie 1'

// SplMinHeap - kolejka priorytetowa, O(log n) dla insert i extract
$heap = new \SplMinHeap();
$heap->insert(['priority' => 3, 'task' => 'Niski priorytet']);
$heap->insert(['priority' => 1, 'task' => 'Wysoki priorytet']);
$heap->insert(['priority' => 2, 'task' => 'Średni priorytet']);

while (!$heap->isEmpty()) {
    $item = $heap->extract();
    echo $item['task'] . PHP_EOL;
}
// Wysoki priorytet
// Średni priorytet
// Niski priorytet

Zużycie pamięci – PHP array vs SplFixedArray

PHP array jest wygodna, ale pamięciożerna – każdy element przechowuje dodatkowe metadane (typ klucza, typ wartości, wskaźniki do poprzedniego i następnego elementu w ordered map). Przy dużych zbiorach numerycznych SplFixedArray zużywa znacznie mniej pamięci:

<?php

$size = 100000;

// Zwykła tablica PHP
$start = memory_get_usage();
$arr = range(0, $size - 1);
$phpArrayMemory = memory_get_usage() - $start;

// SplFixedArray - tylko indeksy numeryczne, stały rozmiar
$start = memory_get_usage();
$fixed = SplFixedArray::fromArray(range(0, $size - 1));
$fixedMemory = memory_get_usage() - $start;

echo 'PHP array:     ' . number_format($phpArrayMemory / 1024 / 1024, 2) . ' MB' . PHP_EOL;
echo 'SplFixedArray: ' . number_format($fixedMemory / 1024 / 1024, 2) . ' MB' . PHP_EOL;
// PHP array:     ~8 MB
// SplFixedArray: ~2 MB

Podsumowanie

PHP array to jeden z najbardziej wszechstronnych typów danych w jakimkolwiek języku programowania – hash table, stos, kolejka i lista w jednym. Kluczowe rzeczy do zapamiętania: dostęp przez klucz to O(1), in_array() to O(n) – zastępuj przez isset() na odwróconej tablicy gdy wydajność ma znaczenie, a przy dużych zbiorach numerycznych rozważ SplFixedArray.