Hash Table

Also Known As

TL;DR

Explanation

A hash function converts a key to an array index. Collisions (two keys hashing to the same index) are resolved by chaining (linked list per bucket) or open addressing (probing for the next free slot). PHP arrays are hash tables internally, which is why isset() is O(1) but in_array() is O(n). Understanding hash tables explains why flipping an array enables O(1) lookups.

Diagram

flowchart TD
    K1[key: email] & K2[key: name] & K3[key: age] --> HASH[Hash Function]
    HASH --> B1[Bucket 1: email - alice@...]
    HASH --> B3[Bucket 3: name - Alice]
    HASH --> B4[Bucket 4: age - 30]
    B1 -->|collision chaining| B1B[another key - value]
    INFO[O of 1 average lookup<br/>O of n worst case with collisions]
style HASH fill:#6e40c9,color:#fff
style B1 fill:#238636,color:#fff
style B3 fill:#238636,color:#fff
style B4 fill:#238636,color:#fff
style INFO fill:#1f6feb,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Using in_array() in a loop — O(n) per call makes the loop O(n²); flip the array for O(1) lookup.
• Not understanding that hash collisions degrade performance — a poor hash function can make O(1) into O(n).
• Using objects as hash keys in PHP without SplObjectStorage or WeakMap — objects are not valid array keys.
• Assuming hash table iteration order — PHP arrays preserve insertion order but most hash table implementations do not.

Code Examples

// O(n²) — in_array inside a loop:
$banned = ['alice', 'bob', 'charlie']; // Could be 10,000 entries
foreach ($users as $user) {
    if (in_array($user->name, $banned)) block($user); // O(n) per iteration
}

// O(n) total — flip for O(1) lookup:
$banned = array_flip(['alice', 'bob', 'charlie']);
foreach ($users as $user) {
    if (isset($banned[$user->name])) block($user); // O(1) per iteration
}

References

• ↗ https://en.wikipedia.org/wiki/Hash_table

Tags

Related Terms