Bincangkan cara PHP menyelesaikan konflik cincang

Dalam pengaturcaraan, jadual cincang ialah struktur data yang sangat berguna. Ia boleh mencari dan memasukkan elemen dalam masa O(1), tetapi fungsi cincang boleh menyebabkan perlanggaran cincang, masalah yang berlaku apabila dua nilai kunci berbeza dipetakan pada indeks yang sama. Dalam artikel ini, kami akan meneroka beberapa cara untuk menyelesaikan isu perlanggaran cincang dan cara melaksanakannya dalam PHP.

1. Kaedah alamat rantaian
   Kaedah alamat rantaian ialah salah satu kaedah paling mudah dan biasa untuk menyelesaikan konflik cincang. Dalam kaedah alamat rantai, setiap slot jadual cincang menghala ke senarai terpaut, di mana setiap nod mengandungi pasangan nilai kunci. Apabila perlanggaran cincang berlaku, elemen baharu ditambahkan pada senarai terpaut pada kedudukan itu. Apabila mencari elemen, anda hanya perlu melintasi senarai terpaut untuk mencari nod.

Dalam PHP, kita boleh menggunakan tatasusunan untuk melaksanakan kaedah alamat rantai. Sebagai contoh, berikut ialah pelaksanaan mudah:

class Hashtable {
    private $table = array();
  
    public function put($key, $value) {
        $hash = $this->hashFunction($key);
        if (!isset($this->table[$hash])) {
            $this->table[$hash] = array();
        }
        foreach ($this->table[$hash] as &$v) {
            if ($v['key'] == $key) {
                $v['value'] = $value;
                return;
            }
        }
        $this->table[$hash][] = array('key' => $key, 'value' => $value);
    }
  
    public function get($key) {
        $hash = $this->hashFunction($key);
        if (isset($this->table[$hash])) {
            foreach ($this->table[$hash] as $v) {
                if ($v['key'] == $key) {
                    return $v['value'];
                }
            }
        }
        return null;
    }
  
    private function hashFunction($key) {
        return crc32($key); // 简单的哈希函数
    }
}

Dalam contoh ini, kami mentakrifkan kelas jadual hash Hashtable. Ia menggunakan fungsi cincang crc32 untuk mengira nilai cincang setiap kunci dan menyimpan pasangan nilai kunci dalam tatasusunan dua dimensi. Apabila elemen perlu ditemui atau dimasukkan, kami mula-mula mengira nilai cincangnya dan kemudian semak sama ada lokasi di mana nilai cincang itu berada sudah wujud. Jika ia tidak wujud, kami mencipta senarai baharu dan menambah elemen pada senarai. Jika kedudukan itu sudah wujud, kami mengulangi senarai, mencari elemen yang sepadan dengan kunci, dan menggantikan nilai. Pelaksanaan ini sangat mudah, tetapi apabila saiz jadual cincang berkembang, panjang senarai terpaut mungkin menjadi sangat panjang, menjejaskan kecekapan carian.

2. Pengalamatan Terbuka
   Pengalamatan terbuka ialah kaedah lain untuk menyelesaikan perlanggaran cincang. Dalam pengalamatan terbuka, apabila perlanggaran cincang berlaku, bukannya menambah elemen baharu pada senarai terpaut, kami terus mencari slot percuma bermula dari kedudukan asal dan memasukkan elemen ke kedudukan pertama yang tersedia. Kelebihan kaedah ini ialah ia tidak memerlukan senarai terpaut dan boleh mengurangkan penggunaan memori.

Dalam PHP, kita boleh menggunakan tatasusunan untuk melaksanakan pengalamatan terbuka. Sebagai contoh, berikut ialah pelaksanaan mudah:

class Hashtable {
    private $table = array();
  
    public function put($key, $value) {
        $i = $this->hashFunction($key);
        $j = $i;
        do {
            if (!isset($this->table[$j])) {
                $this->table[$j] = array('key' => $key, 'value' => $value);
                return;
            }
            if ($this->table[$j]['key'] == $key) {
                $this->table[$j]['value'] = $value;
                return;
            }
            $j = ($j + 1) % count($this->table);
        } while ($j != $i);
    }
  
    public function get($key) {
        $i = $this->hashFunction($key);
        $j = $i;
        do {
            if (isset($this->table[$j])) {
                if ($this->table[$j]['key'] == $key) {
                    return $this->table[$j]['value'];
                }
            } else {
                return null;
            }
            $j = ($j + 1) % count($this->table);
        } while ($j != $i);
        return null;
    }
  
    private function hashFunction($key) {
        return crc32($key); // 简单的哈希函数
    }
}

Dalam contoh ini, kami mentakrifkan kelas jadual hash Hashtable yang lain, yang menggunakan fungsi cincang crc32 untuk mengira nilai cincang setiap kunci, Dan simpan kunci- pasangan nilai dalam tatasusunan satu dimensi. Apabila elemen perlu ditemui atau dimasukkan, kami mula-mula mengira nilai cincangnya dan mula merentasi tatasusunan dari kedudukan itu. Jika kedudukan kosong, kami masukkan elemen baharu pada kedudukan tersebut. Jika kedudukan sudah diduduki, kami akan terus melintasi tatasusunan sehingga kami menemui kedudukan bebas atau melintasi keseluruhan tatasusunan. Satu kelemahan pelaksanaan ini ialah apabila jadual hash membesar dalam saiz, storan perlu diagihkan semula dan elemen sedia ada disalin ke dalam tatasusunan baharu.

3. Cincangan berganda
   Cincangan berganda ialah kaedah yang menggunakan fungsi cincangan untuk menjana satu siri nilai cincangan untuk mencari kedudukan baharu sekiranya berlaku perlanggaran cincang. Dalam pencincangan berganda, kami menggunakan dua fungsi cincang yang berbeza untuk mengira nilai cincang bagi setiap kunci dan ikuti jujukan nilai cincang untuk mencari kedudukan kosong. Menggunakan berbilang fungsi cincang mengurangkan bilangan perlanggaran cincang dan meningkatkan kecekapan carian.

Dalam PHP, kita boleh menggunakan tatasusunan untuk melaksanakan pencincangan berganda. Sebagai contoh, berikut ialah pelaksanaan mudah:

class Hashtable {
    private $table = array();
  
    public function put($key, $value) {
        $i = $this->hashFunction1($key);
        $j = $this->hashFunction2($key);
        $k = $i;
        do {
            if (!isset($this->table[$k])) {
                $this->table[$k] = array('key' => $key, 'value' => $value);
                return;
            }
            if ($this->table[$k]['key'] == $key) {
                $this->table[$k]['value'] = $value;
                return;
            }
            $k = ($k + $j) % count($this->table);
        } while ($k != $i);
    }
  
    public function get($key) {
        $i = $this->hashFunction1($key);
        $j = $this->hashFunction2($key);
        $k = $i;
        do {
            if (isset($this->table[$k])) {
                if ($this->table[$k]['key'] == $key) {
                    return $this->table[$k]['value'];
                }
            } else {
                return null;
            }
            $k = ($k + $j) % count($this->table);
        } while ($k != $i);
        return null;
    }
  
    private function hashFunction1($key) {
        return crc32($key);
    }
  
    private function hashFunction2($key) {
        return ((int)(crc32($key) / count($this->table)) + 1) % count($this->table);
    }
}

Dalam contoh ini, kami mentakrifkan kelas jadual hash lain Hashtable yang menggunakan dua fungsi cincang untuk mengira nilai cincang setiap kunci dan menyimpan pasangan nilai kunci dalam tatasusunan satu dimensi. Apabila elemen perlu ditemui atau dimasukkan, kami mula-mula mengira nilai cincangnya dan menggunakan nilai cincang pertama sebagai kedudukan awal dan nilai cincang kedua untuk mengira saiz langkah bagi setiap carian. Jika kedudukan kosong, kami masukkan elemen baharu pada kedudukan tersebut. Jika kedudukan sudah diduduki, kami akan terus melintasi tatasusunan sehingga kami menemui kedudukan bebas atau melintasi keseluruhan tatasusunan. Satu kelebihan pelaksanaan ini ialah menggunakan dua fungsi cincang yang berbeza boleh mengurangkan bilangan perlanggaran cincang, di mana penggunaan fungsi cincang kedua boleh mengurangkan berlakunya situasi "pengkelompokan".

Kesimpulan
Melaksanakan jadual cincang dalam PHP ialah latihan yang menyeronokkan dan berguna. Semasa pelaksanaan kod, kami melihat tiga kaedah yang biasa digunakan untuk menyelesaikan konflik cincang - kaedah alamat rantai, kaedah pengalamatan terbuka dan kaedah cincang berganda. Setiap kaedah mempunyai kelebihan dan kekurangannya, dan kita harus memilih kaedah yang paling sesuai dengan senario aplikasi semasa.

Akhir sekali, kita perlu ambil perhatian bahawa walaupun jadual cincang sangat cekap dalam operasi carian dan sisipan, prestasinya akan menurun dengan mendadak apabila faktor muatan jadual cincang terlalu tinggi. Oleh itu, kita perlu menyemak faktor beban apabila memasukkan elemen dan mengagihkan semula memori jika perlu untuk memastikan operasi jadual cincang yang cekap.

Atas ialah kandungan terperinci Bincangkan cara PHP menyelesaikan konflik cincang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!