Fungsi Hash
Dalam bahagian ini, kita akan membincangkan tentang fungsi cincang yang membantu untuk melaksanakan kod cincang kunci berkaitan item data dalam struktur data seperti yang dinyatakan dalam perkara berikut:
Int hashItem ( int kunci ){
kembali kunci % saiz meja ;
}
Proses melaksanakan indeks tatasusunan dipanggil pencincangan. Kadangkala, jenis kod yang sama dilaksanakan untuk menjana indeks yang sama menggunakan kekunci yang sama yang dipanggil perlanggaran yang dikendalikan melalui perangkaian berbeza (penciptaan senarai terpaut) dan pelaksanaan strategi pengalamatan terbuka.
Mengerjakan Jadual Hash dalam C++
Penunjuk kepada nilai sebenar disimpan dalam jadual cincang. Ia menggunakan kunci untuk mencari indeks tatasusunan di mana nilai terhadap kunci perlu disimpan di lokasi yang dikehendaki dalam tatasusunan. Kami mengambil jadual hash yang mempunyai saiz 10 seperti yang dinyatakan dalam berikut:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Marilah kita mengambil sebarang data secara rawak terhadap kunci yang berbeza dan menyimpan kunci ini dalam jadual cincang dengan hanya mengira indeks. Jadi, data disimpan terhadap kunci dalam indeks yang dikira dengan bantuan fungsi cincang. Katakan kita mengambil data = {14,25,42,55,63,84} dan kunci =[ 15,9,5,25,66,75 ].
Kira indeks data ini menggunakan fungsi cincang. Nilai indeks dinyatakan dalam perkara berikut:
| kunci | lima belas | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Kira 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 |
Selepas mencipta indeks tatasusunan, letakkan data pada kunci pada indeks tepat tatasusunan yang diberikan seperti yang diterangkan sebelum ini.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Selepas itu, kita boleh melihat bahawa perlanggaran berlaku jika dua atau lebih kunci mempunyai kod cincang yang sama yang menghasilkan indeks yang sama bagi elemen dalam tatasusunan. Kami mempunyai satu penyelesaian untuk mengelakkan kemungkinan perlanggaran: memilih kaedah cincang yang baik dan melaksanakan strategi yang tepat.
Sekarang, mari kita bincangkan teknik pelaksanaan yang berbeza dengan bantuan contoh yang betul.
Contoh: Tambah Data dalam Jadual Hash Menggunakan Teknik Hashing Terbuka
Dalam contoh ini, kami mengambil teknik pelaksanaan seperti Open Hashing untuk mengelakkan perlanggaran dalam jadual cincang. Dalam pencincangan terbuka atau perangkaian, kami membuat senarai terpaut untuk merantai nilai jadual cincang. Coretan kod contoh ini dilampirkan dalam perkara berikut yang menerangkan teknik pencincangan terbuka:
#include#include
kelas HashTable {
persendirian :
statik const int Saiz meja = 10 ;
std :: senarai < int > tableHas [ Saiz meja ] ;
int hashFunc ( int kunci ) {
kembali kunci % Saiz meja ;
}
awam :
batal masukkan ( int kunci ) {
int indeks = hashFunc ( kunci ) ;
tableHas [ indeks ] . menolak kembali ( kunci ) ;
}
batal lihat Jadual ( ) {
untuk ( int i = 0 ; i < Saiz meja ; ++ i ) {
std :: cout << '[' << i << ']' ;
untuk ( auto ia = tableHas [ i ] . bermula ( ) ; ia ! = tableHas [ i ] . tamat ( ) ; ++ ia ) {
std :: cout << ' -> ' << * ia ;
}
std :: cout << std :: endl ;
}
}
} ;
int utama ( ) {
HashTable hasTable ;
hasTable. masukkan ( lima belas ) ;
hasTable. masukkan ( 33 ) ;
hasTable. masukkan ( 23 ) ;
hasTable. masukkan ( 65 ) ;
hasTable. masukkan ( 3 ) ;
hasTable. lihat Jadual ( ) ;
kembali 0 ;
}
Ini adalah contoh yang sangat menarik: kami membina senarai terpaut dan memasukkan data dalam jadual cincang. Pertama sekali, kami mentakrifkan perpustakaan pada permulaan program. The < senarai > perpustakaan digunakan untuk pelaksanaan senarai terpaut. Selepas itu, kami membina kelas bernama 'HashTable' dan mencipta atribut kelas yang peribadi sebagai saiz jadual dan tatasusunan jadual menggunakan kata kunci 'private:'. Ingat bahawa atribut peribadi tidak boleh digunakan di luar kelas. Di sini, kami mengambil saiz jadual sebagai '10'. Kami memulakan kaedah cincang menggunakan ini dan mengira indeks jadual cincang. Dalam fungsi cincang, kami lulus kunci dan saiz jadual cincang.
Kami membina beberapa fungsi yang diperlukan dan menjadikan fungsi ini umum dalam kelas. Ingat bahawa fungsi awam boleh digunakan di luar kelas di mana-mana sahaja. Kami menggunakan kata kunci 'awam:' untuk memulakan bahagian awam kelas . Memandangkan kami ingin menambah elemen baharu pada jadual cincang, kami mencipta fungsi bernama 'InsertHash' dengan kunci sebagai hujah bagi fungsi tersebut. Dalam fungsi 'masukkan', kami memulakan pembolehubah indeks. Kami menghantar fungsi hash kepada pembolehubah indeks. Selepas itu, hantar pembolehubah indeks ke jadual senarai terpautHas[]menggunakan kaedah 'tolak' untuk memasukkan elemen dalam jadual.
Selepas itu, kami membina fungsi 'viewHashTab' untuk memaparkan jadual cincang untuk melihat data yang baru dimasukkan. Dalam fungsi ini, kami mengambil gelung 'untuk' yang mencari nilai sehingga penghujung jadual cincang. Pastikan nilai disimpan pada indeks yang sama yang dibangunkan menggunakan fungsi cincang. Dalam gelung, kami lulus nilai pada indeks masing-masing dan menamatkan kelas di sini. Dalam fungsi 'utama', kami mengambil objek kelas bernama 'hasTable'. Dengan bantuan objek kelas ini, kita boleh mengakses kaedah penyisipan dengan menghantar kunci dalam kaedah. Kunci yang kami luluskan dalam fungsi 'utama' dikira dalam fungsi 'sisipkan' yang mengembalikan kedudukan indeks dalam jadual cincang. Kami memaparkan jadual cincang dengan memanggil fungsi 'pandangan' dengan bantuan objek 'Kelas'.
Output kod ini dilampirkan dalam yang berikut:
Seperti yang dapat kita lihat, jadual cincang berjaya dibuat menggunakan senarai terpaut dalam C++. Rantaian terbuka digunakan untuk mengelakkan perlanggaran indeks yang sama.
Kesimpulan
Akhirnya, kami membuat kesimpulan bahawa jadual cincang ialah teknik yang paling baru muncul untuk menyimpan dan mendapatkan kunci dengan pasangan nilai untuk mengendalikan sejumlah besar data dengan cekap. Peluang perlanggaran adalah sangat tinggi dalam jadual cincang, memusnahkan data dan storannya. Kita boleh mengatasi perlanggaran ini menggunakan teknik pengurusan jadual cincang yang berbeza. Dengan membangunkan jadual cincang dalam C++, pembangun boleh meningkatkan prestasi menggunakan teknik terbaik yang sesuai untuk menyimpan data dalam jadual cincang. Kami berharap artikel ini berguna untuk pemahaman anda tentang jadual hash.