Perbedaan antara hashing dinamis dan statis

Dalam struktur data, hashing adalah teknik memetakan sejumlah besar item data ke tabel yang lebih kecil menggunakan fungsi khusus yang disebut fungsi hash untuk akses yang lebih cepat. Terkadang struktur data sangat besar sehingga hampir tidak mungkin mencari semua nilai indeks melalui semua level untuk mengakses blok data akhir. Di sinilah hashing masuk. Apa yang dilakukannya adalah menghitung lokasi catatan data pada disk secara langsung tanpa menggunakan struktur indeks. Alamat setiap catatan ditentukan dengan menggunakan algoritma hashing, yang mengubah nilai kunci utama menjadi alamat catatan. Jadi, ada dua kategori pengindeksan yang tersedia menggunakan fungsi hash - hashing dinamis dan hashing statis.

Apa itu hashing statis?

Hashing statis adalah metode hashing di mana sejumlah ember tetap dialokasikan untuk file untuk menyimpan catatan. Jumlah ember yang dialokasikan sebelumnya sehingga ketika nilai kunci pencarian disediakan, fungsi hash selalu menghitung alamat yang sama. Halaman file dapat dilihat sebagai kumpulan ember, dengan satu halaman utama dan halaman tambahan tambahan. Dengan hashing statis, mekanisme lokasi adalah fungsi hash dan tidak ada struktur data yang terlibat. Di sini, entri indeks diacak sedemikian rupa sehingga jumlah entri indeks di setiap bucket kira -kira sama. Namun, ada kerugian tertentu untuk skema ini juga. Jika jumlah awal ember terlalu kecil dan file tumbuh, kinerja menurun karena ember luapan. Di sisi lain, jika terlalu besar, banyak ruang dialokasikan untuk pertumbuhan yang diantisipasi dan sejumlah besar ruang dibuang untuk limbah.

Apa itu hashing dinamis?

Hashing dinamis, di sisi lain, adalah teknik yang digunakan untuk mengatasi keterbatasan hashing statis seperti ember overflow. Tidak seperti di hashing statis, ini memungkinkan jumlah ember untuk bervariasi secara dinamis untuk mengakomodasi pertumbuhan atau penyusutan file database. Ini memungkinkan fungsi hash untuk dimodifikasi sesuai permintaan yang baik untuk basis data yang tumbuh dan menyusut dalam ukuran. Saat baris ditambahkan dan dihapus, itu mengubah jumlah ember yang sesuai untuk meminimalkan luapan ember. Itu menanamkan penanganan catatan meluap ke ruang alamat utamanya secara dinamis untuk menghindari manajemen ember overflow. Dua bentuk hashing dinamis yang umum digunakan adalah hashing linier dan hashing yang dapat diperpanjang. Hashing yang dapat diperpanjang adalah teknik populer yang menangani ember ember dengan membagi ember menjadi dua, mendistribusikan catatan antara ember lama dan baru. Hashing linear adalah bentuk populer hashing dinamis lainnya yang memungkinkan file hash tumbuh atau menyusut secara dinamis dengan mengalokasikan ember baru.

Perbedaan antara hashing dinamis dan statis

Teknik

- Hashing statis adalah metode hashing di mana sejumlah ember tetap dialokasikan untuk file untuk menyimpan catatan yang berarti menggunakan fungsi hash di mana jumlah alamat ember diperbaiki. Di sini, entri indeks diacak sedemikian rupa sehingga jumlah entri indeks di setiap bucket kira -kira sama. Hashing dinamis, di sisi lain, memungkinkan jumlah ember bervariasi secara dinamis untuk mengakomodasi pertumbuhan atau penyusutan file database.

Pertunjukan

- Jika jumlah awal ember terlalu kecil dan file tumbuh, kinerja menurun karena ember luapan. Di sisi lain, jika terlalu besar, banyak ruang dialokasikan untuk pertumbuhan yang diantisipasi dan sejumlah besar ruang dibuang untuk limbah. Hashing dinamis, di sisi lain, memungkinkan fungsi hash untuk dimodifikasi secara dinamis yang baik untuk basis data yang tumbuh dan menyusut dalam ukuran. Saat baris ditambahkan dan dihapus, itu mengubah jumlah ember yang sesuai untuk meminimalkan luapan ember.

Penerapan

- Hashing statis menggunakan fungsi hash tetap untuk mempartisi himpunan semua nilai kunci pencarian yang mungkin ke dalam himpunan bagian, dan kemudian memetakan setiap subset ke ember. Hashing dinamis, di sisi lain, menggunakan tahap kedua pemetaan untuk menentukan ember yang terkait dengan beberapa nilai kunci pencarian. Hashing yang dapat diperpanjang dan linier melakukan pemetaan ini dengan sangat berbeda.

Dinamis vs. Hashing Statis: Bagan Perbandingan

Ringkasan

Jumlah ember ditetapkan dalam hashing statis dan catatan dengan nilai kunci pencarian yang berbeda menunjuk ke ember yang sama, dalam hal ini tabrakan dapat terjadi. Jika Anda perlu menemukan catatan tertentu dalam ember dengan beberapa tombol, Anda harus mencari seluruh bucket secara berurutan. Terkadang, ember memiliki lebih banyak catatan daripada yang dapat dikandungnya. Jadi, dalam hal ini, beberapa teknik penanganan luapan harus dipanggil. Dalam hal ini, hashing dinamis digunakan, yang menggunakan fungsi yang berubah secara dinamis yang memungkinkan jumlah ember yang dialokasikan tumbuh dan menyusut dalam ukuran saat baris ditambahkan dan dihapus. Ini secara eksplisit menangani overflow ember dengan menanamkan catatan overflow secara dinamis ke alamat utamanya.