Apa keuntungan dari hashing cuckoo dibandingkan hashing dinamis sempurna?

12

Tabel hash dinamis sempurna dan tabel hash cuckoo adalah dua struktur data yang berbeda yang mendukung pencarian O (1) terburuk dan diharapkan O (1) waktu penyisipan dan penghapusan. Keduanya membutuhkan O (n) ruang tambahan dan akses ke keluarga fungsi hash untuk operasi mereka.

Saya pikir kedua struktur data ini indah dan brilian, tetapi saya tidak yakin saya melihat bagaimana dan kapan salah satu dari ini lebih disukai daripada yang lain.

Apakah ada konteks khusus di mana salah satu struktur data ini memiliki keunggulan yang jelas di atas yang lain? Atau mereka sebagian besar dipertukarkan?

data-structures hash-tables templatetypedef
sumber

Saya tidak yakin apakah salah satu dari teknik ini benar-benar digunakan dalam praktik. Biasanya jenis-jenis struktur data yang menawarkan batas asimptotik terbaik ini terutama menarik minat penelitian, karena mereka biasanya memiliki konstanta besar yang tersembunyi dalam notasi-

O

$O$ . Dalam praktiknya Anda mungkin lebih suka teknik

lebih sederhana dan mudah diterapkan

O (\log n)

$O(\log n)$ dengan konstanta yang sangat kecil daripada

lebih rumit

O (1)

$O(1)$ dengan konstanta yang sangat besar.

Tom van der Zanden

@ TomvanderZanden Itu benar sekali. Saya juga tertarik dengan keunggulan teoretis dari satu pendekatan di atas yang lain - adakah properti teoretis bagus yang ditawarkan masing-masing pendekatan di atas yang lain?

templatetypedef

@ templatetypedef, saya mendorong Anda untuk menambahkan itu ke pertanyaan, lalu. Orang tidak harus membaca komentar untuk memahami pertanyaan Anda - komentar bersifat sementara dan dapat menghilang kapan saja.

DW

Ya, teknik ini sebenarnya digunakan dalam praktik, biasanya di area khusus.

Nama samaran

1

Satu keuntungan dari hashing kukuk adalah mudah dipahami dan diimplementasikan. Juga, imho, itu jauh lebih mudah untuk dianalisis daripada hashing dinamis sempurna.

A.Schulz

3

Hashing sempurna dinamis dalam arti Dietzfelbinger et al. hanya membutuhkan hashing 2-independen . Sementara ada beberapa hasil pada hashing sederhana untuk tabel hash cuckoo, seperti hashing tabulasi bengkok dan "Keluarga Hash Eksplisit dan Efisien Cukup untuk Cuckoo Hashing dengan Stash", hashing dinamis asli lebih kuat dalam beberapa hal.

jbapple
sumber

Lihat komentar klarifikasi dari OP: "Saya juga tertarik pada keunggulan teoretis dari satu pendekatan di atas yang lain - adakah properti teoretis bagus yang ditawarkan masing-masing pendekatan di atas yang lain?"

jbapple

3

Dalam hashing cuckoo, pencarian dapat dilakukan secara paralel, sedangkan dalam skema hashing dinamis sempurna asli Dietzfelbinger et al., Pencarian membutuhkan dua akses memori berantai, di mana akses kedua menggunakan informasi yang diambil dari yang pertama.

jbapple
sumber

1

Relatif mudah untuk meningkatkan efisiensi ruang hashing cuckoo dengan memungkinkan setiap slot menampung lebih dari satu item. Untuk slot ukuran 4, efisiensi ruang adalah sekitar 95%. Dengan kata lain, item dapat dimasukkan hingga 95% dari ruang dalam tabel digunakan untuk menyimpan item, bukan hanya tempat di mana item mungkin pergi.

Di sisi lain, batasan dalam Dietzfelbinger et al. kertas pada hashing dinamis sempurna hanya membuktikan bahwa operasi memasukkan dapat dilanjutkan selama tabel tidak lebih dari 3% penuh.

jbapple
sumber

Anda mungkin ingin menggabungkan kedua jawaban Anda menjadi satu. :-)

templatetypedef

0

Cuckoo hashing menggunakan blok memori pada satu waktu dan perlu membebaskan atau merealokasi memori jarang. Hashing dinamis sempurna dalam arti Dietzfelbinger menggunakan blok memori dan akan menggunakan lebih banyak ruang dalam fragmentasi internal dan eksternal. Ada cara untuk menghindari ini, tetapi mereka menambah kompleksitas pada algoritma. $O(1)$ $O(n)$

jbapple
sumber

Apa keuntungan dari hashing cuckoo dibandingkan hashing dinamis sempurna?

Jawaban: