Saya mencari penjelasan tentang cara kerja tabel hash - dalam bahasa Inggris sederhana untuk orang bodoh seperti saya!

Sebagai contoh, saya tahu itu mengambil kunci, menghitung hash (saya mencari penjelasan bagaimana) dan kemudian melakukan beberapa jenis modulo untuk bekerja di mana ia terletak di array di mana nilai disimpan, tetapi di situlah pengetahuan saya berhenti .

Adakah yang bisa menjelaskan prosesnya?

Sunting: Saya tidak bertanya secara khusus tentang bagaimana kode hash dihitung, tetapi gambaran umum umum tentang cara kerja tabel hash.

Berikut penjelasan dalam istilah awam.

Mari kita asumsikan Anda ingin mengisi perpustakaan dengan buku-buku dan tidak hanya mengisinya di sana, tetapi Anda ingin dapat dengan mudah menemukannya lagi saat Anda membutuhkannya.

Jadi, Anda memutuskan bahwa jika orang yang ingin membaca buku mengetahui judul buku dan judul yang tepat untuk boot, maka hanya itu yang diperlukan. Dengan judul, orang tersebut, dengan bantuan pustakawan, harus dapat menemukan buku dengan mudah dan cepat.

Jadi, bagaimana Anda bisa melakukan itu? Yah, jelas Anda dapat menyimpan beberapa jenis tempat Anda meletakkan setiap buku, tetapi kemudian Anda memiliki masalah yang sama seperti mencari di perpustakaan, Anda perlu mencari daftar itu. Memang, daftar akan lebih kecil dan lebih mudah untuk dicari, tetapi Anda tetap tidak ingin mencari secara berurutan dari satu ujung perpustakaan (atau daftar) ke yang lain.

Anda menginginkan sesuatu yang, dengan judul buku, dapat memberi Anda tempat yang tepat sekaligus, sehingga yang harus Anda lakukan hanyalah berjalan ke rak yang tepat, dan mengambil buku itu.

Tapi bagaimana itu bisa dilakukan? Nah, dengan sedikit pemikiran saat Anda mengisi perpustakaan dan banyak pekerjaan ketika Anda mengisi perpustakaan.

Alih-alih mulai mengisi perpustakaan dari satu ujung ke ujung yang lain, Anda membuat metode kecil yang pintar. Anda mengambil judul buku, menjalankannya melalui program komputer kecil, yang mengeluarkan nomor rak dan nomor slot di rak itu. Di sinilah Anda meletakkan buku.

Keindahan dari program ini adalah bahwa di kemudian hari, ketika seseorang kembali untuk membaca buku, Anda memberi makan judul melalui program sekali lagi, dan mendapatkan kembali nomor rak dan nomor slot yang sama dengan yang semula Anda berikan, dan ini adalah di mana buku itu berada.

Program, seperti yang telah disebutkan orang lain, disebut algoritma hash atau perhitungan hash dan biasanya bekerja dengan mengambil data yang dimasukkan ke dalamnya (judul buku dalam kasus ini) dan menghitung angka dari itu.

Untuk kesederhanaan, katakan saja itu hanya mengubah setiap huruf dan simbol menjadi angka dan merangkum semuanya. Pada kenyataannya, ini jauh lebih rumit dari itu, tapi mari kita selesaikan sekarang.

Keindahan dari algoritma semacam itu adalah bahwa jika Anda memasukkan input yang sama berulang kali, ia akan terus mengeluarkan angka yang sama setiap kali.

Ok, jadi pada dasarnya cara kerja tabel hash.

Hal-hal teknis berikut.

Pertama, ada ukuran angka. Biasanya, output dari algoritma hash tersebut berada di dalam kisaran sejumlah besar, biasanya jauh lebih besar dari ruang yang Anda miliki di tabel Anda. Misalnya, katakanlah kita memiliki ruang untuk tepat satu juta buku di perpustakaan. Output dari perhitungan hash bisa di kisaran 0 hingga satu miliar yang jauh lebih tinggi.

Jadi apa yang kita lakukan? Kami menggunakan sesuatu yang disebut perhitungan modulus, yang pada dasarnya mengatakan bahwa jika Anda menghitung ke angka yang Anda inginkan (yaitu satu miliar angka) tetapi ingin tetap berada di dalam rentang yang lebih kecil, setiap kali Anda menekan batas rentang yang lebih kecil itu Anda mulai kembali pada 0, tetapi Anda harus melacak seberapa jauh dalam urutan besar Anda telah datang.

Katakanlah bahwa output dari algoritma hash berada di kisaran 0 hingga 20 dan Anda mendapatkan nilai 17 dari judul tertentu. Jika ukuran perpustakaan hanya 7 buku, Anda menghitung 1, 2, 3, 4, 5, 6, dan ketika Anda sampai ke 7, Anda mulai kembali pada 0. Karena kita perlu menghitung 17 kali, kami memiliki 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, dan angka terakhirnya adalah 3.

Tentu saja perhitungan modulus tidak dilakukan seperti itu, itu dilakukan dengan pembagian dan sisanya. Sisa dari membagi 17 dengan 7 adalah 3 (7 berjalan 2 kali menjadi 17 pada 14 dan perbedaan antara 17 dan 14 adalah 3).

Dengan demikian, Anda meletakkan buku di slot nomor 3.

Ini mengarah ke masalah berikutnya. Tabrakan. Karena algoritme tidak memiliki cara untuk mengeluarkan buku sehingga mereka memenuhi perpustakaan dengan tepat (atau tabel hash jika Anda mau), itu akan selalu menghitung angka yang telah digunakan sebelumnya. Dalam arti perpustakaan, ketika Anda sampai ke rak dan nomor slot yang ingin Anda masukkan buku, sudah ada buku di sana.

Ada berbagai metode penanganan tabrakan, termasuk menjalankan data ke dalam perhitungan lain untuk mendapatkan tempat lain dalam tabel ( hashing ganda ), atau hanya untuk menemukan ruang yang dekat dengan yang Anda diberikan (yaitu tepat di sebelah buku sebelumnya dengan asumsi slot tersedia juga dikenal sebagai linear probing ). Ini berarti Anda harus melakukan beberapa penggalian saat Anda mencoba menemukan buku itu nanti, tetapi itu masih lebih baik daripada hanya mulai di salah satu ujung perpustakaan.

Akhirnya, pada titik tertentu, Anda mungkin ingin memasukkan lebih banyak buku ke perpustakaan daripada yang diizinkan perpustakaan. Dengan kata lain, Anda perlu membangun perpustakaan yang lebih besar. Karena tempat yang tepat di perpustakaan dihitung menggunakan ukuran perpustakaan yang tepat dan saat ini, maka akan mengikuti bahwa jika Anda mengubah ukuran perpustakaan Anda mungkin akhirnya harus menemukan tempat baru untuk semua buku karena perhitungan dilakukan untuk menemukan tempat mereka telah berubah.

Saya harap penjelasan ini sedikit lebih membumi daripada ember dan fungsi :)

Penggunaan dan Lingo:

1. Tabel hash digunakan untuk menyimpan dan mengambil data (atau catatan) dengan cepat.
2. Catatan disimpan dalam ember menggunakan kunci hash
3. Kunci hash dihitung dengan menerapkan algoritma hashing ke nilai yang dipilih (nilai kunci ) yang terkandung dalam catatan. Nilai yang dipilih ini harus menjadi nilai umum untuk semua catatan.
4. Setiap ember dapat memiliki beberapa catatan yang disusun dalam urutan tertentu.

Contoh Dunia Nyata:

Hash & Co. , yang didirikan pada 1803 dan tidak memiliki teknologi komputer, memiliki total 300 lemari arsip untuk menyimpan informasi terperinci (catatan) untuk sekitar 30.000 klien mereka. Setiap folder file diidentifikasi dengan jelas dengan nomor kliennya, nomor unik dari 0 hingga 29.999.

Panitera pengarsipan pada waktu itu harus dengan cepat mengambil dan menyimpan catatan klien untuk staf yang bekerja. Staf telah memutuskan bahwa akan lebih efisien untuk menggunakan metodologi hashing untuk menyimpan dan mengambil catatan mereka.

Untuk mengajukan catatan klien, pengarsipan pegawai akan menggunakan nomor klien unik yang tertulis di folder. Dengan menggunakan nomor klien ini, mereka akan memodulasi hash key oleh 300 untuk mengidentifikasi lemari arsip yang terkandung di dalamnya. Ketika mereka membuka lemari arsip mereka akan menemukan bahwa itu berisi banyak folder yang dipesan oleh nomor klien. Setelah mengidentifikasi lokasi yang benar, mereka hanya akan memasukkannya.

Untuk mengambil catatan klien, panitera pengarsipan akan diberi nomor klien pada selembar kertas. Dengan menggunakan nomor klien unik ini ( kunci hash ), mereka akan memodulasi dengan 300 untuk menentukan lemari arsip mana yang memiliki folder klien. Ketika mereka membuka lemari arsip mereka akan menemukan bahwa itu berisi banyak folder yang dipesan oleh nomor klien. Mencari melalui catatan mereka akan dengan cepat menemukan folder klien dan mengambilnya.

Dalam contoh dunia nyata kita, ember kita adalah lemari arsip dan catatan kita adalah folder file .

Satu hal yang penting untuk diingat adalah bahwa komputer (dan algoritmanya) menangani angka lebih baik daripada dengan string. Jadi mengakses array besar menggunakan indeks secara signifikan jauh lebih cepat daripada mengakses secara berurutan.

Seperti yang telah disebutkan oleh Simon yang saya yakini sangat penting adalah bahwa bagian hashing adalah mengubah ruang besar (dengan panjang acak, biasanya string, dll.) Dan memetakannya ke ruang kecil (ukuran diketahui, biasanya angka) untuk pengindeksan. Ini kalau sangat penting untuk diingat!

Jadi, dalam contoh di atas, sekitar 30.000 klien kemungkinan dipetakan ke ruang yang lebih kecil.

Gagasan utama dalam hal ini adalah untuk membagi seluruh set data Anda ke dalam segmen-segmen untuk mempercepat pencarian aktual yang biasanya memakan waktu. Dalam contoh kami di atas, masing-masing dari 300 lemari arsip akan (secara statistik) berisi sekitar 100 catatan. Pencarian (terlepas dari urutannya) melalui 100 catatan jauh lebih cepat daripada harus berurusan dengan 30.000.

Anda mungkin telah memperhatikan bahwa beberapa sebenarnya sudah melakukan ini. Tetapi alih-alih merancang metodologi hashing untuk menghasilkan kunci hash, mereka dalam banyak kasus hanya akan menggunakan huruf pertama dari nama belakang. Jadi jika Anda memiliki 26 lemari arsip yang masing-masing berisi surat dari A hingga Z, Anda secara teori baru saja membagi data Anda dan meningkatkan proses pengarsipan dan pengambilan.

Semoga ini membantu,

Jeach!

Ini ternyata merupakan bidang teori yang cukup dalam, tetapi garis dasarnya sederhana.

Pada dasarnya, fungsi hash hanyalah fungsi yang mengambil sesuatu dari satu ruang (katakanlah string dengan panjang sewenang-wenang) dan memetakannya ke ruang yang berguna untuk pengindeksan (bilangan bulat bertanda, katakanlah).

Jika Anda hanya memiliki sedikit ruang untuk di-hash, Anda mungkin bisa pergi dengan hanya menafsirkan hal-hal itu sebagai bilangan bulat, dan Anda selesai (mis. String 4 byte)

Namun, biasanya, Anda memiliki ruang yang jauh lebih besar. Jika ruang yang Anda izinkan sebagai kunci lebih besar dari ruang yang Anda gunakan untuk mengindeks (uint32 atau apa pun), maka Anda tidak mungkin memiliki nilai unik untuk masing-masingnya. Ketika dua atau lebih hal hash ke hasil yang sama, Anda harus menangani redundansi dengan cara yang tepat (ini biasanya disebut sebagai tabrakan, dan bagaimana Anda menanganinya atau tidak akan tergantung sedikit pada apa yang Anda miliki. menggunakan hash untuk).

Ini menyiratkan Anda ingin itu tidak mungkin memiliki hasil yang sama, dan Anda mungkin juga sangat ingin fungsi hash menjadi cepat.

Menyeimbangkan dua properti ini (dan beberapa lainnya) telah membuat banyak orang sibuk!

Dalam praktiknya Anda biasanya harus dapat menemukan fungsi yang diketahui berfungsi baik untuk aplikasi Anda dan menggunakannya.

Sekarang untuk menjadikan ini sebagai hashtable: Bayangkan Anda tidak peduli dengan penggunaan memori. Kemudian Anda dapat membuat array selama set pengindeksan Anda (semua uint32, misalnya). Saat Anda menambahkan sesuatu ke tabel, Anda hash kuncinya dan lihat array di indeks itu. Jika tidak ada apa-apa di sana, Anda menaruh nilai Anda di sana. Jika sudah ada sesuatu di sana, Anda menambahkan entri baru ini ke daftar hal-hal di alamat itu, bersama dengan informasi yang cukup (kunci asli Anda, atau sesuatu yang pintar) untuk menemukan entri mana yang sebenarnya milik kunci yang mana.

Jadi saat Anda berjalan lama, setiap entri dalam hashtable Anda (array) kosong, atau berisi satu entri, atau daftar entri. Mengambil adalah sederhana seperti pengindeksan ke dalam array, dan baik mengembalikan nilai, atau berjalan daftar nilai dan mengembalikan yang benar.

Tentu saja dalam praktiknya Anda biasanya tidak dapat melakukan ini, itu membuang-buang terlalu banyak memori. Jadi, Anda melakukan semuanya berdasarkan array jarang (di mana satu-satunya entri adalah yang benar-benar Anda gunakan, semua yang lain secara implisit nol).

Ada banyak skema dan trik untuk membuat ini bekerja lebih baik, tetapi itulah dasarnya.

Banyak jawaban, tetapi tidak ada satupun yang sangat visual , dan tabel hash dapat dengan mudah "klik" ketika divisualisasikan.

Tabel hash sering diimplementasikan sebagai array dari daftar yang ditautkan. Jika kita membayangkan sebuah tabel yang menyimpan nama orang, setelah beberapa penyisipan itu mungkin diletakkan dalam memori seperti di bawah ini, di mana ()angka-angka tertutup adalah nilai hash dari teks / nama.

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

Beberapa poin:

• masing-masing entri array (indeks [0], [1]...) dikenal sebagai bucket , dan memulai daftar nilai yang kemungkinan terkait - kosong (alias elemen , dalam contoh ini - nama orang )
• setiap nilai (misalnya "fred"dengan hash 42) dihubungkan dari bucket [hash % number_of_buckets]misalnya 42 % 10 == [2]; %adalah operator modulo - sisanya ketika dibagi dengan jumlah ember
• beberapa nilai data dapat bertabrakan dan dihubungkan dari bucket yang sama, paling sering karena nilai hash mereka bertabrakan setelah operasi modulo (misalnya 42 % 10 == [2], dan 9282 % 10 == [2]), tetapi kadang-kadang karena nilai hash sama (misalnya "fred"dan "jane"keduanya ditunjukkan dengan hash di 42atas)
  • sebagian besar tabel hash menangani tabrakan - dengan kinerja sedikit berkurang tetapi tanpa kebingungan fungsional - dengan membandingkan nilai penuh (di sini teks) dari nilai yang dicari atau dimasukkan ke setiap nilai yang sudah ada dalam daftar tertaut di hashed-to bucket

Panjang daftar tertaut terkait dengan faktor muatan, bukan jumlah nilai

Jika ukuran tabel bertambah, tabel hash yang diterapkan seperti di atas cenderung untuk mengubah ukurannya sendiri (yaitu membuat array yang lebih besar dari bucket, membuat daftar tertaut yang baru / yang diperbarui dari sana, menghapus array yang lama) untuk menjaga rasio nilai terhadap bucket (alias memuat faktor ) di suatu tempat dalam kisaran 0,5 hingga 1,0.

Hans memberikan rumus aktual untuk faktor muatan lainnya dalam komentar di bawah ini, tetapi untuk nilai indikatif: dengan faktor muatan 1 dan fungsi hash kekuatan kriptografi, 1 / e (~ 36,8%) ember cenderung kosong, 1 / e lainnya (~ 36,8%) memiliki satu elemen, 1 / (2e) atau ~ 18,4% dua elemen, 1 / (3! E) sekitar 6,1% tiga elemen, 1 / (4! E) atau ~ 1,5% empat elemen, 1 / (5! E) ~ .3% memiliki lima dll. - panjang rantai rata-rata dari ember yang tidak kosong adalah ~ 1,58 tidak peduli berapa banyak elemen dalam tabel (yaitu apakah ada 100 elemen dan 100 ember, atau 100 juta elemen dan 100 juta ember), itulah sebabnya kami mengatakan pencarian / masukkan / hapus adalah O (1) operasi waktu konstan.

Bagaimana tabel hash dapat mengaitkan kunci dengan nilai

Dengan penerapan tabel hash seperti dijelaskan di atas, kita dapat membayangkan membuat tipe nilai seperti struct Value { string name; int age; };, dan perbandingan kesetaraan dan fungsi hash yang hanya melihat namebidang (mengabaikan usia), dan kemudian sesuatu yang luar biasa terjadi: kita dapat menyimpan Valuecatatan seperti {"sue", 63}di tabel , lalu cari "sue" tanpa mengetahui usianya, cari nilai yang disimpan dan pulihkan atau bahkan perbarui usianya
- selamat ulang tahun Sue - yang menarik tidak mengubah nilai hash jadi tidak mengharuskan kami memindahkan catatan Sue ke yang lain ember.

Ketika kita melakukan ini, kita menggunakan tabel hash sebagai wadah asosiatif alias peta , dan nilai-nilai yang disimpannya dapat dianggap terdiri dari kunci (nama) dan satu atau lebih bidang lainnya masih disebut - membingungkan - nilainya ( dalam contoh saya, hanya usia). Implementasi tabel hash yang digunakan sebagai peta dikenal sebagai peta hash .

Ini kontras dengan contoh sebelumnya dalam jawaban ini di mana kami menyimpan nilai-nilai diskrit seperti "sue", yang dapat Anda anggap sebagai kuncinya sendiri: penggunaan semacam itu dikenal sebagai hash set .

Ada cara lain untuk mengimplementasikan tabel hash

Tidak semua tabel hash menggunakan daftar tertaut (dikenal sebagai rantai terpisah ), tetapi sebagian besar tujuan umum melakukannya, sebagai alternatif utama hashing tertutup (alias pengalamatan terbuka ) - terutama dengan operasi yang didukung penghapusan - memiliki sifat kinerja yang kurang stabil dengan kunci rawan tabrakan / fungsi hash.

Beberapa kata tentang fungsi hash

Hashing yang kuat ...

Tujuan umum, tugas fungsi hash meminimalkan tabrakan terburuk meminimalkan adalah untuk menyemprotkan kunci di sekitar tabel hash secara efektif secara acak, sambil selalu menghasilkan nilai hash yang sama untuk kunci yang sama. Bahkan satu bit yang berubah di mana saja di kunci idealnya - secara acak - membalik sekitar setengah bit dalam nilai hash yang dihasilkan.

Ini biasanya diatur dengan matematika yang terlalu rumit bagi saya untuk grok. Saya akan menyebutkan satu cara yang mudah dipahami - bukan yang paling skalabel atau ramah-cache tetapi secara inheren elegan (seperti enkripsi dengan pad sekali pakai!) - karena saya pikir ini membantu mengembalikan kualitas yang diinginkan yang disebutkan di atas. Katakanlah Anda hashing 64-bit doubles - Anda bisa membuat 8 tabel masing-masing 256 angka acak (kode di bawah), kemudian gunakan setiap irisan 8-bit / 1-byte doublerepresentasi memori untuk mengindeks ke tabel yang berbeda, XORing the angka acak yang Anda cari. Dengan pendekatan ini, mudah untuk melihat bahwa sedikit (dalam arti angka biner) berubah di mana saja dalam doublehasil dalam angka acak berbeda yang dilihat di salah satu tabel, dan nilai akhir yang sama sekali tidak berkorelasi.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
size_t random[8][256] = { ...random data... };
const char* p = (const char*)&my_double;
size_t hash = random[0][p[0]] ^ random[1][p[1]] ^ ... ^ random[7][p[7]];

Hashing lemah tapi sering cepat ...

Banyak fungsi hashing perpustakaan melewati bilangan bulat melalui tidak berubah (dikenal sebagai fungsi hash sepele atau identitas ); itu ekstrem lain dari hashing kuat yang dijelaskan di atas. Hash identitas sangattabrakan cenderung dalam kasus terburuk, tetapi harapannya adalah bahwa dalam kasus bilangan bulat yang cukup umum yang cenderung bertambah (mungkin dengan beberapa celah), mereka akan memetakan ke dalam ember berturut-turut yang meninggalkan lebih sedikit daun kosong daripada hashing acak (kami ~ 36,8 % pada load factor 1 yang disebutkan sebelumnya), sehingga memiliki lebih sedikit tabrakan dan lebih sedikit daftar elemen bertabrakan yang lebih lama dibandingkan dengan yang dicapai oleh pemetaan acak. Ini juga bagus untuk menghemat waktu yang diperlukan untuk menghasilkan hash yang kuat, dan jika kunci dicari agar dapat ditemukan dalam ember di dekatnya dalam memori, meningkatkan hit cache. Ketika kunci tidak bertambah baik, harapannya adalah mereka akan cukup acak mereka tidak akan membutuhkan fungsi hash yang kuat untuk secara acak mengacak penempatan mereka ke dalam ember.

Kalian sangat dekat untuk menjelaskan ini sepenuhnya, tetapi melewatkan beberapa hal. Hashtable hanyalah sebuah array. Array itu sendiri akan berisi sesuatu di setiap slot. Minimal Anda akan menyimpan nilai hash atau nilai itu sendiri di slot ini. Selain itu, Anda juga dapat menyimpan daftar nilai tertaut / berantai yang telah bertabrakan pada slot ini, atau Anda dapat menggunakan metode pengalamatan terbuka. Anda juga dapat menyimpan pointer atau pointer ke data lain yang ingin Anda ambil dari slot ini.

Penting untuk dicatat bahwa nilai hash itu sendiri umumnya tidak menunjukkan slot yang digunakan untuk menempatkan nilai. Misalnya, nilai hash mungkin nilai integer negatif. Jelas angka negatif tidak dapat menunjuk ke lokasi array. Selain itu, nilai hash akan cenderung berkali-kali angka lebih besar dari slot yang tersedia. Jadi perhitungan lain perlu dilakukan oleh hashtable itu sendiri untuk mengetahui slot mana yang harus dimasukkan nilainya. Ini dilakukan dengan operasi matematika modulus seperti:

uint slotIndex = hashValue % hashTableSize;

Nilai ini adalah slot nilai yang akan dimasukkan. Dalam pengalamatan terbuka, jika slot sudah diisi dengan nilai hash lain dan / atau data lain, operasi modulus akan dijalankan sekali lagi untuk menemukan slot berikutnya:

slotIndex = (remainder + 1) % hashTableSize;

Saya kira mungkin ada metode lain yang lebih maju untuk menentukan indeks slot, tetapi ini adalah yang umum saya lihat ... akan tertarik pada orang lain yang berkinerja lebih baik.

Dengan metode modulus, jika Anda memiliki tabel ukuran say 1000, nilai hash apa pun antara 1 dan 1000 akan masuk ke slot yang sesuai. Nilai negatif apa pun, dan nilai apa pun yang lebih besar dari 1000 akan berpotensi bertabrakan nilai slot. Peluang yang terjadi tergantung pada metode hashing Anda, serta berapa banyak total item yang Anda tambahkan ke tabel hash. Secara umum, praktik terbaik untuk membuat ukuran hashtable sehingga jumlah total nilai yang ditambahkan hanya sekitar 70% dari ukurannya. Jika fungsi hash Anda melakukan distribusi yang baik, Anda biasanya akan menemukan sangat sedikit atau tidak ada tabrakan / slot dan akan bekerja sangat cepat untuk operasi pencarian dan penulisan. Jika jumlah total nilai yang ditambahkan tidak diketahui sebelumnya, buatlah perkiraan yang baik dengan cara apa pun,

Saya harap ini membantu.

PS - Dalam C # GetHashCode()metode ini sangat lambat dan menghasilkan tabrakan nilai aktual di bawah banyak kondisi yang telah saya uji. Untuk bersenang-senang, buatlah fungsi Anda sendiri dan cobalah untuk TIDAK PERNAH bertabrakan dengan data spesifik yang Anda hashing, jalankan lebih cepat daripada GetHashCode, dan distribusikan dengan cukup merata. Saya telah melakukan ini menggunakan nilai hashcode panjang bukan ukuran int dan itu bekerja cukup baik hingga 32 juta nilai hash dalam hashtable dengan 0 tabrakan. Sayangnya saya tidak dapat membagikan kode karena itu milik majikan saya ... tetapi saya dapat mengungkapkan bahwa itu mungkin untuk domain data tertentu. Ketika Anda dapat mencapai ini, hashtable itu SANGAT cepat. :)

Beginilah cara kerjanya menurut pemahaman saya:

Berikut ini sebuah contoh: gambar seluruh meja sebagai serangkaian ember. Misalkan Anda memiliki implementasi dengan kode hash alfa-numerik dan memiliki satu ember untuk setiap huruf alfabet. Implementasi ini menempatkan setiap item yang kode hashnya dimulai dengan huruf tertentu di ember yang sesuai.

Katakanlah Anda memiliki 200 objek, tetapi hanya 15 di antaranya yang memiliki kode hash yang dimulai dengan huruf 'B.' Tabel hash hanya perlu mencari dan mencari melalui 15 objek dalam ember 'B', bukan semua 200 objek.

Sejauh menghitung kode hash, tidak ada yang ajaib tentang hal itu. Tujuannya adalah agar objek yang berbeda mengembalikan kode yang berbeda dan untuk objek yang sama mengembalikan kode yang sama. Anda bisa menulis kelas yang selalu mengembalikan bilangan bulat yang sama dengan kode hash untuk semua contoh, tetapi Anda pada dasarnya akan menghancurkan kegunaan tabel hash, karena hanya akan menjadi satu ember raksasa.

Pendek dan manis:

Tabel hash membungkus sebuah array, sebut saja itu internalArray. Item dimasukkan ke dalam array dengan cara ini:

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

Terkadang dua kunci akan hash ke indeks yang sama dalam array, dan Anda ingin mempertahankan kedua nilai. Saya suka menyimpan kedua nilai dalam indeks yang sama, yang mudah dikodekan dengan membuat internalArrayarray daftar tertaut:

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

Jadi, jika saya ingin mengambil item dari tabel hash saya, saya bisa menulis:

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

Hapus operasi sama mudahnya untuk menulis. Seperti yang Anda tahu, sisipkan, pencarian, dan penghapusan dari berbagai daftar tertaut kami hampir O (1).

Ketika internalArray kami menjadi terlalu penuh, mungkin sekitar 85% kapasitas, kami dapat mengubah ukuran array internal dan memindahkan semua item dari array lama ke array baru.

Bahkan lebih sederhana dari itu.

Hashtable tidak lebih dari sebuah array (biasanya jarang ) dari vektor yang berisi pasangan kunci / nilai. Ukuran maksimum array ini biasanya lebih kecil dari jumlah item dalam set nilai yang mungkin untuk jenis data yang disimpan dalam hashtable.

Algoritma hash digunakan untuk menghasilkan indeks ke dalam array berdasarkan nilai-nilai item yang akan disimpan dalam array.

Di sinilah menyimpan vektor pasangan kunci / nilai dalam array. Karena set nilai yang dapat diindeks dalam array biasanya lebih kecil dari jumlah semua nilai yang mungkin dimiliki oleh tipe tersebut, ada kemungkinan hash Anda Algoritma akan menghasilkan nilai yang sama untuk dua kunci terpisah. Sebuah baik algoritma hash akan mencegah hal ini sebanyak mungkin (yang mengapa adalah diturunkan ke jenis biasanya karena memiliki informasi spesifik yang algoritma hash umum tidak mungkin tahu), tapi itu tidak mungkin untuk mencegah.

Karena itu, Anda dapat memiliki beberapa kunci yang akan menghasilkan kode hash yang sama. Ketika itu terjadi, item dalam vektor iterasi melalui, dan perbandingan langsung dilakukan antara kunci dalam vektor dan kunci yang sedang dicari. Jika ditemukan, hebat dan nilai yang terkait dengan kunci dikembalikan, jika tidak, tidak ada yang dikembalikan.

Anda mengambil banyak hal, dan sebuah array.

Untuk setiap hal, Anda membuat indeks untuk itu, disebut hash. Yang penting tentang hash adalah bahwa ia 'banyak' tersebar; Anda tidak ingin dua hal serupa memiliki hash yang serupa.

Anda meletakkan barang-barang Anda ke dalam array pada posisi yang ditunjukkan oleh hash. Lebih dari satu hal dapat berakhir pada hash yang diberikan, sehingga Anda menyimpan barang-barang dalam array atau sesuatu yang sesuai, yang biasanya kita sebut ember.

Ketika Anda mencari hal-hal di hash, Anda pergi melalui langkah yang sama, mencari tahu nilai hash, kemudian melihat apa yang ada di ember di lokasi itu dan memeriksa apakah itu yang Anda cari.

Ketika hashing Anda bekerja dengan baik dan array Anda cukup besar, hanya akan ada beberapa hal paling banyak pada indeks tertentu dalam array, sehingga Anda tidak perlu melihat terlalu banyak.

Untuk poin bonus, buatlah agar ketika tabel hash Anda diakses, itu memindahkan hal yang ditemukan (jika ada) ke awal ember, jadi lain kali itu adalah hal pertama yang diperiksa.

Semua jawaban sejauh ini bagus, dan dapatkan berbagai aspek tentang cara kerja hashtable. Ini adalah contoh sederhana yang mungkin bisa membantu. Katakanlah kita ingin menyimpan beberapa item dengan string huruf kecil sebagai kunci.

Seperti yang dijelaskan simon, fungsi hash digunakan untuk memetakan dari ruang besar ke ruang kecil. Implementasi fungsi hash yang sederhana dan naif sebagai contoh kita dapat mengambil huruf pertama dari string, dan memetakannya ke integer, jadi "buaya" memiliki kode hash 0, "bee" memiliki kode hash 1, " zebra "akan menjadi 25, dll.

Selanjutnya kita memiliki array 26 ember (bisa jadi ArrayLists di Jawa), dan kita memasukkan item ke dalam ember yang cocok dengan kode hash kunci kita. Jika kita memiliki lebih dari satu item yang memiliki kunci yang dimulai dengan huruf yang sama, mereka akan memiliki kode hash yang sama, jadi semuanya akan masuk dalam ember untuk kode hash itu sehingga pencarian linear harus dilakukan dalam ember untuk temukan barang tertentu.

Dalam contoh kita, jika kita hanya memiliki beberapa lusin item dengan kunci yang mencakup alfabet, itu akan bekerja dengan sangat baik. Namun, jika kami memiliki sejuta item atau semua kunci dimulai dengan 'a' atau 'b', maka tabel hash kami tidak akan ideal. Untuk mendapatkan kinerja yang lebih baik, kita membutuhkan fungsi hash yang berbeda dan / atau lebih banyak bucket.

Berikut cara lain untuk melihatnya.

Saya berasumsi Anda memahami konsep array A. Itu adalah sesuatu yang mendukung operasi pengindeksan, di mana Anda bisa sampai ke elemen Ith, A [I], dalam satu langkah, tidak peduli seberapa besar A.

Jadi, misalnya, jika Anda ingin menyimpan informasi tentang sekelompok orang yang semuanya memiliki usia berbeda, cara sederhana adalah dengan memiliki array yang cukup besar, dan menggunakan usia setiap orang sebagai indeks ke dalam array. Ngomong-ngomong, Anda bisa memiliki akses satu langkah ke informasi siapa pun.

Tetapi tentu saja mungkin ada lebih dari satu orang dengan usia yang sama, jadi apa yang Anda masukkan dalam array pada setiap entri adalah daftar semua orang yang memiliki usia tersebut. Jadi, Anda dapat memperoleh informasi seseorang secara pribadi dalam satu langkah plus sedikit pencarian dalam daftar itu (disebut "ember"). Itu hanya melambat jika ada begitu banyak orang sehingga ember menjadi besar. Maka Anda memerlukan susunan yang lebih besar, dan beberapa cara lain untuk mendapatkan informasi identitas lebih banyak tentang orang tersebut, seperti beberapa huruf pertama dari nama keluarga mereka, alih-alih menggunakan usia.

Itu ide dasarnya. Alih-alih menggunakan usia, fungsi orang yang menghasilkan penyebaran nilai yang baik dapat digunakan. Itu fungsi hash. Seperti Anda dapat mengambil setiap bit ketiga dari representasi ASCII dari nama orang tersebut, diacak dalam beberapa urutan. Yang penting adalah Anda tidak ingin terlalu banyak orang melakukan hash ke ember yang sama, karena kecepatan tergantung pada ember yang tersisa kecil.

Bagaimana hash dihitung biasanya tidak tergantung pada hashtable, tetapi pada item yang ditambahkan. Dalam framework / pustaka kelas dasar seperti .net dan Java, setiap objek memiliki metode GetHashCode () (atau serupa) yang mengembalikan kode hash untuk objek ini. Algoritma kode hash yang ideal dan implementasi yang tepat tergantung pada data yang diwakili oleh dalam objek.

Tabel hash benar-benar berfungsi pada kenyataan bahwa perhitungan praktis mengikuti model mesin akses acak yaitu nilai pada setiap alamat dalam memori dapat diakses dalam waktu O (1) atau waktu konstan.

Jadi, jika saya memiliki alam semesta kunci (set semua kunci yang mungkin dapat saya gunakan dalam aplikasi, mis. Roll no. Untuk siswa, jika 4 digit maka alam semesta ini adalah kumpulan angka dari 1 hingga 9999), dan cara untuk memetakannya ke sejumlah terbatas ukuran saya dapat mengalokasikan memori dalam sistem saya, secara teoritis tabel hash saya siap.

Secara umum, dalam aplikasi ukuran semesta kunci sangat besar daripada jumlah elemen yang ingin saya tambahkan ke tabel hash (Saya tidak ingin menyia-nyiakan memori 1 GB untuk hash, katakanlah, 10000 atau 100000 nilai integer karena mereka 32 agak panjang dalam reprsentaion biner). Jadi, kami menggunakan hashing ini. Ini semacam semacam pencampuran operasi "matematis", yang memetakan alam semesta saya yang besar ke sejumlah kecil nilai yang dapat saya akomodasikan dalam memori. Dalam kasus-kasus praktis, sering kali ruang tabel hash memiliki "urutan" yang sama (big-O) dengan (jumlah elemen * ukuran masing-masing elemen), Jadi, kami tidak membuang banyak memori.

Sekarang, satu set besar dipetakan ke set kecil, pemetaan harus banyak-ke-satu. Jadi, tombol yang berbeda akan dibagikan ruang yang sama (?? tidak adil). Ada beberapa cara untuk menangani ini, saya hanya tahu dua yang populer dari mereka:

• Gunakan ruang yang akan dialokasikan ke nilai sebagai referensi ke daftar tertaut. Daftar tertaut ini akan menyimpan satu atau lebih nilai, yang berada di slot yang sama dalam pemetaan banyak ke satu. Daftar tertaut juga berisi kunci untuk membantu seseorang yang datang mencari. Seperti banyak orang di apartemen yang sama, ketika seorang pengantar barang datang, dia pergi ke kamar dan meminta secara khusus untuk pria itu.
• Gunakan fungsi hash ganda dalam array yang memberikan urutan nilai yang sama setiap kali daripada nilai tunggal. Ketika saya pergi untuk menyimpan nilai, saya melihat apakah lokasi memori yang diperlukan bebas atau terisi. Jika gratis, saya dapat menyimpan nilai saya di sana, jika sudah diisi saya mengambil nilai berikutnya dari urutan dan seterusnya sampai saya menemukan lokasi gratis dan saya menyimpan nilai saya di sana. Saat mencari atau mengambil kembali nilai, saya kembali ke jalur yang sama seperti yang diberikan oleh urutan dan di setiap lokasi meminta vaue apakah ada di sana sampai saya menemukannya atau mencari semua lokasi yang mungkin dalam array.

Pengantar Algoritma oleh CLRS memberikan wawasan yang sangat baik tentang topik tersebut.

Untuk semua yang mencari bahasa pemrograman, berikut adalah cara kerjanya. Implementasi internal dari hashtable lanjutan memiliki banyak seluk-beluk dan optimisasi untuk alokasi / deallokasi penyimpanan dan pencarian, tetapi ide tingkat atas akan sangat sama.

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

di mana calculate_bucket_from_val()fungsi hashing di mana semua keajaiban keunikan harus terjadi.

Aturan praktisnya adalah: Untuk nilai yang diberikan untuk dimasukkan, ember harus UNIK & DERIVABEL DARI NILAI yang seharusnya disimpan.

Bucket adalah ruang di mana nilai disimpan - karena di sini saya menyimpannya sebagai indeks array, tetapi mungkin juga merupakan lokasi memori.