Mengapa pencarian hashtable (tanpa tabrakan) benar-benar O (1)?

Penafian: Saya tahu ada pertanyaan yang terdengar serupa di sini dan di Stackoverflow. Tapi mereka semua tentang tabrakan, yang bukan itu yang saya minta.

Pertanyaan saya adalah: mengapa pencarian tanpa tabrakan O(1)di tempat pertama?

Anggap saya memiliki hashtable ini:

Hash  Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6

Sekarang saya sedang mencari kunci di kmana fungsi hash h(k)memberi h(k) = mkwer. Tetapi bagaimana pencarian "tahu" bahwa hash mkwerada di posisi 5? Mengapa tidak harus menelusuri semua kunci O(n)untuk menemukannya? Hash tidak boleh berupa alamat perangkat keras yang sebenarnya karena saya akan kehilangan kemampuan untuk memindahkan data. Dan sejauh yang saya tahu, hashtable tidak diurutkan pada hash (bahkan jika itu, pencarian juga akan mengambil O(log n))?

Bagaimana mengetahui hash membantu menemukan tempat yang benar dalam tabel?

Fungsi hash tidak mengembalikan beberapa string seperti mkwer. Ini langsung mengembalikan posisi item dalam array. Jika, misalnya, tabel hash Anda memiliki sepuluh entri, fungsi hash akan mengembalikan integer dalam rentang 0-9.

Fungsi hash menghitung posisi array dari string yang diberikan . Jika hash ini sempurna, artinya pasti tidak ada tabrakan, array yang paling mungkin setidaknya dua kali lebih besar dari jumlah elemen.

Misalnya saya akan memberikan hash yang sangat buruk untuk surat, hanya untuk menggambarkan mekanisme:
0) 1) untuk setiap karakter dalam string mengambil nilai ascii, kurangi 'a' jika huruf kecil, kurangi 'A' jika huruf besar, tambahkan nilai ke x. 2) angka yang dihasilkan misalnya 15 adalah indeks array. x = x m o d $x = 0;$
$x = x mod 52$

Hash yang sangat sederhana ini (terbatas dan rawan benturan) berbeda dari hash lainnya dalam mekanisme hashing, tidak mempertimbangkan input yang diberikan. Dalam skema yang lebih maju hash adalah angka yang lebih besar, disesuaikan dengan jumlah elemen. Hash sempurna dihasilkan untuk semua input untuk menjamin tidak ada tabrakan.

Ini adalah karena menghitung hash dari string tergantung pada seberapa canggih fungsi dihitung, tetapi tidak tergantung pada jumlah elemen.$O(1)$

Dalam kasus hash sempurna, ketika elemen ditambahkan dihitung ulang, kasus sederhana dengan tabrakan ketika beban array besar ukuran array meningkat, fungsi mengambil modulo output yang lebih besar, dan elemen digeser ke tempat-tempat baru.$h(k)$

Array adalah fragmen memori berkelanjutan, untuk mendapatkan elemen Anda mengambil alamat elemen pertama (array start) dan kemudian menambahkan ke alamat ini sehingga Anda memiliki sel memori eksplisit.n ∗ ( s i z e o f e l e m e n t $n-th$$n * (size of element)$

Untuk memperluas jawaban David Richerby, istilah " fungsi hash " sedikit kelebihan. Seringkali, ketika kita berbicara tentang fungsi hash kita memikirkan MD5, SHA-1, atau sesuatu seperti .hashCode()metode Java , yang mengubah beberapa input menjadi satu nomor. Namun domain nomor ini (yaitu nilai maksimum) sangat tidak mungkin memiliki ukuran yang sama dengan hashtable yang Anda coba simpan data. (MD5 adalah 16 byte, SHA-1 adalah 20 byte, dan .hashCode()merupakan int- 4 byte).

Jadi pertanyaan Anda adalah tentang langkah selanjutnya - setelah kami memiliki fungsi hash yang dapat memetakan input sewenang-wenang ke angka, bagaimana kita menempatkan mereka ke dalam struktur data dengan ukuran tertentu? Dengan fungsi lain, juga disebut "fungsi hash"!

Contoh sepele dari fungsi tersebut adalah modulo ; Anda dapat dengan mudah memetakan sejumlah ukuran acak ke indeks tertentu dalam array dengan modulo. Ini diperkenalkan dalam CLRS sebagai "metode pembagian":

Dalam metode pembagian untuk membuat fungsi hash, kami memetakan kunci ke salah satu slot dengan mengambil sisa dibagi dengan . Artinya, fungsi hash adalahm k $k$$m$$k$$m$

$h(k) = k$ mod .$m$

...

Saat menggunakan metode pembagian, kita biasanya menghindari nilai tertentu . Misalnya, tidak harus menjadi kekuatan 2, karena jika maka hanyalah terendah-order bit .m m = 2 p h ( k ) p $m$$m$$m = 2^p$$h(k)$$p$$k$

~ Pengantar Algoritma, §11.3.1 - CLRS

Jadi modulo bukanlah fungsi hash yang hebat, karena modulo membatasi ukuran apa yang dapat kita gunakan dengan aman untuk struktur data dasar kita. Bagian berikutnya memperkenalkan "metode multiplikasi" yang sedikit lebih kompleks, yang juga menggunakan modulo tetapi menguntungkan karena "nilai tidak kritis". Namun itu bekerja paling baik dengan pengetahuan sebelumnya tentang "karakteristik data yang di-hash" - sesuatu yang sering kita tidak tahu.$m$

Java HashMapmenggunakan versi modifikasi dari metode pembagian yang melakukan langkah pra-pemrosesan untuk menjelaskan .hashCode()implementasi yang lemah sehingga dapat menggunakan array berukuran dua kekuatan. Anda dapat melihat dengan tepat apa yang terjadi dalam .getEntry()metode ini (komentar adalah milik saya):

 // hash() transforms key.hashCode() to protect against bad hash functions
 int hash = (key == null) ? 0 : hash(key.hashCode());
 // indexOf() converts the resulting hash to a value between 0 and table.length-1
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
     ...

_{Java 8 membawa serta penulisan ulang HashMapyang bahkan lebih cepat, tetapi sedikit lebih sulit untuk dibaca. Namun, ia menggunakan prinsip umum yang sama untuk pencarian indeks.}