Fungsi Hash
Pada bagian ini, kita akan membahas tentang fungsi hash yang membantu mengeksekusi kode hash dari kunci terkait item data dalam struktur data seperti yang disebutkan berikut ini:
ke dalam hashItem ( ke dalam kunci ){
kembali kunci % ukuran tabel ;
}
Proses mengeksekusi indeks array disebut hashing. Kadang-kadang, jenis kode yang sama dieksekusi untuk menghasilkan indeks yang sama menggunakan kunci yang sama yang disebut tabrakan yang ditangani melalui rangkaian berbeda (pembuatan daftar tertaut) dan implementasi strategi pengalamatan terbuka.
Cara Kerja Tabel Hash di C++
Petunjuk ke nilai sebenarnya disimpan di tabel hash. Ia menggunakan kunci untuk mencari indeks array di mana nilai-nilai terhadap kunci perlu disimpan di lokasi yang diinginkan dalam array. Kami mengambil tabel hash berukuran 10 seperti yang disebutkan berikut ini:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Mari kita secara acak mengambil data apa pun terhadap kunci yang berbeda dan menyimpan kunci ini dalam tabel hash hanya dengan menghitung indeks. Jadi, data disimpan terhadap kunci dalam indeks terhitung dengan bantuan fungsi hash. Misalkan kita mengambil data = {14,25,42,55,63,84} dan kunci =[ 15,9,5,25,66,75 ].
Hitung indeks data ini menggunakan fungsi hash. Nilai indeks disebutkan sebagai berikut:
| Kunci | limabelas | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Hitung Indeks | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Data | 14 | 25 | 42 | 55 | 63 | 84 |
Setelah membuat indeks array, tempatkan data pada kunci pada indeks yang tepat dari array tertentu seperti yang dijelaskan sebelumnya.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Setelah itu, kita dapat melihat bahwa tabrakan terjadi jika dua kunci atau lebih memiliki kode hash yang sama yang menghasilkan indeks elemen dalam array yang sama. Kami memiliki satu solusi untuk menghindari kemungkinan tabrakan: memilih metode hash yang baik dan menerapkan strategi yang akurat.
Sekarang, mari kita bahas berbagai teknik implementasi dengan bantuan contoh yang tepat.
Contoh: Menambahkan Data dalam Tabel Hash Menggunakan Teknik Hashing Terbuka
Dalam contoh ini, kami mengambil teknik implementasi seperti Open Hashing untuk menghindari tabrakan pada tabel hash. Dalam hashing atau chaining terbuka, kami membuat daftar tertaut untuk merangkai nilai tabel hash. Cuplikan kode contoh ini terlampir berikut ini yang menjelaskan teknik hashing terbuka:
#termasuk#sertakan
kelas Tabel Hash {
pribadi :
statis konstanta ke dalam ukuran meja = 10 ;
std :: daftar < ke dalam > mejaMemiliki [ ukuran meja ] ;
ke dalam fungsi hash ( ke dalam kunci ) {
kembali kunci % ukuran meja ;
}
publik :
ruang kosong menyisipkan ( ke dalam kunci ) {
ke dalam indeks = fungsi hash ( kunci ) ;
mejaMemiliki [ indeks ] . dorong_kembali ( kunci ) ;
}
ruang kosong lihat Tabel ( ) {
untuk ( ke dalam Saya = 0 ; Saya < ukuran meja ; ++ Saya ) {
std :: cout << '[' << Saya << ']' ;
untuk ( mobil dia = mejaMemiliki [ Saya ] . mulai ( ) ; dia ! = mejaMemiliki [ Saya ] . akhir ( ) ; ++ dia ) {
std :: cout << ' -> ' << * dia ;
}
std :: cout << std :: akhir ;
}
}
} ;
ke dalam utama ( ) {
HashTable memiliki Tabel ;
hasTable. menyisipkan ( limabelas ) ;
hasTable. menyisipkan ( 33 ) ;
hasTable. menyisipkan ( 23 ) ;
hasTable. menyisipkan ( 65 ) ;
hasTable. menyisipkan ( 3 ) ;
hasTable. lihat Tabel ( ) ;
kembali 0 ;
}
Ini adalah contoh yang sangat menarik: kita membuat daftar tertaut dan memasukkan data ke dalam tabel hash. Pertama-tama, kita mendefinisikan perpustakaan di awal program. Itu < daftar > perpustakaan digunakan untuk implementasi daftar tertaut. Setelah itu, kita membangun sebuah kelas bernama “HashTable” dan membuat atribut kelas tersebut yang bersifat private sebagai ukuran tabel dan array tabel menggunakan kata kunci “private:”. Ingatlah bahwa atribut privat tidak dapat digunakan di luar kelas. Di sini, kami mengambil ukuran tabel sebagai “10”. Kami menginisialisasi metode hash menggunakan ini dan menghitung indeks tabel hash. Dalam fungsi hash, kami meneruskan kunci dan ukuran tabel hash.
Kami membangun beberapa fungsi yang diperlukan dan menjadikan fungsi-fungsi ini publik di kelas. Ingatlah bahwa fungsi publik dapat digunakan di luar kelas dimana saja. Kami menggunakan kata kunci “publik:” untuk memulai bagian publik kelas . Karena kita ingin menambahkan elemen baru ke tabel hash, kita membuat fungsi bernama “InsertHash” dengan kunci sebagai argumen fungsi tersebut. Dalam fungsi “sisipkan”, kami menginisialisasi variabel indeks. Kami meneruskan fungsi hash ke variabel indeks. Setelah itu, teruskan variabel indeks ke daftar tertaut tableHas[]menggunakan metode “push” untuk menyisipkan elemen ke dalam tabel.
Setelah itu, kita membuat fungsi “viewHashTab” untuk menampilkan tabel hash guna melihat data yang baru dimasukkan. Dalam fungsi ini, kita mengambil loop “untuk” yang mencari nilai hingga akhir tabel hash. Pastikan nilai disimpan pada indeks yang sama yang dikembangkan menggunakan fungsi hash. Dalam perulangan, kita meneruskan nilai pada indeksnya masing-masing dan mengakhiri kelas di sini. Dalam fungsi “main”, kita mengambil objek dari kelas bernama “hasTable”. Dengan bantuan objek kelas ini, kita dapat mengakses metode penyisipan dengan meneruskan kunci dalam metode tersebut. Kunci yang kita lewati dalam fungsi “utama” dihitung dalam fungsi “masukkan” yang mengembalikan posisi indeks dalam tabel hash. Kami menampilkan tabel hash dengan memanggil fungsi “view” dengan bantuan objek “Class”.
Output dari kode ini terlampir sebagai berikut:
Seperti yang bisa kita lihat, tabel hash berhasil dibuat menggunakan daftar tertaut di C++. Rantai terbuka digunakan untuk menghindari benturan indeks yang sama.
Kesimpulan
Pada akhirnya, kami menyimpulkan bahwa tabel hash adalah teknik paling baru untuk menyimpan dan mendapatkan kunci dengan pasangan nilai untuk menangani data dalam jumlah besar secara efisien. Kemungkinan tabrakan sangat tinggi pada tabel hash, sehingga merusak data dan penyimpanannya. Kita dapat mengatasi tabrakan ini dengan menggunakan teknik manajemen tabel hash yang berbeda. Dengan mengembangkan tabel hash di C++, pengembang dapat meningkatkan kinerja menggunakan teknik yang paling sesuai untuk menyimpan data dalam tabel hash. Kami harap artikel ini bermanfaat untuk pemahaman Anda tentang tabel hash.