You've been using PHP associative arrays since day one of this course. They're great—practically magic. You throw a string key in, you get a value back, and you don't have to worry about how PHP actually finds that value in memory. But if you're going to be a senior engineer, you can't treat the core of your language as a black box. Today, I want to pull back the curtain and actually build a rudimentary hash table from scratch using a basic indexed array.

The search for a faster lookup

Let's imagine we're building a simple cache for a user permission system. I have a few usernames, and I need to store their access levels. If I use a standard indexed array, I have to loop through every single element to find the right user. That's $O(n)$ time complexity, and it's a nightmare once you hit a few thousand users.

$users = [
    ['name' => 'alice', 'level' => 'admin'],
    ['name' => 'bob', 'level' => 'editor'],
    ['name' => 'charlie', 'level' => 'guest'],
];

// To find 'bob', I have to loop. Boring and slow.

I want to be able to jump directly to the index where "bob" is stored without looping. In a perfect world, "bob" would just *be* the index. But arrays don't take strings as indices in a low-level sense; they take integers. So, I need a way to turn the string "bob" into a consistent integer.

Trying a basic hashing function

I'll start by creating a fixed-size array of "buckets." Let's keep it small—say, 10 slots—so we can actually see what's happening. I'll use crc32(), which is a fast way to turn a string into a 32-bit integer, and then use the modulo operator (%) to make sure that number fits within my 10 buckets.

$buckets = array_fill(0, 10, null);

function getIndex($key, $size) {
    return abs(crc32($key)) % $size;
}

$user = 'alice';
$index = getIndex($user, 10); // Let's say this returns 4
$buckets[$index] = 'admin';

echo "Alice is at index $index";

This feels like a win. I've mapped a string to a specific integer index. Now I can find Alice instantly. But wait—what happens when I add Bob?

The collision problem

I'm going to add Bob and Charlie to the mix. Here is where the "magic" usually breaks. Because I only have 10 buckets, it's statistically inevitable that two different strings will eventually hash to the same index. This is called a collision.

$usersToStore = [
    'alice' => 'admin',
    'bob' => 'editor',
    'charlie' => 'guest'
];

foreach ($usersToStore as $name => $level) {
    $index = getIndex($name, 10);
    echo "Storing $name at $index\n";
    $buckets[$index] = $level;
}

If I run this and find that both 'alice' and 'charlie' map to index 4, Charlie will simply overwrite Alice. My data is gone. This is the fundamental problem of hash tables. I can't just store the value at the index; I need a way to handle multiple items that claim the same spot.

Solving collisions with chaining

The most common way to fix this is "chaining." Instead of storing the value directly in the bucket, I'll store another array (a "list" or "bucket") at that index. If two users land in the same bucket, they both just live in that smaller list.

Let's rewrite the logic. Now, each bucket starts as an empty array. When I store something, I'll append a key-value pair to that bucket. When I retrieve something, I'll jump to the bucket and then do a very tiny linear search through only the items in that specific bucket.

$buckets = array_fill(0, 10, []);

function store($buckets, $key, $value) {
    $index = abs(crc32($key)) % count($buckets);
    
    // We still need to check if the key exists to update it instead of duplicating
    foreach ($buckets[$index] as &$pair) {
        if ($pair['key'] === $key) {
            $pair['value'] = $value;
            return $buckets;
        }
    }
    
    $buckets[$index][] = ['key' => $key, 'value' => $value];
    return $buckets;
}

function retrieve($buckets, $key) {
    $index = abs(crc32($key)) % count($buckets);
    
    foreach ($buckets[$index] as $pair) {
        if ($pair['key'] === $key) {
            return $pair['value'];
        }
    }
    
    return null; // Not found
}

$buckets = store($buckets, 'alice', 'admin');
$buckets = store($buckets, 'bob', 'editor');
$buckets = store($buckets, 'charlie', 'guest');

echo retrieve($buckets, 'bob'); // 'editor'

Now we've actually implemented the core concept of a hash table. We've gone from a slow global search to a fast hash-jump, followed by a very short local search. This is exactly what PHP is doing under the hood when you use $array['key'], just with a much more sophisticated hashing algorithm and a dynamic resizing mechanism so the buckets don't get too crowded.

📋 Practical Task

Exercise: Implementing a Collision-Resistant User Session Store

You are tasked with building a manual session store to better understand hash table collisions. Create a script that does the following:

• Initialize a $sessionBuckets array with exactly 5 empty slots.
• Create a function called hashSessionId($id, $size) that uses crc32 and the modulo operator to return an index.
• Create a function called setSession($buckets, $sessionId, $data). This function must handle collisions using the "chaining" method (storing an array of pairs within the bucket).
• Create a function called getSession($buckets, $sessionId) that retrieves the data for a specific session ID.
• Test your implementation by inserting 10 different session IDs. Given that you only have 5 buckets, collisions will happen. Verify that you can still retrieve the correct data for all 10 sessions without any data being overwritten.