php hashtable怎样处理哈希冲突

在PHP中，哈希表是通过关联数组实现的。当两个或多个键产生相同的哈希值时，就会发生冲突。处理哈希冲突的方法有以下几种：

1. 链地址法（Separate Chaining）： 链地址法是在每个哈希表的槽位上链接一个链表。当发生冲突时，将具有相同哈希值的元素添加到相应槽位的链表中。查找、插入和删除操作的时间复杂度为O(1)。

class HashTable {
    private $size;
    private $table;

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

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

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

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

2. 开放寻址法（Open Addressing）： 开放寻址法是在发生冲突时寻找下一个可用的槽位。常见的开放寻址法有线性探测、二次探测和双散列。查找、插入和删除操作的平均时间复杂度为O(1)，但在最坏情况下可能达到O(n)。

class HashTable {
    private $size;
    private $table;

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

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

    public function set($key, $value) {
        $index = $this->hash($key);
        while ($this->table[$index] !== null) {
            if ($this->table[$index][0] === $key) {
                $this->table[$index] = [$key, $value];
                return;
            }
            $index = ($index + 1) % $this->size;
        }
        $this->table[$index] = [$key, $value];
    }

    public function get($key) {
        $index = $this->hash($key);
        while ($this->table[$index] !== null) {
            if ($this->table[$index][0] === $key) {
                return $this->table[$index][1];
            }
            $index = ($index + 1) % $this->size;
        }
        return null;
    }
}

这些方法可以根据具体应用场景和需求选择。链地址法在大多数情况下性能较好，但可能导致内存占用较高；开放寻址法在内存利用方面更优，但在最坏情况下性能较差。