当前位置：首页 > PHP

php 实现hashtable

2026-01-29 22:08:55PHP

实现哈希表的基本思路

哈希表（HashTable）是一种通过哈希函数将键映射到存储位置的数据结构，能够实现高效的插入、查找和删除操作。PHP中可以通过数组或结合对象模拟实现哈希表的功能。

使用PHP数组实现哈希表

PHP的关联数组本质上就是哈希表的实现，因此可以直接利用数组操作：

$hashTable = [];

// 插入键值对
$hashTable['key1'] = 'value1';
$hashTable['key2'] = 'value2';

// 查找
if (isset($hashTable['key1'])) {
    echo $hashTable['key1']; // 输出: value1
}

// 删除
unset($hashTable['key2']);

自定义哈希表类

如果需要更底层控制或学习目的，可以封装一个哈希表类：

class HashTable {
    private $buckets = [];
    private $size = 100; // 桶大小

    // 简单哈希函数
    private function hashFunction($key) {
        return crc32($key) % $this->size;
    }

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

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

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

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

处理哈希冲突的方法

当不同键映射到相同索引时会发生哈希冲突，常见解决方法：

链地址法 使用数组存储链表（如上例中的二维数组），冲突时在同一个桶内追加。

开放寻址法 当发生冲突时，按一定规则寻找下一个可用位置：

private function linearProbing($key, $i) {
    return ($this->hashFunction($key) + $i) % $this->size;
}

性能优化建议

初始桶大小应设置为质数，减少哈希聚集。当元素数量超过阈值（如70%容量）时执行扩容操作，重新哈希所有元素。

php 实现hashtable

private function resize() {
    $oldBuckets = $this->buckets;
    $this->size *= 2;
    $this->buckets = [];

    foreach ($oldBuckets as $bucket) {
        foreach ($bucket as $key => $value) {
            $this->set($key, $value);
        }
    }
}