(Kapan) adalah pencarian tabel hash O (1)?

Sering dikatakan bahwa pencarian tabel hash beroperasi dalam waktu konstan: Anda menghitung nilai hash, yang memberi Anda indeks untuk pencarian array. Namun ini mengabaikan tabrakan; dalam kasus terburuk, setiap item kebetulan mendarat di ember yang sama dan waktu pencarian menjadi linear ( ).$\Theta(n)$

Apakah ada kondisi pada data yang dapat membuat pencarian tabel hash benar-benar ? Apakah itu hanya rata-rata, atau dapatkah tabel hash memiliki O (1) pencarian kasus terburuk?O ( 1 $O(1)$$O(1)$

Catatan: Saya datang dari sudut pandang programmer di sini; ketika saya menyimpan data dalam tabel hash, itu hampir selalu string atau beberapa struktur data komposit, dan data berubah selama masa pakai tabel hash. Jadi, sementara saya menghargai jawaban tentang hash yang sempurna, mereka lucu tetapi anekdot dan tidak praktis dari sudut pandang saya.

PS Follow-up: Untuk jenis data apa operasi tabel hash O (1)?

Ada dua pengaturan di mana Anda bisa mendapatkan terburuk.$O(1)$

1. Jika pengaturan Anda statis, maka hashing FKS akan memberi Anda jaminan terburuk . Tetapi seperti yang Anda tunjukkan, pengaturan Anda tidak statis.$O(1)$

2. Jika Anda menggunakan hashing Cuckoo, maka kueri dan penghapusan adalah kasus terburuk, tetapi penyisipan hanya O ( 1 ) yang diharapkan. Cuckoo hashing bekerja cukup baik jika Anda memiliki batas atas jumlah sisipan, dan atur ukuran tabel menjadi sekitar 25% lebih besar.$O(1)$$O(1)$

Ada informasi lebih lanjut di sini .

Jawaban ini merangkum bagian-bagian dari TAoCP Vol 3, Bab 6.4.

Asumsikan kita memiliki seperangkat nilai , n yang ingin kita simpan dalam array A ukuran m . Kami menggunakan fungsi hash h : V → [ 0 .. M ) ; biasanya, M ≪ | V | . Kami memanggil α = $V$$n$$A$$m$$h : V \to [0..M)$$M \ll |V|$ denganload factordariA. Di sini, kita akan mengasumsikan naturalm=M; dalam skenario praktis, kita memilikim«M, meskipun, dan harus memetakan kemdiri kita sendiri.$\alpha = \frac{n}{m}$$A$$m=M$$m \ll M$$m$

Pengamatan pertama adalah bahwa bahkan jika memiliki karakteristik seragam-probabilitas dua nilai memiliki nilai hash yang sama tinggi; ini pada dasarnya adalah contoh dari paradoks ulang tahun yang terkenal . Oleh karena itu, kita biasanya harus berurusan dengan konflik dan dapat meninggalkan harapan O ( 1 ) waktu akses kasus terburuk.$h$$\mathcal{O}(1)$

Bagaimana dengan kasus rata-rata? Mari kita asumsikan bahwa setiap kunci dari muncul dengan probabilitas yang sama. Jumlah rata-rata entri yang diperiksa C S n (pencarian berhasil) resp. C U n (pencarian yang gagal) tergantung pada metode resolusi konflik yang digunakan.$[0..M)$$C_n^S$$C_n^U$

Rantai

Setiap entri array berisi (pointer ke kepala) daftar tertaut. Ini adalah ide yang bagus karena panjang daftar yang diharapkan kecil ( ) meskipun probabilitas untuk tabrakan tinggi. Pada akhirnya, kita mendapatkan C S n ≈1+$\frac{n}{m}$ Ini dapat ditingkatkan sedikit dengan menyimpan daftar (sebagian atau seluruhnya) di dalam tabel.

$$C_n^S \approx 1 + \frac{\alpha}{2} \quad \text{ and } \quad C_n^U \approx 1 + \frac{\alpha^2}{2} .$$

Probing Linier

Ketika memasukkan (resp. Mencari nilai) , periksa posisi h ( v ) , h ( v ) - 1 , … , 0 , m - 1 , … , h ( v ) + 1 dalam urutan ini hingga posisi kosong (resp . v ) ditemukan. Keuntungannya adalah kami bekerja secara lokal dan tanpa struktur data sekunder; Namun, jumlah akses rata-rata berbeda untuk α → 1 : C S n ≈ $v$

$$h(v), h(v)-1,\dots,0,m-1,\dots,h(v)+1$$ $v$$\alpha \to 1$ Namun untukα<0,75, kinerjanya sebanding dengan chaining². $$C_n^S \approx \frac{1}{2}\left(1 +\frac{1}{1-\alpha}\right) \quad \text{ and } \quad C_n^U \approx \frac{1}{2}\left(1 +\left(\frac{1}{1-\alpha}\right)^2\right).$$ $\alpha < 0.75$

Hashing ganda

Mirip dengan linear probing tetapi ukuran langkah pencarian dikendalikan oleh fungsi hash kedua yang coprime untuk . Tidak ada derivasi formal yang diberikan, tetapi pengamatan empiris menunjukkan C S n ≈ $M$ Metode ini telah diadaptasi oleh Brent; variannya diamortisasi meningkatkan biaya penyisipan dengan pencarian lebih murah.

$$C_n^S \approx \frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\quad \text{ and } \quad C_n^U \approx \frac{1}{1-\alpha} .$$

Perhatikan bahwa menghapus elemen dari dan memperluas tabel memiliki berbagai tingkat kesulitan untuk metode masing-masing.

Intinya, Anda harus memilih implementasi yang beradaptasi dengan baik dengan kasus penggunaan khas Anda. Waktu akses yang diharapkan dalam dimungkinkan jika tidak selalu dijamin. Tergantung pada metode yang digunakan, menjaga α rendah sangat penting; Anda harus menukar waktu akses (yang diharapkan) dengan overhead ruang. Pilihan yang baik untuk h juga sangat penting.$\mathcal{O}(1)$$\alpha$$h$

---

$h$
Hashtable

$S$$\{0, 1, 2, ..., n\}$$O(1)$$O(1)$$l$$S$$l$$x$$x \in S$$O(|l|)$$S$$O(|S|)$$O(|l| + |S|)$$O(|l||S|)$$O(\log(|l|)|S|)$$O(|l|)$$l$

$O(|l|)$

$l$$U \subset \mathbb{N}$$S \subseteq U$$x \in S$$l$$l$$h: U \rightarrow \{true, false\}$$h$$h(x) = false$$x \in U$$y$$l$$h(y) = true$$O(|l|)$$O(|U|)$

$l$$O(|U|)$$O(|1|)$$O(|U|)$

$U$$h$

$\cal{O}(1)$

$\cal{O}(1)$$\cal{O}(1)$$\cal{O}(1)$$\cal{O}(1)$