Bagaimana menghindari cascading resize ketika mengubah ukuran tabel hash?

Dengan metode resolusi tabrakan konvensional seperti chaining terpisah dan linear / kuadrat probing, urutan probe untuk kunci dapat panjang sewenang-wenang - hanya disimpan pendek dengan probabilitas tinggi dengan menjaga faktor beban tabel rendah. Tabrakan selama pengulangan bukan masalah karena tidak mempengaruhi faktor beban.

Namun, dengan hashing kukuk (dan metode lain yang menawarkan waktu pencarian O (1) kasus terburuk?), Pengubahan ukuran harus terjadi ketika urutan probe untuk kunci terlalu lama. Tetapi ketika kunci dikocok sekitar selama pengulangan, itu mungkin bahwa mereka membuat urutan penyelidikan terlalu lama untuk satu kunci, memerlukan ukuran lain - mungkin beberapa, jika ini terjadi beberapa kali berturut-turut. Probabilitasnya kecil, terutama dengan fungsi hash yang baik, tetapi saya telah melihatnya terjadi.

Apakah ada cara - singkat secara eksplisit menghasilkan fungsi hash yang sempurna selama pengulangan - untuk memastikan bahwa ukuran tidak dapat mengalir dengan cara ini? Mungkin khusus untuk skema resolusi tabrakan yang diberikan? Literatur yang saya temui sejauh ini tampaknya sepenuhnya menutupi masalah ini. Ingatlah bahwa saya juga tertarik untuk mengecilkan tabel hash, tidak hanya menumbuhkannya.

Anda bertanya bagaimana cara menghindari cascading rehash tetapi Anda sudah memberikan jawaban di posting Anda. Anda menjaga probabilitas bahwa peristiwa buruk terjadi kecil.

Karena Anda menyebutkan hashing kukuk. Probabilitas bahwa Anda mendapatkan urutan penyelidikan yang panjang adalah$O(1/n^2)$. Jadi jika Anda mengulangi, Anda memasukkan elemen dari awal. Probabilitas bahwa pengulangan tidak berhasil maka , sehingga dengan probabilitas yang sangat tinggi Anda berhasil. Dengan harapan Anda hanya perlu jumlah percobaan yang konstan. Jika Anda melihat bahwa Anda memiliki masalah dengan pengulangan, maka Anda harus meningkatkan ukuran tabel Anda dan memodifikasi load factor Anda. Atau Anda dapat memilih keluarga fungsi hash yang lebih baik.$n$$O(1/n)$

Saya yakin saya punya satu solusi, terinspirasi oleh hashing linier :

Jika fungsi hash dipertahankan konstan (yaitu, tidak diubah saat mengubah ukuran) dan tabel selalu tumbuh dengan menggandakan slot, maka setelah tabel tumbuh, itu menyatakan bahwa

$H \mod 2L = \begin{cases} H \mod L + L & \text{or} \\ H \mod L \end{cases}$

di mana adalah hash kunci dan adalah jumlah slot yang lama. Ini berarti bahwa kunci tetap berada di tempatnya atau pindah ke slot unik di area yang baru dialokasikan, yang dijamin kosong.$H$$L$

Untuk menerapkan ini pada hashing cuckoo (d-ary), cukup mengubah ukuran masing-masing subtabel secara terpisah dan tidak memindahkan kunci di antara subtabel.

Untuk mengecilkan tabel, Anda perlu mengonfirmasi bahwa salah satu dari adalah kosong untuk setiap kunci dalam tabel, dan jika demikian, pindahkan semuanya ke slot . Tentu saja, ini ... Saya tidak yakin apakah ada cara yang lebih baik untuk melakukan ini daripada menjalankan pemeriksaan untuk setiap penghapusan setelah faktor beban turun di bawah setengah.$\lbrace H \mod \frac{L}{2} + \frac{L}{2}, ~ H \mod \frac{L}{2} \rbrace$$H \mod \frac{L}{2}$$O(n)$