php 实现hashtable

哈希表的基本概念

哈希表（Hash Table）是一种通过哈希函数将键映射到特定位置以实现高效查找的数据结构。PHP中可通过数组或SplFixedArray实现哈希表，但需手动处理哈希冲突（如开放寻址法或链地址法）。

基于数组的实现

PHP数组本身是哈希表的实现，但若需手动模拟底层逻辑，可参考以下代码：

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

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

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

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

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

处理哈希冲突

链地址法（如上例）通过在每个桶中存储链表或子数组解决冲突。开放寻址法则需探测下一个可用位置：

public function insertLinearProbing($key, $value) {
    $index = $this->hashFunction($key);
    while (isset($this->buckets[$index]) && $this->buckets[$index]['key'] !== $key) {
        $index = ($index + 1) % $this->size;
    }
    $this->buckets[$index] = ['key' => $key, 'value' => $value];
}

动态扩容

当负载因子超过阈值时，需扩容并重新哈希所有元素：

private function resize() {
    $oldBuckets = $this->buckets;
    $this->size *= 2;
    $this->buckets = array_fill(0, $this->size, null);
    foreach ($oldBuckets as $bucket) {
        if ($bucket !== null) {
            foreach ($bucket as $key => $value) {
                $this->insert($key, $value);
            }
        }
    }
}

性能优化建议

• 选择高效的哈希函数（如crc32或murmurhash）。
• 合理设置初始大小以减少扩容次数。
• 根据场景选择冲突处理策略（链地址法适合高冲突，开放寻址法节省内存）。

实际应用

PHP内置数组已优化了哈希表实现，直接使用关联数组即可：

$hashTable = [];
$hashTable['key1'] = 'value1'; // 插入
$value = $hashTable['key1'] ?? null; // 查找

对于大规模数据，可考虑扩展如SplFixedArray或第三方库（如DS\Map）。