Phenquestions
Asumsikan bahwa Anda adalah pemilik toko perlengkapan besar di daerah tempat Anda tinggal. Asumsikan Anda tinggal di area yang luas, yang bukan area komersial. Anda bukan satu-satunya yang memiliki toko perbekalan di area tersebut; Anda memiliki beberapa pesaing. Dan kemudian terpikir oleh Anda bahwa Anda harus mencatat nomor telepon pelanggan Anda di buku latihan. Tentu saja, buku latihannya kecil, dan Anda tidak dapat mencatat semua nomor telepon untuk semua pelanggan Anda.
Jadi, Anda memutuskan untuk hanya mencatat nomor telepon pelanggan tetap Anda. Jadi Anda memiliki tabel dengan dua kolom. Kolom di sebelah kiri memiliki nama pelanggan, dan kolom di sebelah kanan memiliki nomor telepon yang sesuai. Dengan cara ini, ada pemetaan antara nama pelanggan dan nomor telepon. Kolom kanan tabel dapat dianggap sebagai tabel hash inti. Nama pelanggan sekarang disebut kunci, dan nomor telepon disebut nilai. Perhatikan bahwa ketika pelanggan melakukan transfer, Anda harus membatalkan barisnya, membiarkan baris kosong atau diganti dengan pelanggan reguler baru. Perhatikan juga bahwa seiring waktu, jumlah pelanggan tetap dapat bertambah atau berkurang, sehingga meja dapat bertambah atau berkurang or.
Sebagai contoh pemetaan lainnya, asumsikan bahwa ada klub petani di suatu kabupaten. Tentu saja, tidak semua petani akan menjadi anggota klub. Beberapa anggota klub tidak akan menjadi anggota tetap (kehadiran dan kontribusi). Bar-man dapat memutuskan untuk mencatat nama-nama anggota dan minuman pilihan mereka. Dia mengembangkan tabel dua kolom. Di kolom kiri, dia menulis nama-nama anggota klub. Di kolom kanan, dia menulis pilihan minuman yang sesuai.
Ada masalah di sini: ada duplikat di kolom kanan. Artinya, nama minuman yang sama ditemukan lebih dari satu kali. Dengan kata lain, anggota yang berbeda minum minuman manis yang sama atau minuman beralkohol yang sama, sementara anggota lain minum minuman manis atau beralkohol yang berbeda. Bar-man memutuskan untuk memecahkan masalah ini dengan memasukkan kolom sempit di antara dua kolom. Di kolom tengah ini, mulai dari atas, dia memberi nomor baris mulai dari nol (i.e. 0, 1, 2, 3, 4, dst.), turun, satu indeks per baris. Dengan ini, masalahnya terpecahkan, karena nama anggota sekarang dipetakan ke indeks, dan bukan ke nama minuman. Jadi, saat minuman diidentifikasi oleh indeks, nama pelanggan dipetakan ke indeks yang sesuai.
Kolom nilai (minuman) saja membentuk tabel hash dasar. Dalam tabel yang dimodifikasi, kolom indeks dan nilai terkaitnya (dengan atau tanpa duplikat) membentuk tabel hash normal - definisi lengkap dari tabel hash diberikan di bawah ini. Kunci (kolom pertama) tidak selalu merupakan bagian dari tabel hash.
Sebagai contoh lain lagi, pertimbangkan server jaringan di mana pengguna dari komputer kliennya dapat menambahkan beberapa informasi, menghapus beberapa informasi, atau mengubah beberapa informasi. Ada banyak pengguna untuk server. Setiap nama pengguna sesuai dengan kata sandi yang disimpan di server. Mereka yang memelihara server dapat melihat nama pengguna dan kata sandi yang sesuai, sehingga dapat merusak pekerjaan pengguna.
Jadi pemilik server memutuskan untuk membuat fungsi yang mengenkripsi kata sandi sebelum disimpan. Seorang pengguna masuk ke server, dengan kata sandi yang dipahami secara normal. Namun, sekarang, setiap kata sandi disimpan dalam bentuk terenkripsi. Jika ada yang melihat kata sandi terenkripsi dan mencoba masuk menggunakannya, itu tidak akan berfungsi, karena masuk, menerima kata sandi yang dipahami oleh server, dan bukan kata sandi terenkripsi.
Dalam hal ini, kata sandi yang dipahami adalah kuncinya, dan kata sandi terenkripsi adalah nilainya. Jika kata sandi terenkripsi ada di kolom kata sandi terenkripsi, maka kolom itu adalah tabel hash dasar. Jika kolom itu didahului oleh kolom lain dengan indeks yang dimulai dari nol, sehingga setiap kata sandi terenkripsi, dikaitkan dengan indeks, maka kolom indeks dan kolom kata sandi terenkripsi, membentuk tabel hash normal. Kunci belum tentu merupakan bagian dari tabel hash.
Perhatikan, dalam hal ini, bahwa setiap kunci, yang merupakan kata sandi yang dipahami, sesuai dengan nama pengguna. Jadi, ada nama pengguna yang sesuai dengan kunci yang dipetakan ke indeks, yang dikaitkan dengan nilai yang merupakan kunci terenkripsi.
Definisi fungsi hash, definisi lengkap tabel hash, arti array, dan detail lainnya diberikan di bawah ini. Anda perlu memiliki pengetahuan dalam pointer (referensi) dan daftar tertaut, untuk menghargai sisa tutorial ini.
Arti Fungsi Hash dan Tabel Hash
Himpunan
Array adalah sekumpulan lokasi memori berurutan. Semua lokasi memiliki ukuran yang sama. Nilai di lokasi pertama diakses dengan indeks, 0; nilai di lokasi kedua diakses dengan indeks, 1; nilai ketiga diakses dengan indeks, 2; keempat dengan indeks, 3; dan seterusnya. Array biasanya tidak dapat bertambah atau berkurang. Untuk mengubah ukuran (panjang) larik, larik baru harus dibuat, dan nilai terkait disalin ke larik baru. Nilai-nilai array selalu bertipe sama.
Fungsi Hash
Dalam perangkat lunak, fungsi hash adalah fungsi yang mengambil kunci dan menghasilkan indeks yang sesuai untuk sel array. Array berukuran tetap (panjang tetap). Jumlah kunci berukuran sewenang-wenang, biasanya lebih besar dari ukuran array. Indeks yang dihasilkan dari fungsi hash disebut nilai hash atau intisari atau kode hash atau hanya hash.
Tabel Hash
Tabel hash adalah array dengan nilai, yang indeksnya, kuncinya dipetakan. Kunci secara tidak langsung dipetakan ke nilai. Faktanya, kunci dikatakan dipetakan ke nilai, karena setiap indeks dikaitkan dengan nilai (dengan atau tanpa duplikat). Namun, fungsi yang melakukan pemetaan (i.e. hashing) menghubungkan kunci ke indeks array dan tidak benar-benar dengan nilai, karena mungkin ada duplikat dalam nilai. Diagram berikut mengilustrasikan tabel hash untuk nama orang dan nomor teleponnya. Sel array (slot) disebut ember called.
Perhatikan bahwa beberapa ember kosong. Tabel hash tidak harus memiliki nilai di semua keranjangnya. Nilai dalam ember tidak harus dalam urutan menaik. Namun, indeks yang terkait dengannya berada dalam urutan menaik. Panah menunjukkan pemetaan. Perhatikan bahwa kunci tidak dalam array. Mereka tidak harus berada dalam struktur apa pun. Fungsi hash mengambil kunci apa saja, dan mengeluarkan indeks untuk array. Jika tidak ada nilai dalam ember yang terkait dengan hash indeks, nilai baru dapat dimasukkan ke dalam ember itu. Hubungan logis adalah antara kunci dan indeks, dan bukan antara kunci dan nilai yang terkait dengan indeks.
Nilai-nilai array, seperti yang ada di tabel hash ini, selalu memiliki tipe data yang sama. Tabel hash (ember) dapat menghubungkan kunci ke nilai dari tipe data yang berbeda. Dalam hal ini, nilai-nilai array adalah semua pointer, menunjuk ke tipe nilai yang berbeda.
Tabel hash adalah array dengan fungsi hash. Fungsi mengambil kunci dan hash indeks yang sesuai, dan menghubungkan kunci ke nilai, dalam array. Kunci tidak harus menjadi bagian dari tabel hash.
Mengapa Array dan bukan Daftar Tertaut untuk Tabel Hash
Array untuk tabel hash dapat diganti dengan struktur data daftar tertaut, tetapi akan ada masalah. Elemen pertama dari daftar tertaut secara alami berada di indeks, 0; elemen kedua secara alami pada indeks, 1; yang ketiga secara alami pada indeks, 2; dan seterusnya. Masalah dengan daftar tertaut adalah bahwa untuk mengambil nilai, daftar harus diulang, dan ini membutuhkan waktu. Mengakses nilai dalam array adalah dengan akses acak. Setelah indeks diketahui, nilai diperoleh tanpa iterasi; akses ini lebih cepat.
Tabrakan
Fungsi hash mengambil kunci dan meng-hash indeks yang sesuai, untuk membaca nilai terkait, atau untuk memasukkan nilai baru. Jika tujuannya adalah untuk membaca nilai, tidak ada masalah (tidak masalah), sejauh ini. Namun, jika tujuannya adalah untuk memasukkan nilai, indeks hash mungkin sudah memiliki nilai terkait, dan itu adalah tabrakan; nilai baru tidak dapat diletakkan di tempat yang sudah ada nilainya. Ada cara untuk menyelesaikan tabrakan - lihat di bawah.
Mengapa Tabrakan Terjadi
Dalam contoh toko persediaan di atas, nama pelanggan adalah kuncinya, dan nama minuman adalah nilainya. Perhatikan bahwa pelanggan terlalu banyak, sedangkan array memiliki ukuran terbatas, dan tidak dapat mengambil semua pelanggan. Jadi, hanya minuman pelanggan tetap yang disimpan dalam susunan. Tabrakan akan terjadi ketika pelanggan tidak tetap menjadi pelanggan tetap. Pelanggan untuk toko membentuk satu set besar, sedangkan jumlah ember untuk pelanggan dalam barisan terbatas.
Dengan tabel hash, itu adalah nilai untuk kunci yang sangat mungkin, yang dicatat. Ketika kunci yang tidak mungkin, menjadi mungkin, mungkin akan terjadi tabrakan. Faktanya, tabrakan selalu terjadi dengan tabel hash.
Dasar-dasar Resolusi Tabrakan
Dua pendekatan untuk resolusi tabrakan disebut Rantai Terpisah dan Pengalamatan Terbuka. Secara teori, kunci tidak boleh berada dalam struktur data atau tidak boleh menjadi bagian dari tabel hash. Namun, kedua pendekatan mengharuskan kolom kunci mendahului tabel hash dan menjadi bagian dari keseluruhan struktur. Alih-alih kunci berada di kolom kunci, penunjuk ke kunci mungkin ada di kolom kunci.
Tabel hash praktis menyertakan kolom kunci, tetapi kolom kunci ini tidak secara resmi menjadi bagian dari tabel hash.
Salah satu pendekatan untuk resolusi dapat memiliki ember kosong, tidak harus di akhir array.
Rantai Terpisah
Dalam rantai terpisah, ketika tabrakan terjadi, nilai baru ditambahkan ke kanan (bukan di atas atau di bawah) dari nilai yang bertabrakan. Jadi dua atau tiga nilai akhirnya memiliki indeks yang sama. Jarang lebih dari tiga harus memiliki indeks yang sama.
Bisakah lebih dari satu nilai benar-benar memiliki indeks yang sama dalam sebuah array?? - Tidak. Jadi dalam banyak kasus, nilai pertama untuk indeks adalah penunjuk ke struktur data daftar tertaut, yang menyimpan satu, dua, atau tiga nilai yang bertabrakan. Diagram berikut adalah contoh tabel hash untuk rantai terpisah pelanggan dan nomor telepon mereka:
Ember kosong ditandai dengan huruf x. Sisa slot memiliki petunjuk ke daftar tertaut. Setiap elemen daftar tertaut memiliki dua bidang data: satu untuk nama pelanggan dan yang lainnya untuk nomor telepon phone. Konflik terjadi untuk kunci: Peter Jones dan Suzan Lee. Nilai yang sesuai terdiri dari dua elemen dari satu daftar tertaut.
Untuk kunci yang bertentangan, kriteria untuk memasukkan nilai adalah kriteria yang sama yang digunakan untuk menemukan (dan membaca) nilai.
Buka Pengalamatan
Dengan pengalamatan terbuka, semua nilai disimpan dalam larik bucket. Ketika konflik terjadi, nilai baru dimasukkan ke dalam ember kosong baru nilai yang sesuai untuk konflik, mengikuti beberapa kriteria. Kriteria yang digunakan untuk memasukkan nilai pada konflik adalah kriteria yang sama yang digunakan untuk menemukan (mencari dan membaca) nilai.
Diagram berikut menggambarkan resolusi konflik dengan pengalamatan terbuka:
Fungsi hash mengambil kunci, Peter Jones dan meng-hash indeks, 152, dan menyimpan nomor teleponnya di keranjang terkait. Setelah beberapa waktu, fungsi hash meng-hash indeks yang sama, 152 dari kunci, Suzan Lee, bertabrakan dengan indeks untuk Peter Jones. Untuk mengatasi ini, nilai untuk Suzan Lee disimpan di ember indeks berikutnya, 153, yang kosong. Fungsi hash meng-hash indeks, 153 untuk kunci, Robin Hood, tetapi indeks ini telah digunakan untuk menyelesaikan konflik untuk kunci sebelumnya. Jadi nilai Robin Hood ditempatkan di ember kosong berikutnya, yaitu indeks 154.
Metode Penyelesaian Konflik untuk Rantai Terpisah dan Penanganan Terbuka
Rantai terpisah memiliki metodenya sendiri untuk menyelesaikan konflik, dan pengalamatan terbuka juga memiliki metodenya sendiri untuk menyelesaikan konflik.
Metode untuk menyelesaikan Konflik Rantai Terpisah
Metode untuk tabel hash chaining terpisah dijelaskan secara singkat sekarang:
Rantai Terpisah dengan Daftar Tertaut
Metode ini seperti yang dijelaskan di atas. Namun, setiap elemen dari daftar tertaut tidak harus memiliki bidang kunci (mis.g. bidang nama pelanggan di atas).
Rantai Terpisah dengan Sel Kepala Daftar
Dalam metode ini, elemen pertama dari daftar tertaut disimpan dalam ember array. Ini dimungkinkan, jika tipe data untuk array, adalah elemen dari daftar tertaut.
Rantai Terpisah dengan Struktur lain
Struktur data lainnya, seperti Pohon Pencarian Biner Penyeimbang Mandiri yang mendukung operasi yang diperlukan, dapat digunakan sebagai pengganti daftar tertaut - lihat nanti.
Metode untuk menyelesaikan Konflik Penanganan Terbuka
Sebuah metode untuk menyelesaikan konflik dalam pengalamatan terbuka disebut urutan probe. Tiga urutan probe terkenal dijelaskan secara singkat sekarang:
Penyelidikan Linier
Dengan probing linier, ketika konflik terjadi, ember kosong terdekat di bawah ember konflik, dicari. Juga, dengan probing linier, baik kunci dan nilainya disimpan dalam ember yang sama.
Penyelidikan Kuadrat
Asumsikan bahwa konflik terjadi pada indeks H. Slot kosong berikutnya (ember) pada indeks H + 12 digunakan; jika yang sudah terisi, selanjutnya kosong pada H+22 digunakan, jika sudah terisi, selanjutnya kosong pada H + 32 digunakan, dan sebagainya. Ada varian untuk ini.
Hashing ganda
Dengan hashing ganda, ada dua fungsi hash. Yang pertama menghitung (hash) indeks. Jika terjadi konflik, yang kedua menggunakan kunci yang sama untuk menentukan seberapa jauh nilai yang harus dimasukkan. Ada lebih dari ini - lihat nanti.
Fungsi Hash Sempurna
Fungsi hash sempurna adalah fungsi hash yang tidak dapat menghasilkan tumbukan apa pun. Ini bisa terjadi ketika set kunci relatif kecil, dan setiap kunci memetakan ke bilangan bulat tertentu dalam tabel hash.
Dalam Kumpulan Karakter ASCII, karakter huruf besar dapat dipetakan ke huruf kecil yang sesuai menggunakan fungsi hash. Huruf direpresentasikan dalam memori komputer sebagai angka. Dalam Set Karakter ASCII, A adalah 65, B adalah 66, C adalah 67, dll. dan a adalah 97, b adalah 98, c adalah 99, dst. Untuk memetakan dari A ke a, tambahkan 32 hingga 65; untuk memetakan dari B ke b, tambahkan 32 menjadi 66; untuk memetakan dari C ke c, tambahkan 32 menjadi 67; dan seterusnya. Di sini, huruf besar adalah kuncinya, dan huruf kecil adalah nilainya. Tabel hash untuk ini dapat berupa array yang nilainya merupakan indeks terkait. Ingat, ember array bisa kosong. Jadi ember dalam larik dari 64 hingga 0 bisa kosong. Fungsi hash hanya menambahkan 32 ke nomor kode huruf besar untuk mendapatkan indeks, dan karenanya huruf kecil. Fungsi seperti itu adalah fungsi hash yang sempurna.
Hashing dari Integer ke Integer Indeks
Ada berbagai metode untuk hashing integer. Salah satunya disebut Modulo Division Method (Fungsi).
Fungsi Hashing Divisi Modulo
Fungsi dalam perangkat lunak komputer bukanlah fungsi matematika. Dalam komputasi (perangkat lunak), suatu fungsi terdiri dari sekumpulan pernyataan yang didahului oleh argumen. Untuk Fungsi Divisi Modulo, kuncinya adalah bilangan bulat dan dipetakan ke indeks larik bucket. Kumpulan kunci besar, jadi hanya kunci yang sangat mungkin terjadi dalam aktivitas yang akan dipetakan. Jadi tabrakan terjadi ketika kunci yang tidak mungkin harus dipetakan.
Dalam pernyataan,
20 / 6 = 3R2
20 adalah hasil bagi, 6 adalah pembagi, dan 3 sisa 2 adalah hasil bagi. Sisanya 2 juga disebut modulo. Catatan: dimungkinkan untuk memiliki modulo 0.
Untuk hashing ini, ukuran tabel biasanya pangkat 2, e.g. 64 = 26 atau 256 = 28, dll. Pembagi untuk fungsi hashing ini adalah bilangan prima yang mendekati ukuran array. Fungsi ini membagi kunci dengan pembagi dan mengembalikan modulo. Modulo adalah indeks dari array ember. Nilai terkait dalam ember adalah nilai pilihan Anda (nilai untuk kunci).
Kunci Panjang Variabel Hashing
Di sini, kunci dari kumpulan kunci adalah teks dengan panjang yang berbeda. Bilangan bulat yang berbeda dapat disimpan dalam memori menggunakan jumlah byte yang sama (ukuran karakter bahasa Inggris adalah satu byte). Ketika kunci yang berbeda memiliki ukuran byte yang berbeda, mereka dikatakan memiliki panjang variabel. Salah satu metode untuk hashing panjang variabel disebut Radix Konversi Hashing.
Hashing Konversi Radix
Dalam string, setiap karakter di komputer adalah angka. Dalam metode ini,
Kode Hash (indeks) = x0Sebuahk−1+x1Sebuahk−2+… +xk−2Sebuah1+xk−1Sebuah0
Dimana (x0, x1,… , xk−1) adalah karakter dari string input dan a adalah radix, e.g. 29 (lihat nanti). k adalah jumlah karakter dalam string. Ada lebih dari ini - lihat nanti.
Kunci dan Nilai
Dalam pasangan kunci/nilai, suatu nilai belum tentu berupa angka atau teks. Itu juga bisa menjadi rekor. Catatan adalah daftar yang ditulis secara horizontal horizontal. Dalam pasangan kunci/nilai, setiap kunci sebenarnya dapat merujuk ke beberapa teks atau nomor atau catatan lain.
Array Asosiatif
Daftar adalah struktur data, di mana item daftar terkait, dan ada satu set operasi yang beroperasi pada daftar. Setiap item daftar dapat terdiri dari sepasang item. Tabel hash umum dengan kuncinya dapat dianggap sebagai struktur data, tetapi lebih merupakan sistem daripada struktur data data. Kunci dan nilainya yang sesuai tidak terlalu bergantung satu sama lain. Mereka tidak terlalu berhubungan satu sama lain.
Di sisi lain, array asosiatif adalah hal yang serupa, tetapi kunci dan nilainya sangat bergantung satu sama lain; mereka sangat berhubungan satu sama lain. Misalnya, Anda dapat memiliki rangkaian buah asosiatif dan warnanya. Setiap buah secara alami memiliki warnanya. Nama buah adalah kuncinya; warna adalah nilai. Selama penyisipan, setiap kunci dimasukkan dengan nilainya. Saat menghapus, setiap kunci dihapus dengan nilainya.
Array asosiatif adalah struktur data tabel hash yang terdiri dari pasangan kunci/nilai, di mana tidak ada duplikat untuk kunci. Nilai dapat memiliki duplikat. Dalam situasi ini, kunci adalah bagian dari struktur. Artinya, kunci harus disimpan, sedangkan, dengan tabel hast umum, kunci tidak harus disimpan. Masalah nilai yang digandakan secara alami diselesaikan oleh indeks array ember. Jangan bingung antara nilai duplikat dan tabrakan pada indeks collision.
Karena array asosiatif adalah struktur data, setidaknya memiliki operasi berikut:
Operasi Array Asosiatif
menyisipkan atau menambahkan
Ini memasukkan pasangan kunci/nilai baru ke dalam koleksi, memetakan kunci ke nilainya.
menugaskan kembali
Operasi ini menggantikan nilai kunci tertentu ke nilai baru.
hapus atau hapus
Ini menghapus kunci ditambah nilai yang sesuai.
mencari
Operasi ini mencari nilai dari kunci tertentu dan mengembalikan nilai (tanpa menghapusnya).
Kesimpulan
Struktur data tabel hash terdiri dari array dan fungsi. Fungsi tersebut disebut fungsi hash. Fungsi memetakan kunci ke nilai dalam array melalui indeks array. Kunci tidak harus menjadi bagian dari struktur data. Kumpulan kunci biasanya lebih besar dari nilai yang disimpan. Ketika tabrakan terjadi, itu diselesaikan dengan Pendekatan Rantai Terpisah atau Pendekatan Pengalamatan Terbuka. Array asosiatif adalah kasus khusus dari struktur data tabel hash.
