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;
    }
}

這些方法可以根據具體應用場景和需求選擇。鏈地址法在大多數情況下性能較好，但可能導致內存占用較高；開放尋址法在內存利用方面更優，但在最壞情況下性能較差。