Phenquestions
Anggaplah anda pemilik kedai besar di daerah tempat anda tinggal. Anggaplah anda tinggal di kawasan yang luas, yang bukan kawasan komersial. Anda bukan satu-satunya yang mempunyai kedai barang di kawasan ini; anda mempunyai beberapa pesaing. Oleh itu, anda harus mencatat nombor telefon pelanggan anda dalam buku latihan. Sudah tentu, buku latihan kecil dan anda tidak dapat mencatat semua nombor telefon untuk semua pelanggan anda.
Oleh itu, anda memutuskan untuk mencatat hanya nombor telefon pelanggan tetap anda. Oleh itu, anda mempunyai jadual dengan dua lajur. Lajur di sebelah kiri mempunyai nama pelanggan, dan lajur di sebelah kanan mempunyai nombor telefon yang sesuai. Dengan cara ini, terdapat pemetaan antara nama pelanggan dan nombor telefon. Lajur kanan jadual boleh dianggap sebagai jadual hash teras. Nama pelanggan kini dipanggil kunci, dan nombor telefon disebut nilai. Perhatikan bahawa semasa pelanggan beralih, anda harus membatalkan barisnya, membiarkan baris kosong atau digantikan dengan pelanggan tetap baru. Juga perhatikan bahawa seiring dengan berjalannya waktu, jumlah pelanggan tetap dapat meningkat atau menurun, sehingga meja dapat bertambah atau menyusut.
Sebagai contoh pemetaan lain, anggaplah bahawa terdapat sebuah kelab petani di sebuah daerah. Sudah tentu, tidak semua petani akan menjadi ahli kelab. Sebilangan ahli kelab tidak akan menjadi ahli tetap (kehadiran dan sumbangan). Peguam boleh memutuskan untuk mencatat nama ahli dan minuman pilihan mereka. Dia mengembangkan jadual dua lajur. Di lajur kiri, dia menulis nama-nama ahli kelab. Di lajur kanan, dia menulis pilihan minuman yang sesuai.
Terdapat masalah di sini: terdapat pendua di lajur kanan. Maksudnya, minuman yang sama dijumpai lebih dari sekali. Dengan kata lain, ahli yang berbeza minum minuman manis yang sama atau minuman beralkohol yang sama, sementara anggota lain minum minuman manis atau alkohol yang berbeza. Peguam memutuskan untuk menyelesaikan masalah ini dengan memasukkan lajur sempit antara dua lajur. Di lajur tengah ini, bermula dari atas, dia nombor baris bermula dari sifar (i.e. 0, 1, 2, 3, 4, dll.), turun, satu indeks setiap baris. Dengan ini, masalahnya diselesaikan, kerana nama ahli sekarang memetakan ke indeks, dan bukan pada nama minuman. Oleh itu, sebagai minuman dikenal pasti oleh indeks, nama pelanggan dipetakan ke indeks yang sesuai.
Lajur nilai (minuman) sahaja membentuk jadual hash asas. Dalam jadual yang diubah, lajur indeks dan nilai yang berkaitan (dengan atau tanpa pendua) membentuk jadual hash biasa - definisi penuh jadual hash diberikan di bawah. Kunci (lajur pertama) tidak semestinya menjadi sebahagian daripada jadual hash.
Sebagai contoh lain lagi, pertimbangkan pelayan rangkaian di mana pengguna dari komputer pelanggannya dapat menambahkan beberapa maklumat, menghapus beberapa maklumat, atau mengubah beberapa maklumat. Terdapat banyak pengguna untuk pelayan. Setiap nama pengguna sesuai dengan kata laluan yang disimpan di pelayan. Mereka yang mengekalkan pelayan dapat melihat nama pengguna dan kata laluan yang sesuai, dan dapat merosakkan kerja pengguna.
Oleh itu, pemilik pelayan memutuskan untuk menghasilkan fungsi yang menyulitkan kata laluan sebelum disimpan. Seorang pengguna log masuk ke pelayan, dengan kata laluannya yang biasa difahami. Namun, sekarang, setiap kata laluan disimpan dalam bentuk yang dienkripsi. Sekiranya ada yang melihat kata laluan yang dienkripsi dan cuba log masuk menggunakannya, ia tidak akan berfungsi, kerana log masuk, menerima kata laluan yang difahami oleh pelayan, dan bukan kata laluan yang dienkripsi.
Dalam kes ini, kata laluan yang difahami adalah kuncinya, dan kata laluan yang disulitkan adalah nilainya. Sekiranya kata laluan yang dienkripsi berada di lajur kata laluan yang dienkripsi, maka lajur itu adalah jadual hash asas. Sekiranya lajur itu didahului oleh lajur lain dengan indeks yang bermula dari sifar, sehingga setiap kata laluan yang dienkripsi, dikaitkan dengan indeks, maka kedua lajur indeks dan lajur kata laluan yang dienkripsi, membentuk jadual hash biasa. Kunci tidak semestinya sebahagian daripada jadual hash.
Perhatikan, dalam kes ini, bahawa setiap kunci, yang merupakan kata laluan yang difahami, sesuai dengan nama pengguna. Jadi, ada nama pengguna yang sesuai dengan kunci yang dipetakan ke indeks, yang dikaitkan dengan nilai yang merupakan kunci yang dienkripsi.
Definisi fungsi hash, definisi penuh jadual hash, makna array, dan perincian lain diberikan di bawah. Anda perlu mempunyai pengetahuan dalam petunjuk (rujukan) dan senarai terpaut, untuk menghargai sisa tutorial ini.
Makna Fungsi Hash dan Jadual Hash
Array
Array adalah sekumpulan lokasi memori berturut-turut. Semua lokasi mempunyai 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 sebagainya. Susunan biasanya tidak dapat meningkat atau menyusut. Untuk mengubah ukuran (panjang) array, array baru harus dibuat, dan nilai yang sesuai disalin ke array baru. Nilai larik selalu jenis yang sama.
Fungsi Hash
Dalam perisian, fungsi hash adalah fungsi yang mengambil kunci dan menghasilkan indeks yang sesuai untuk sel array. Susunannya berukuran tetap (panjang tetap). Bilangan kunci adalah ukuran sewenang-wenang, biasanya lebih besar daripada ukuran array. Indeks yang dihasilkan dari fungsi hash disebut nilai hash atau digest atau kod hash atau hanya hash.
Jadual Hash
Jadual hash adalah array dengan nilai, yang indeksnya, kunci dipetakan. Kunci secara tidak langsung dipetakan ke nilai. Sebenarnya, kunci dikatakan dipetakan ke nilai, kerana setiap indeks dikaitkan dengan nilai (dengan atau tanpa pendua). Walau bagaimanapun, fungsi yang melakukan pemetaan (i.e. hashing) mengaitkan kunci ke indeks array dan tidak benar-benar dengan nilai, kerana mungkin terdapat pendua dalam nilai. Gambar rajah berikut menunjukkan jadual hash untuk nama orang dan nombor telefon mereka. Sel array (slot) dipanggil baldi.
Perhatikan bahawa beberapa baldi kosong. Jadual hash tidak semestinya mempunyai nilai di semua baldi. Nilai dalam baldi tidak semestinya dalam urutan menaik. Walau bagaimanapun, indeks yang berkaitan dengannya berada dalam urutan menaik. Anak panah menunjukkan pemetaan. Perhatikan bahawa kunci tidak terdapat dalam array. Mereka tidak perlu berada dalam struktur apa pun. Fungsi hash mengambil kunci apa pun, dan mencuci indeks untuk array. Sekiranya tidak ada nilai dalam baldi yang dikaitkan dengan hash indeks, nilai baru mungkin dimasukkan ke dalam baldi tersebut. Hubungan logik adalah antara kunci dan indeks, dan bukan antara kunci dan nilai yang berkaitan dengan indeks.
Nilai array, seperti yang terdapat dalam jadual hash ini, selalu jenis data yang sama. Jadual hash (baldi) dapat menghubungkan kunci ke nilai dari pelbagai jenis data. Dalam kes ini, nilai array adalah semua penunjuk, menunjuk pada jenis nilai yang berbeza.
Jadual hash adalah susunan dengan fungsi hash. Fungsi mengambil kunci dan mencuci indeks yang sesuai, dan menghubungkan kunci dengan nilai, dalam array. Kunci tidak harus menjadi sebahagian daripada jadual hash.
Mengapa Senarai dan Senarai Tidak Berkaitan untuk Jadual Hash
Susunan untuk jadual hash dapat diganti dengan struktur data senarai yang dipautkan, tetapi akan ada masalah. Elemen pertama senarai terpaut secara semula jadi pada indeks, 0; elemen kedua secara semula jadi pada indeks, 1; yang ketiga secara semula jadi berada di indeks, 2; dan sebagainya. Masalah dengan senarai yang dipautkan adalah bahawa untuk mendapatkan nilai, senarai itu harus diulang, dan ini memerlukan masa. Mengakses nilai dalam array adalah dengan akses rawak. Setelah indeks diketahui, nilainya diperoleh tanpa lelaran; akses ini lebih pantas.
Perlanggaran
Fungsi hash mengambil kunci dan mencuci indeks yang sesuai, untuk membaca nilai yang berkaitan, atau untuk memasukkan nilai baru. Sekiranya tujuannya adalah membaca nilai, sejauh ini tidak ada masalah (tidak ada masalah). Namun, jika tujuannya adalah untuk memasukkan nilai, indeks hash mungkin sudah mempunyai nilai yang terkait, dan itu adalah perlanggaran; nilai baru tidak boleh diletakkan di mana sudah ada nilai. Terdapat cara untuk menyelesaikan perlanggaran - lihat di bawah.
Mengapa Perlanggaran Berlaku
Dalam contoh kedai penyediaan di atas, nama pelanggan adalah kunci, dan nama minuman adalah nilai. Perhatikan bahawa pelanggan terlalu banyak, sedangkan array memiliki ukuran yang terbatas, dan tidak dapat menerima semua pelanggan. Jadi, hanya minuman pelanggan biasa yang disimpan dalam barisan. Pertembungan akan berlaku apabila pelanggan tidak tetap menjadi biasa. Pelanggan untuk kedai membentuk satu set besar, sementara jumlah baldi untuk pelanggan dalam rangkaian adalah terhad.
Dengan jadual hash, nilai untuk kunci yang sangat mungkin, akan direkodkan. Apabila kunci yang tidak mungkin, menjadi mungkin, kemungkinan akan berlaku perlanggaran. Sebenarnya, perlanggaran selalu berlaku dengan jadual hash.
Asas Penyelesaian Perlanggaran
Dua pendekatan untuk penyelesaian perlanggaran disebut Separate Chaining dan Open Address. Secara teori, kunci tidak boleh berada dalam struktur data atau tidak boleh menjadi sebahagian daripada jadual hash. Walau bagaimanapun, kedua-dua pendekatan tersebut memerlukan ruang utama mendahului jadual hash dan menjadi sebahagian daripada keseluruhan struktur. Daripada kunci berada di lajur kunci, penunjuk ke kunci mungkin berada di lajur kunci.
Jadual hash praktikal merangkumi lajur kunci, tetapi lajur kunci ini bukan secara rasmi sebahagian daripada jadual hash.
Salah satu kaedah penyelesaian boleh mempunyai baldi kosong, tidak semestinya di hujung larik.
Rantai Berasingan
Dalam rantai berasingan, apabila berlaku perlanggaran, nilai baru ditambahkan di sebelah kanan (bukan di atas atau di bawah) dari nilai bertembung. Jadi dua atau tiga nilai akhirnya mempunyai indeks yang sama. Jarang lebih daripada tiga mempunyai indeks yang sama.
Bolehkah lebih daripada satu nilai mempunyai indeks yang sama dalam satu array? - Tidak. Oleh itu, dalam banyak kes, nilai pertama untuk indeks adalah penunjuk ke struktur data senarai yang dipautkan, yang menyimpan nilai satu, dua, atau tiga bertembung. Gambar rajah berikut adalah contoh jadual hash untuk berantai pelanggan dan nombor telefon mereka yang berasingan:
Baldi kosong ditandai dengan huruf x. Slot selebihnya mempunyai petunjuk ke senarai terpaut. Setiap elemen senarai terpaut mempunyai dua bidang data: satu untuk nama pelanggan dan satu lagi untuk nombor telefon. Konflik berlaku untuk kunci: Peter Jones dan Suzan Lee. Nilai yang sesuai terdiri daripada dua elemen dari satu senarai terpaut.
Untuk kunci yang bertentangan, kriteria untuk memasukkan nilai adalah kriteria yang sama yang digunakan untuk mencari (dan membaca) nilainya.
Buka Alamat
Dengan pengalamatan terbuka, semua nilai disimpan dalam susunan baldi. Apabila konflik berlaku, nilai baru dimasukkan ke dalam keranjang kosong baru nilai yang sesuai untuk konflik, mengikuti beberapa kriteria. Kriteria yang digunakan untuk memasukkan nilai pada konflik adalah kriteria yang sama digunakan untuk mencari (mencari dan membaca) nilai.
Gambar rajah berikut menggambarkan penyelesaian konflik dengan pengalamatan terbuka:
Fungsi hash mengambil kunci, Peter Jones dan mencuci indeks, 152, dan menyimpan nombor telefonnya di baldi yang berkaitan. Setelah beberapa waktu, fungsi hash mencuci indeks yang sama, 152 dari kunci, Suzan Lee, bertembung dengan indeks untuk Peter Jones. Untuk menyelesaikannya, nilai untuk Suzan Lee disimpan dalam baldi indeks seterusnya, 153, yang kosong. Fungsi hash mencuci indeks, 153 untuk kunci, Robin Hood, tetapi indeks ini telah digunakan untuk menyelesaikan konflik untuk kunci sebelumnya. Jadi nilai untuk Robin Hood diletakkan di dalam baldi kosong seterusnya, iaitu nilai indeks 154.
Kaedah Menyelesaikan Konflik untuk Berantai Berasingan dan Berpidato Terbuka
Berantai terpisah mempunyai kaedah untuk menyelesaikan konflik, dan pengalamatan terbuka juga mempunyai kaedahnya sendiri untuk menyelesaikan konflik.
Kaedah untuk menyelesaikan Konflik Berantai Berasingan
Kaedah untuk jadual hash berantai terpisah dijelaskan secara ringkas sekarang:
Rantai Berasingan dengan Senarai Terpaut
Kaedah ini adalah seperti yang dijelaskan di atas. Walau bagaimanapun, setiap elemen senarai terpaut tidak semestinya mempunyai bidang utama (e.g. bidang nama pelanggan di atas).
Rantai Berasingan dengan Cell Head List
Dalam kaedah ini, elemen pertama dari senarai terpaut disimpan dalam baldi array. Ini mungkin, jika jenis data untuk array, adalah elemen dari senarai terpaut.
Rantai Berasingan dengan Struktur lain
Sebarang struktur data lain, seperti Pohon Carian Binary Self-Balancing yang menyokong operasi yang diperlukan, boleh digunakan sebagai ganti senarai yang dipautkan - lihat kemudian.
Kaedah untuk menyelesaikan Konflik Menangani Terbuka
Kaedah untuk menyelesaikan konflik dalam pengalamatan terbuka disebut urutan probe. Tiga urutan probe yang terkenal dijelaskan secara ringkas sekarang:
Pemeriksaan Linear
Dengan penyiasatan linier, apabila berlaku konflik, baldi kosong terdekat di bawah baldi bertentangan, dicari. Dengan probing linear, kunci dan nilainya disimpan dalam baldi yang sama.
Pemeriksaan Kuadratik
Andaikan konflik berlaku pada indeks H. Slot kosong seterusnya (baldi) pada indeks H + 12 digunakan; jika itu sudah dihuni, maka yang berikutnya kosong di H + 22 digunakan, jika itu sudah dihuni, maka kosong berikutnya di H + 32 digunakan, dan sebagainya. Terdapat varian untuk ini.
Double Hashing
Dengan hashing berganda, terdapat dua fungsi hash. Yang pertama mengira (mencuci) indeks. Sekiranya konflik berlaku, yang kedua menggunakan kunci yang sama untuk menentukan sejauh mana nilai harus dimasukkan. Terdapat lebih banyak perkara ini - lihat kemudian.
Fungsi Hash Sempurna
Fungsi hash yang sempurna adalah fungsi hash yang tidak dapat mengakibatkan perlanggaran. Ini boleh berlaku apabila set kunci agak kecil, dan setiap kunci memetakan bilangan bulat tertentu dalam jadual hash.
Dalam Set Karakter ASCII, watak huruf besar dapat dipetakan ke huruf kecil yang sesuai dengan menggunakan fungsi hash. Huruf ditunjukkan dalam memori komputer sebagai nombor. Dalam Set Karakter ASCII, A adalah 65, B adalah 66, C adalah 67, dll. dan a adalah 97, b adalah 98, c adalah 99, dll. Untuk memetakan dari A hingga a, tambahkan 32 hingga 65; untuk memetakan dari B ke b, tambah 32 hingga 66; untuk memetakan dari C hingga c, tambah 32 hingga 67; dan sebagainya. Di sini, huruf besar adalah kuncinya, dan huruf kecil adalah nilainya. Jadual hash untuk ini boleh berupa array yang nilainya adalah indeks yang berkaitan. Ingat, baldi array boleh kosong. Jadi baldi dalam array dari 64 hingga 0 boleh kosong. Fungsi hash hanya menambah 32 pada nombor kod huruf besar untuk mendapatkan indeks, dan dengan itu huruf kecil. Fungsi sedemikian adalah fungsi hash yang sempurna.
Hashing dari Indeks Integer ke Integer
Terdapat kaedah yang berbeza untuk hashing integer. Salah satunya disebut Kaedah Pembahagian Modulo (Fungsi).
Fungsi Hashing Bahagian Modulo
Fungsi dalam perisian komputer bukan fungsi matematik. Dalam pengkomputeran (perisian), fungsi terdiri dari sekumpulan pernyataan yang didahului oleh argumen. Untuk Fungsi Pembahagian Modulo, kunci adalah bilangan bulat dan dipetakan ke indeks susunan baldi. Set kunci besar, jadi hanya kunci yang sangat mungkin berlaku dalam aktiviti yang akan dipetakan. Oleh itu, perlanggaran berlaku apabila kunci yang tidak mungkin mesti dipetakan.
Dalam penyataan tersebut,
20/6 = 3R2
20 adalah dividen, 6 adalah pembahagi, dan 3 selebihnya 2 adalah pembahagi. Selebihnya 2 juga disebut modulo. Catatan: mungkin ada modulo 0.
Untuk hashing ini, ukuran meja biasanya adalah kekuatan 2, e.g. 64 = 26 atau 256 = 28, dan lain-lain. Pembahagi untuk fungsi hashing ini adalah nombor perdana yang hampir dengan ukuran array. Fungsi ini membahagi kunci oleh pembahagi dan mengembalikan modulo. Modul adalah indeks susunan baldi. Nilai yang berkaitan dalam baldi adalah nilai pilihan anda (nilai untuk kunci).
Kekunci Panjang Pembolehubah Hashing
Di sini, kunci set kunci adalah teks dengan panjang yang berbeza. Bilangan bulat yang berbeza dapat disimpan dalam memori menggunakan bilangan bait yang sama (ukuran watak Inggeris adalah bait). Apabila kunci yang berlainan mempunyai ukuran bait yang berbeza, ia dikatakan panjangnya berubah-ubah. Salah satu kaedah untuk hashing panjang berubah adalah Radix Conversion Hashing.
Hashing Penukaran Radix
Dalam rentetan, setiap watak dalam komputer adalah nombor. Dalam kaedah ini,
Hash Code (indeks) = x0ak − 1+x1ak − 2+... + xk − 2a1+xk − 1a0
Di mana (x0, x1,…, xk − 1) adalah watak rentetan input dan a adalah radix, e.g. 29 (lihat kemudian). k ialah bilangan aksara dalam rentetan. Terdapat lebih banyak perkara ini - lihat kemudian.
Kunci dan Nilai
Dalam pasangan kunci / nilai, nilai tidak semestinya berupa nombor atau teks. Ia juga boleh menjadi rekod. Rekod adalah senarai yang ditulis secara mendatar. Dalam pasangan kunci / nilai, setiap kunci sebenarnya merujuk kepada beberapa teks atau nombor atau rekod lain.
Array Bersekutu
Senarai adalah struktur data, di mana item-item senarai berkaitan, dan ada sekumpulan operasi yang beroperasi di dalam daftar. Setiap item senarai boleh terdiri daripada sepasang item. Jadual hash umum dengan kuncinya dapat dianggap sebagai struktur data, tetapi lebih merupakan sistem daripada struktur data. Kunci dan nilai yang sepadan tidak saling bergantung antara satu sama lain. Mereka tidak saling berkaitan antara satu sama lain.
Sebaliknya, susunan bersekutu adalah perkara yang serupa, tetapi kunci dan nilainya sangat bergantung satu sama lain; mereka sangat berkaitan antara satu sama lain. Contohnya, anda boleh mempunyai sebatian buah-buahan dan warnanya. Setiap buah secara semula jadi mempunyai warnanya. Nama buah adalah kuncinya; warna adalah nilai. Semasa penyisipan, setiap kunci dimasukkan dengan nilainya. Semasa memadam, setiap kunci dihapuskan dengan nilainya.
Susunan asosiatif adalah struktur data jadual hash yang terdiri daripada pasangan kunci / nilai, di mana tidak ada pendua untuk kunci. Nilai boleh mempunyai pendua. Dalam keadaan ini, kunci adalah sebahagian daripada struktur. Maksudnya, kunci mesti disimpan, sedangkan, dengan jadual umum, kunci tidak perlu disimpan. Masalah nilai pendua secara semula jadi diselesaikan oleh indeks susunan baldi. Jangan mengelirukan antara nilai pendua dan perlanggaran pada indeks.
Oleh kerana array asosiatif adalah struktur data, sekurang-kurangnya mempunyai operasi berikut:
Operasi Array Bersekutu
masukkan atau tambah
Ini memasukkan pasangan kunci / nilai baru ke dalam koleksi, memetakan kunci ke nilainya.
menetapkan semula
Operasi ini menggantikan nilai kunci tertentu ke nilai baru.
padam atau buang
Ini mengeluarkan kunci ditambah dengan nilai yang sepadan.
mencari
Operasi ini mencari nilai kunci tertentu dan mengembalikan nilai (tanpa mengeluarkannya).
Kesimpulannya
Struktur data jadual hash terdiri daripada array dan fungsi. Fungsi tersebut disebut fungsi hash. Fungsi memetakan kunci nilai dalam array melalui indeks array. Kunci tidak semestinya menjadi sebahagian daripada struktur data. Set kunci biasanya lebih besar daripada nilai yang disimpan. Apabila perlanggaran berlaku, ia diselesaikan sama ada dengan Pendekatan Berantai Berasingan atau Pendekatan Pengalamatan Terbuka. Susunan asosiatif adalah kes khas struktur data jadual hash.
