当前位置：首页 > PHP

php 实现hashtable

2026-02-14 20:01:10PHP

PHP 实现哈希表

哈希表（Hash Table）是一种高效的数据结构，通过键值对（key-value）存储数据。PHP 本身提供了关联数组（associative array），其底层实现就是哈希表。如果需要手动实现哈希表，可以参考以下方法。

使用 PHP 数组模拟哈希表

PHP 的关联数组天然支持哈希表的功能，可以直接使用：

$hashTable = [];
$hashTable['key1'] = 'value1';
$hashTable['key2'] = 'value2';

// 访问值
echo $hashTable['key1']; // 输出: value1

// 检查键是否存在
if (isset($hashTable['key1'])) {
    echo 'Key exists';
}

// 删除键值对
unset($hashTable['key1']);

手动实现哈希表结构

如果需要更底层的实现，可以模拟哈希表的冲突处理（如链地址法）：

class HashTable {
    private $buckets;
    private $size = 10;

    public function __construct() {
        $this->buckets = array_fill(0, $this->size, []);
    }

    private function hash($key) {
        return crc32($key) % $this->size;
    }

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

    public function get($key) {
        $index = $this->hash($key);
        return $this->buckets[$index][$key] ?? null;
    }

    public function delete($key) {
        $index = $this->hash($key);
        unset($this->buckets[$index][$key]);
    }
}

// 使用示例
$ht = new HashTable();
$ht->set('name', 'Alice');
echo $ht->get('name'); // 输出: Alice
$ht->delete('name');

处理哈希冲突

链地址法（Chaining）是一种常见的冲突处理方法，将冲突的键值对存储在同一个桶的链表中：

class HashTableWithChaining {
    private $buckets;
    private $size = 10;

    public function __construct() {
        $this->buckets = array_fill(0, $this->size, []);
    }

    private function hash($key) {
        return crc32($key) % $this->size;
    }

    public function set($key, $value) {
        $index = $this->hash($key);
        foreach ($this->buckets[$index] as &$pair) {
            if ($pair[0] === $key) {
                $pair[1] = $value;
                return;
            }
        }
        $this->buckets[$index][] = [$key, $value];
    }

    public function get($key) {
        $index = $this->hash($key);
        foreach ($this->buckets[$index] as $pair) {
            if ($pair[0] === $key) {
                return $pair[1];
            }
        }
        return null;
    }
}

性能优化

调整哈希表的大小和哈希函数可以减少冲突：

private function hash($key) {
    return abs(crc32($key) % $this->size);
}

动态扩容可以在负载因子过高时提升性能：

public function set($key, $value) {
    if ($this->count / $this->size > 0.7) {
        $this->resize();
    }
    // ... 其他逻辑
}

private function resize() {
    $this->size *= 2;
    $newBuckets = array_fill(0, $this->size, []);
    foreach ($this->buckets as $bucket) {
        foreach ($bucket as $pair) {
            $index = $this->hash($pair[0]);
            $newBuckets[$index][] = $pair;
        }
    }
    $this->buckets = $newBuckets;
}

通过以上方法，可以在 PHP 中实现一个基本的哈希表结构。

php 实现hashtable