溫馨提示×

php hashtable怎樣處理哈希沖突

PHP
小樊
81
2024-10-17 06:47:41
欄目: 編程語言

在PHP中，哈希表是通過關(guān)聯(lián)數(shù)組實(shí)現(xiàn)的。當(dāng)兩個(gè)或多個(gè)鍵產(chǎn)生相同的哈希值時(shí)，就會(huì)發(fā)生沖突。處理哈希沖突的方法有以下幾種：

  1. 鏈地址法（Separate Chaining）： 鏈地址法是在每個(gè)哈希表的槽位上鏈接一個(gè)鏈表。當(dāng)發(fā)生沖突時(shí)，將具有相同哈希值的元素添加到相應(yīng)槽位的鏈表中。查找、插入和刪除操作的時(shí)間復(fù)雜度為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;
    }
}
  1. 開放尋址法（Open Addressing）： 開放尋址法是在發(fā)生沖突時(shí)尋找下一個(gè)可用的槽位。常見的開放尋址法有線性探測、二次探測和雙散列。查找、插入和刪除操作的平均時(shí)間復(fù)雜度為O(1)，但在最壞情況下可能達(dá)到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;
    }
}

這些方法可以根據(jù)具體應(yīng)用場景和需求選擇。鏈地址法在大多數(shù)情況下性能較好，但可能導(dǎo)致內(nèi)存占用較高；開放尋址法在內(nèi)存利用方面更優(yōu)，但在最壞情況下性能較差。

0 踩