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

A PHP array is one of the most-used data types, but few people think about how it works under the hood. A PHP array is actually a hash table – a data structure that allows O(1) element access. I show how it works, what the practical implications are, and where PHP arrays surprise you with their performance characteristics.

What is a hash table?

A hash table stores key-value pairs. A hash function converts the key to an index, allowing O(1) access regardless of the number of elements:

<?php

// PHP array as hash table - O(1) access whether you have 3 or 300,000 entries
$users = [
    'jan.kowalski' => ['id' => 1, 'role' => 'admin'],
    'anna.nowak'   => ['id' => 2, 'role' => 'user'],
    'piotr.wisz'   => ['id' => 3, 'role' => 'user'],
];

$user = $users['jan.kowalski']; // O(1)

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

One of the most common performance mistakes in PHP. in_array() scans linearly. isset() on an associative array uses the hash table – O(1):

<?php

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

// O(n) - checks every element in the worst case
if (in_array('SKU-999', $allowedSkus)) {
    // ...
}

// Rewrite as associative array - O(1) always
$allowedSkusMap = array_flip($allowedSkus);
// ['SKU-001' => 0, 'SKU-002' => 1, ...]

if (isset($allowedSkusMap['SKU-999'])) {
    // O(1) - instant access through hash
}

At 10 elements the difference is imperceptible. At 10,000 elements checked in a loop on every request – very much real.

PHP array as queue and stack

<?php

// Stack (LIFO) - push/pop
$stack = [];
array_push($stack, 'first');
array_push($stack, 'second');
array_push($stack, 'third');
echo array_pop($stack); // 'third'

// Shorthand
$stack[] = 'element'; // push
$last    = array_pop($stack); // pop

// Queue (FIFO) - enqueue/dequeue
$queue = [];
array_push($queue, 'first task');
array_push($queue, 'second task');
echo array_shift($queue); // 'first task' - FIFO

Note: array_shift() is O(n) – after removing the first element PHP renumbers all numeric keys. For a performant queue on thousands of elements use SplQueue.

SplStack and SplQueue – when performance matters

<?php

// SplStack - O(1) for push and pop
$stack = new \SplStack();
$stack->push('first');
$stack->push('second');
echo $stack->pop(); // 'second'

// SplQueue - O(1) for enqueue and dequeue
$queue = new \SplQueue();
$queue->enqueue('task 1');
$queue->enqueue('task 2');
echo $queue->dequeue(); // 'task 1'

// SplMinHeap - priority queue, O(log n) for insert and extract
$heap = new \SplMinHeap();
$heap->insert(['priority' => 3, 'task' => 'Low priority']);
$heap->insert(['priority' => 1, 'task' => 'High priority']);
$heap->insert(['priority' => 2, 'task' => 'Medium priority']);

while (!$heap->isEmpty()) {
    $item = $heap->extract();
    echo $item['task'] . PHP_EOL;
}
// High priority
// Medium priority
// Low priority

Memory usage – PHP array vs SplFixedArray

<?php

$size = 100000;

$start = memory_get_usage();
$arr   = range(0, $size - 1);
$phpArrayMemory = memory_get_usage() - $start;

$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

Summary

PHP array is one of the most versatile data types in any programming language – hash table, stack, queue and list in one. Key takeaways: key access is O(1), in_array() is O(n) – replace with isset() on a flipped array when performance matters, and for large numeric sets consider SplFixedArray.