PHP data structure: Implementation principle of hash table, explore the secret of fast data search

A hash table is an efficient data structure that enables fast lookups by mapping data into fixed-size arrays ("buckets"), each bucket containing data with the same key. Hash tables in PHP use a hash function to convert data of any size into a fixed-length integer, which is used to calculate the buckets of the data in the hash table.

PHP data structure: implementation principle of hash table, exploring the secret of fast data search

Introduction

Hash table (hash table) is an efficient data structure used to find data quickly. It achieves fast lookups by mapping data into a fixed-size array, a "bucket." Each bucket contains data with the same key.

Implementation principle

The implementation principle of hash table in PHP is based on Hash function. A hash function converts data of any size into a fixed-length integer. This integer is used to calculate the bucket into which the data is inserted in the hash table.

Code implementation: Custom hash table

The following is a sample code to implement a hash table in PHP:

class HashTable
{
    private $buckets = [];
    private $size = 0;

    public function __construct($size)
    {
        $this->size = $size;
    }

    public function hash(string $key): int
    {
        return crc32($key) % $this->size;
    }

    public function set(string $key, $value): void
    {
        $index = $this->hash($key);
        $this->buckets[$index][$key] = $value;
    }

    public function get(string $key): mixed
    {
        $index = $this->hash($key);
        if (isset($this->buckets[$index][$key])) {
            return $this->buckets[$index][$key];
        } else {
            return null;
        }
    }
}

Actual case: Press Group employees by age

Suppose we have an array containing the ages of employees and we want to group employees by age. We can use a hash table to quickly find employees with the same age.

$ages = [25, 30, 28, 35, 32, 25, 30];
$hashTable = new HashTable(count($ages));

foreach ($ages as $age) {
    $hashTable->set($age, []);
}

foreach ($ages as $age) {
    $hashTable->get($age)[] = $age;
}

var_dump($hashTable->buckets);

Output result:

array(
    25 => array(25, 25),
    30 => array(30, 30),
    28 => array(28),
    35 => array(35),
    32 => array(32)
)

The above is the detailed content of PHP data structure: Implementation principle of hash table, explore the secret of fast data search. For more information, please follow other related articles on the PHP Chinese website!