Hashing dalam DBMS: Teknik Hashing Statis dan Dinamis
Apa itu Hashing di DBMS?
Dalam DBMS, hashing adalah teknik untuk mencari langsung lokasi data yang diinginkan pada disk tanpa menggunakan struktur indeks. Metode hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat mencari item tertentu menggunakan kunci hash yang lebih pendek daripada menggunakan nilai aslinya. Data disimpan dalam bentuk blok data yang alamatnya dihasilkan dengan menerapkan fungsi hash di lokasi memori tempat catatan tersebut disimpan yang dikenal sebagai a blok data atau keranjang data.
Mengapa kita perlu Hashing?
Berikut adalah situasi di DBMS di mana Anda perlu menerapkan metode Hashing:
- Untuk struktur database yang besar, sulit untuk mencari semua nilai indeks melalui seluruh levelnya dan kemudian Anda harus mencapai blok data tujuan untuk mendapatkan data yang diinginkan.
- Metode hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat mencari item tertentu menggunakan kunci hash yang lebih pendek daripada menggunakan nilai aslinya.
- Hashing adalah metode ideal untuk menghitung lokasi langsung dari catatan data pada disk tanpa menggunakan struktur indeks.
- Ini juga merupakan teknik yang berguna untuk mengimplementasikan kamus.
Terminologi Penting dalam Hashing
Berikut adalah terminologi penting yang digunakan dalam Hashing:
- Keranjang data – Keranjang data adalah lokasi memori tempat catatan disimpan. Ia juga dikenal sebagai Unit Penyimpanan.
- kunci: Sebuah kunci DBMS adalah atribut atau kumpulan atribut yang membantu Anda mengidentifikasi baris (tupel) dalam suatu relasi (tabel). Ini memungkinkan Anda menemukan hubungan antara dua tabel.
- Fungsi hash: Fungsi hash, adalah fungsi pemetaan yang memetakan seluruh rangkaian kunci pencarian ke alamat tempat catatan sebenarnya ditempatkan.
- Pemeriksaan Linier – Probing linier adalah interval tetap antar probe. Dalam metode ini, blok data berikutnya yang tersedia digunakan untuk memasukkan data baru, alih-alih menimpa data lama.
- Pemeriksaan kuadratik– Ini membantu Anda menentukan alamat bucket baru. Ini membantu Anda menambahkan Interval antar probe dengan menambahkan keluaran polinomial kuadrat berturut-turut ke nilai awal yang diberikan oleh perhitungan asli.
- Indeks hash – Ini adalah alamat blok data. Fungsi hash bisa berupa fungsi matematika sederhana atau bahkan fungsi matematika yang kompleks.
- Double Hashing -Double hashing adalah metode pemrograman komputer yang digunakan dalam tabel hash untuk menyelesaikan masalah tabrakan.
- Ember Melimpah: Kondisi luapan ember disebut tumbukan. Ini adalah tahap fatal agar listrik statis dapat berfungsi.
Jenis Teknik Hashing
Ada dua jenis metode/teknik hashing SQL:
- Hashing Statis
- Hashing Dinamis
Hashing statis
Dalam hashing statis, alamat keranjang data yang dihasilkan akan selalu sama.
Oleh karena itu, jika Anda membuat alamat untuk katakanlah ID_Siswa = 10 menggunakan fungsi hashing mod(3), alamat keranjang yang dihasilkan akan selalu seperti itu 1. Jadi, Anda tidak akan melihat perubahan apa pun pada alamat bucket.
Oleh karena itu, dalam metode hashing statis ini, jumlah keranjang data di memori selalu konstan.
Fungsi Hash Statis
- Memasukkan catatan: Ketika catatan baru perlu dimasukkan ke dalam tabel, Anda dapat membuat alamat untuk catatan baru menggunakan kunci hashnya. Ketika alamat dibuat, catatan secara otomatis disimpan di lokasi itu.
- Pencarian: Saat Anda perlu mengambil catatan, fungsi hash yang sama akan membantu untuk mengambil alamat keranjang tempat data harus disimpan.
- Hapus sebuah record: Dengan menggunakan fungsi hash, Anda dapat mengambil record yang ingin Anda hapus terlebih dahulu. Kemudian Anda dapat menghapus catatan untuk alamat tersebut di memori.
Hashing statis dibagi lagi menjadi
- Buka hashing
- Tutup hashing.
Buka Hashing
Dalam metode hashing terbuka, alih-alih menimpa data lama, blok data berikutnya yang tersedia digunakan untuk memasukkan data baru. Metode ini juga dikenal sebagai probing linier.
Misalnya, A2 adalah record baru yang ingin Anda sisipkan. Fungsi hash menghasilkan alamat sebagai 222. Tapi sudah ditempati oleh beberapa nilai lain. Itu sebabnya sistem mencari keranjang data 501 berikutnya dan menetapkan A2 ke dalamnya.
Tutup Hashing
Dalam metode hashing dekat, ketika keranjang penuh, keranjang baru dialokasikan untuk hash yang sama dan hasilnya ditautkan setelah yang sebelumnya.
Hashing Dinamis
Hashing dinamis menawarkan mekanisme di mana keranjang data ditambahkan dan dihapus secara dinamis dan sesuai permintaan. Dalam hashing ini, fungsi hash membantu Anda membuat nilai dalam jumlah besar.
Perbedaan antara Pengindeksan Terurut dan Hashing
Di bawah ini adalah perbedaan utama antara Pengindeksan dan Hashing
Parameters | Pengindeksan Pesanan | Hashing |
---|---|---|
Menyimpan alamat | Alamat-alamat dalam memori diurutkan berdasarkan nilai kunci yang disebut kunci utama | Alamat selalu dihasilkan menggunakan fungsi hash pada nilai kunci. |
Performance | Itu bisa berkurang ketika data dalam file hash bertambah. Karena menyimpan data dalam bentuk yang diurutkan ketika ada operasi (masukkan/hapus/perbarui) yang dilakukan yang menurunkan kinerjanya. | Kinerja hashing akan menjadi yang terbaik bila ada penambahan dan penghapusan data secara konstan. Namun, ketika database berukuran besar, maka pengorganisasian file hash dan pemeliharaannya akan lebih mahal. |
Digunakan untuk | Lebih disukai untuk pengambilan data dalam rentang tertentu - yang berarti setiap kali ada pengambilan data untuk rentang tertentu, metode ini adalah pilihan ideal. | Ini adalah metode yang ideal ketika Anda ingin mengambil catatan tertentu berdasarkan kunci pencarian. Namun, ini hanya akan bekerja dengan baik jika fungsi hash ada pada tombol pencarian. |
Manajemen memori | Akan ada banyak blok data yang tidak terpakai karena operasi penghapusan/pembaruan. Blok data ini tidak dapat dilepaskan untuk digunakan kembali. Oleh karena itu diperlukan pemeliharaan memori secara berkala. | Dalam metode hashing statis dan dinamis, memori selalu dikelola. Bucket overflow juga ditangani dengan sempurna untuk memperluas hashing statis. |
Apa itu Collision?
Tabrakan hash adalah keadaan ketika hash yang dihasilkan dari dua atau lebih data dalam kumpulan data salah memetakan tempat yang sama di kumpulan data. tabel hash.
Bagaimana cara mengatasi Tabrakan Hashing?
Ada dua teknik yang dapat Anda gunakan untuk menghindari tabrakan hash:
- mengulang: Metode ini memanggil fungsi hash sekunder, yang diterapkan terus menerus hingga slot kosong ditemukan, di mana catatan harus ditempatkan.
- Rantai: Metode rangkaian membuat daftar item Tertaut yang kuncinya di-hash ke nilai yang sama. Metode ini memerlukan kolom tautan tambahan ke setiap posisi tabel.
Kesimpulan
- In DBMS, hashing adalah teknik untuk mencari langsung lokasi data yang diinginkan pada disk tanpa menggunakan struktur indeks.
- Metode hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat mencari item tertentu menggunakan kunci hash yang lebih pendek daripada menggunakan nilai aslinya.
- Keranjang data, Kunci, Fungsi Hash, Pemeriksaan Linier, Pemeriksaan Kuadrat, Indeks Hash, Double Hashing, Bucket Overflow adalah terminologi penting yang digunakan dalam hashing
- Dua jenis metode hashing adalah 1) hashing statis 2) hashing dinamis
- Dalam hashing statis, alamat keranjang data yang dihasilkan akan selalu sama.
- Hashing dinamis menawarkan mekanisme di mana keranjang data ditambahkan dan dihapus secara dinamis dan sesuai permintaan.
- Agar pengindeksan alamat di memori diurutkan berdasarkan nilai kritis sedangkan dalam hashing alamat selalu dihasilkan menggunakan fungsi hash pada nilai kunci.
- Tabrakan hash adalah keadaan ketika hash yang dihasilkan dari dua atau lebih data dalam kumpulan data salah memetakan tempat yang sama dalam tabel hash.
- Rehashing dan chaining adalah dua metode yang membantu Anda menghindari tabrakan hashing.