Untuk jenis data apa operasi tabel hash O (1)?

18

Dari jawaban untuk (Kapan) adalah pencarian tabel hash O (1)? , Saya mengumpulkan bahwa tabel hash memiliki perilaku kasus terburuk, setidaknya diamortisasi, ketika data memenuhi kondisi statistik tertentu, dan ada teknik untuk membantu membuat kondisi ini luas.O(1)

Namun, dari perspektif programmer, saya tidak tahu sebelumnya apa data saya akan: sering berasal dari beberapa sumber eksternal. Dan saya jarang memiliki semua data sekaligus: sering kali penyisipan dan penghapusan terjadi pada tingkat yang tidak jauh di bawah tingkat pencarian, jadi preprocessing data untuk menyempurnakan fungsi hash keluar.

Jadi, mengambil langkah: diberikan pengetahuan tentang sumber data, bagaimana saya bisa menentukan apakah tabel hash memiliki peluang untuk memiliki operasi , dan mungkin teknik mana yang digunakan pada fungsi hash saya?O(1)

Gilles 'SANGAT berhenti menjadi jahat'
sumber
Oh, dan tabel hash versus pohon biner terkait, tapi di sini saya fokus pada tabel hash dan ketika mereka (atau tidak) yang terbaik.
Gilles 'SANGAT berhenti menjadi jahat'
Kasus terbaik untuk setiap fungsi-hash adalah ketika data didistribusikan secara seragam.
0x0
@ Sunil: Tidak benar. Anda dapat memiliki fungsi hash yang disesuaikan.
Raphael
Saya pikir pertanyaan ini terlalu luas. Secara khusus, dapatkah Anda mengkonkretkan seperti apa pengetahuan tentang sumber data?
Raphael
@Raphael Misalnya, jika kuncinya adalah string: nama orang, nama file dalam direktori, tag XML, hash file, ...
Gilles 'SO- stop being evil'

Jawaban:

4

Ada beberapa teknik yang menjamin bahwa pencarian akan selalu membutuhkan operasi O (1), bahkan dalam kasus terburuk.

Bagaimana saya bisa menentukan apakah tabel hash memiliki peluang untuk memiliki operasi O (1), dan mungkin teknik mana yang digunakan pada fungsi hash saya?

Kasus terburuk terjadi ketika beberapa penyerang jahat (Mallory) sengaja memberi Anda data yang dipilih Mallory khusus untuk membuat sistem berjalan lambat.

Setelah Anda memilih beberapa fungsi hash tertentu, mungkin terlalu optimis untuk menganggap Mallory tidak akan pernah mengetahui fungsi hash mana yang Anda pilih. Setelah Mallory menemukan fungsi hash yang Anda pilih, jika Anda mengizinkan Mallory memberi Anda banyak data untuk dimasukkan ke tabel hash Anda menggunakan fungsi hash, maka Anda akan hancur: Mallory secara internal dapat dengan cepat menghasilkan miliaran item data, hash dengan Anda fungsi hash untuk menemukan item data mana yang cenderung bertabrakan, dan kemudian memberi Anda jutaan item data satu-dalam-seribu yang cenderung bertabrakan, yang mengarah ke pencarian yang berjalan jauh lebih lambat daripada O (1).

Semua teknik yang menjamin "O (1) pencarian bahkan dalam kasus terburuk" hindari masalah ini dengan melakukan sedikit kerja ekstra pada setiap penyisipan untuk menjamin bahwa, di masa depan, setiap pencarian yang mungkin dapat berhasil dalam O (1) waktu . Secara khusus, kami mengasumsikan (kasus terburuk) bahwa Mallory cepat atau lambat akan menemukan fungsi hash mana yang kami gunakan; tetapi dia hanya mendapat kesempatan untuk memasukkan beberapa item data sebelum kita memilih fungsi hash yang berbeda - tabulasi hashing atau hashing universal lainnya - yang kita pilih secara khusus sehingga semua data yang kita miliki sejauh ini dapat dilihat dalam 2 atau 3 probe - yaitu, O (1). Karena kami memilih fungsi ini secara acak, kami dapat yakin bahwa Mallory tidak akan tahu fungsi apa yang kami pilih untuk sementara waktu. Bahkan jika Mallorysegera memberi kita data bahwa, bahkan dengan fungsi hash baru ini, bertabrakan dengan data sebelumnya, kita kemudian dapat memilih fungsi hash baru yang baru sehingga, setelah mengulangi, semua data sebelumnya yang dia dan orang lain berikan kepada kita sekarang dapat dilihat di 2 atau 3 probe dalam kasus terburuk - yaitu, O (1) pencarian dalam kasus terburuk.

Ini cukup mudah untuk secara acak memilih fungsi hash baru dan mengulangi seluruh tabel cukup sering untuk menjamin bahwa setiap pencarian selalu O (1). Meskipun ini menjamin bahwa setiap pencarian selalu O (1), teknik-teknik ini, saat memasukkan item N ke dalam tabel hash yang sudah berisi item N-1, kadang-kadang dapat membutuhkan waktu O (N) untuk memasukkan itu. Namun, adalah mungkin untuk merancang sistem sedemikian rupa sehingga, bahkan ketika Mallory dengan sengaja memberi Anda data baru, dengan menggunakan fungsi hash baru, bertabrakan dengan data sebelumnya, sistem dapat menerima banyak item dari Mallory dan lainnya sebelum perlu melakukan O penuh (N) dibangun kembali. Teknik tabel hash yang memilih fungsi baru dan pengulangan untuk menjamin O (1) pencarian, bahkan dalam kasus terburuk, termasuk:

  • jaminan hash cuckoo bahwa setiap pencarian kunci berhasil dengan paling banyak 2 perhitungan hash dan 2 pencarian tabel.
  • hashing hopscotch menjamin bahwa setiap pencarian kunci berhasil setelah memeriksa sejumlah kecil H (mungkin H = 32) entri berturut-turut dalam tabel.
  • dynamic perfect hashing - makalah 1994 oleh Dietzfelbinger adalah yang pertama saya baca yang menunjukkan bahwa, meskipun mengulangi "sering" untuk memastikan bahwa setiap pencarian kunci selalu berhasil dengan 2 perhitungan hash dan 2 pencarian, itu mungkin untuk melakukan pengulangan penuh sangat jarang sehingga meskipun setiap pengulangan penuh menggunakan waktu O (n), biaya rata-rata penyisipan dan penghapusan yang diharapkan adalah O (1) diamortisasi.

Struktur Data / Tabel Hash

David Cary
sumber
5

HAI(1)

HAI(1)HAI(n2W)

HAI(catatann/catatancatatann)HAI(1)

DI
sumber
5

hSebuah,b(x)=Sebuahx+bmodhal

Di masa lalu, menurut kertas Usenix oleh Crosby dan Wallach , bahasa pemrograman umum tidak melakukan hal seperti ini, meninggalkan banyak aplikasi web (dan server lain) terbuka untuk serangan DoS berdasarkan pada tabrakan manufaktur. (Makalah ini dari tahun 2003, tetapi menunjukkan bahwa Dan Bernstein telah menemukan ide yang sama sedikit lebih awal.)

Pencarian google cepat memberikan klaim bahwa keadaan dalam hal implementasi telah meningkat dan tidak membaik .

Selain itu adalah bahwa di dunia bandwidth tinggi, serangan waktu membuatnya tidak terlalu sulit untuk menemukan tabrakan online (sebagai lawan offline seperti yang disarankan tautan Crosby-Wallach). Sepertinya saya ingat bahwa Daniel Golovin memiliki hasil beberapa tahun yang lalu pada struktur data yang tidak rentan terhadap serangan waktu, tetapi saya tidak tahu apakah itu digunakan secara luas.

Louis
sumber
0

Analisis kasus rata-rata untuk tabel hash dibuat dengan asumsi keseragaman input yang biasa, yang pernah membuat karena pisau cukur occam.

Jika Anda memiliki pengetahuan tambahan tentang domain dan distribusi kunci, Anda dapat mengambil analisis kasus rata-rata yang sama dan mengganti distribusi seragam dengan distribusi Anda dan menghitung ulang harapan, setidaknya secara teori.

Tentu saja kesulitannya berasal dari fakta bahwa analisis kasus rerata yang tidak seragam 'sulit dilakukan. Dan "pengetahuan" Anda mungkin tidak dapat dengan mudah diungkapkan sebagai distribusi yang dapat digunakan dengan mudah dalam analisis semacam itu.

Jelas hal yang paling mudah untuk dilakukan adalah simulasi. Terapkan hash-tables dan oberserve bagaimana kinerjanya untuk set input khas Anda.

uli
sumber
8
Saya harus tidak setuju dengan kalimat pertama. Asumsi standar adalah bahwa fungsi hash adalah acak, bukan input data. Dengan asumsi data terdistribusi secara seragam mendorong analisis ke dalam dunia fantasi — data dunia nyata tidak pernah seragam! Tetapi ada teknik buku teks untuk membuat fungsi hash cukup seragam. Lihat hashing universal dan hashing tabulasi khusus .
JeffE
@ Jeff JE Lihatlah analisis kasus rata-rata dalam jawaban Raphael ia menyatakan asumsi keseragaman ini. Anda tidak dapat melakukan analisis kasus rata-rata tanpa distribusi. Anda harus memilih satu dan jika tidak diberikan, pisau cukur Occam menyarankan yang seragam.
uli
6
Tentu saja Anda memiliki distribusi; itu distribusi yang Anda gunakan untuk memilih fungsi hash. Memilih distribusi untuk data input seperti mencari kunci Anda yang hilang di bawah tiang lampu; tentu, cahayanya lebih baik, tapi itu mungkin bukan tempat Anda menjatuhkannya.
JeffE
@ Jeffe Begitulah cara analisis kasus rata-rata dilakukan, pilih distribusi dan mulai menghitung. Seperti biasa pilihan distribusi masih bisa diperdebatkan. Anda dapat melakukan analisis kasus rata-rata yang tidak seragam.
uli
4
Ya, saya tahu caranya. (Periksa profil saya.) Jika Anda ingin analisis Anda bersifat prediktif (yang merupakan keseluruhan poin analisis), Anda harus mengacak fungsi hash. Maka Anda tahu distribusi yang tepat, karena Anda memilihnya.
JeffE
-1

nn!

isturdy
sumber