Hashing dalam DBMS: Teknik Hashing Statis dan Dinamis
Fiona Coklat
⚡ Ringkasan Cerdas
Hashing dalam DBMS adalah teknik yang menghitung lokasi disk suatu record langsung dari kuncinya, tanpa menelusuri indeks. Fungsi hash memetakan kunci pencarian ke bucket data, dan hashing statis atau dinamis mengatur bagaimana bucket tersebut berkembang.
Apa itu Hashing di DBMS?
Dalam DBMS, hashing adalah teknik untuk langsung mencari lokasi data yang diinginkan pada disk tanpa menggunakan struktur indeks. Metode hashing digunakan untuk mengindeks dan mengambil item dalam basis data, karena lebih cepat mencari item tertentu menggunakan kunci hash yang lebih pendek daripada nilai aslinya. Data disimpan dalam bentuk blok data yang alamatnya dihasilkan dengan menerapkan fungsi hash; lokasi memori tempat catatan ini disimpan dikenal sebagai blok data atau keranjang data.
Mengapa Kita Membutuhkan Hashing?
Berikut adalah situasi-situasi dalam DBMS di mana Anda perlu menerapkan metode hashing:
- Untuk struktur basis data yang sangat besar, sulit untuk mencari semua nilai indeks melalui semua levelnya dan kemudian mencapai blok data tujuan untuk mendapatkan data yang diinginkan.
- Hashing digunakan untuk mengindeks dan mengambil item dalam basis data, karena pencarian item tertentu menggunakan kunci hash yang lebih pendek lebih cepat daripada menggunakan nilai aslinya.
- Hashing adalah metode ideal untuk menghitung lokasi langsung dari sebuah 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:
- Bucket data: Bucket data adalah lokasi memori tempat data disimpan. Ini juga dikenal sebagai unit penyimpanan.
- Kunci: a kunci DBMS adalah atribut atau sekumpulan atribut yang membantu Anda mengidentifikasi baris (tuple) dalam sebuah relasi (tabel).
- Fungsi hash: sebuah petaping Fungsi yang memetakan seluruh kumpulan kunci pencarian ke alamat tempat catatan sebenarnya berada.
- Pemeriksaan Linier: Interval tetap antara setiap pengambilan data. Dalam metode ini, blok data yang tersedia berikutnya digunakan untuk memasukkan data baru, alih-alih menimpa data yang lebih lama.
- Penyelidikan Kuadratik: Membantu menentukan alamat bucket baru dengan menambahkan keluaran berurutan dari polinomial kuadrat ke nilai awal yang diberikan oleh perhitungan asli.
- Indeks hash: Alamat blok data. Fungsi hash bisa berupa fungsi matematika sederhana atau fungsi yang kompleks.
- Double Pencirian: Metode yang digunakan dalam tabel hash untuk mengatasi benturan (collision) dengan menerapkan fungsi hash kedua.
- Ember Meluap: Kondisi kelebihan kapasitas bucket disebut tabrakan (collision). Ini adalah tahap fatal bagi fungsi hash statis apa pun.
Jenis Teknik Hashing
Pada dasarnya ada dua jenis teknik hashing dalam DBMS:
- Hashing Statis
- Hashing Dinamis
Perbedaan utama antara keduanya terletak pada apakah jumlah wadah tetap atau tidak, seperti yang akan dijelaskan pada dua bagian selanjutnya.
Hashing Statis
Dalam hashing statis, alamat bucket data yang dihasilkan akan selalu tetap sama.
Oleh karena itu, jika Anda membuat alamat untuk, misalnya, ID_Siswa = 10 menggunakan fungsi hashing mod(3), alamat keranjang yang dihasilkan akan selalu seperti itu 1Jadi Anda tidak akan melihat perubahan apa pun pada alamat bucket.
Oleh karena itu, dalam metode hashing statis, jumlah bucket data dalam memori selalu tetap konstan.
Fungsi Hash Statis
- Menyisipkan data: Saat data baru perlu dimasukkan ke dalam tabel, Anda membuat alamat untuk data tersebut menggunakan kunci hash-nya. Setelah alamat dibuat, data tersebut disimpan di lokasi tersebut.
- Mencari: Saat Anda perlu mengambil data, fungsi hash yang sama digunakan untuk mengambil alamat bucket tempat data tersebut disimpan.
- Hapus sebuah catatan: Dengan menggunakan fungsi hash, Anda pertama-tama mengambil data yang ingin Anda hapus, kemudian menghapus data tersebut dari alamat tersebut di memori.
Hashing statis selanjutnya dibagi menjadi:
- Buka hashing
- Hashing tertutup
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 linear probing.
Sebagai contoh, A2 adalah data baru yang ingin Anda masukkan. Fungsi hash menghasilkan alamat 222, tetapi alamat tersebut sudah ditempati oleh nilai lain. Karena itulah sistem mencari bucket data berikutnya, 501, dan menetapkan A2 ke dalamnya.
Hashing Tertutup
Dalam metode hashing tertutup, ketika bucket penuh, bucket baru dialokasikan untuk hash yang sama dan hasilnya dihubungkan setelah yang sebelumnya.
Hashing Dinamis
Hashing dinamis menawarkan mekanisme di mana bucket data ditambahkan dan dihapus secara dinamis dan sesuai permintaan. Dalam metode hashing ini, fungsi hash membantu Anda membuat sejumlah besar nilai, dan strukturnya tumbuh atau menyusut sesuai dengan data. Hal ini menjadikannya sangat cocok untuk tabel yang ukurannya tidak dapat diprediksi sebelumnya, di mana hashing statis akan membuang ruang atau menyebabkan kelebihan kapasitas.
Perbedaan Antara Pengindeksan Terurut dan Hashing
Berikut adalah perbedaan utama antara pengindeksan dan hashing:
| Parameter Teknis | Pengindeksan Terurut | 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 | Nilai tersebut dapat menurun seiring bertambahnya data, karena data disimpan dalam keadaan terurut dan setiap penyisipan, penghapusan, atau pembaruan akan mengubah urutannya. | Performa terbaik diperoleh dengan penambahan dan penghapusan data secara konstan. Untuk basis data yang sangat besar, pemeliharaan file hash menjadi lebih mahal. |
| Digunakan untuk | Lebih disukai untuk pengambilan rentang, di mana data diambil untuk rentang tertentu. | Ideal untuk mengambil data tertentu berdasarkan kunci pencarian, dan hanya berfungsi dengan baik jika fungsi hash diterapkan pada kunci pencarian. |
| Manajemen memori | Banyak blok data yang tidak terpakai muncul dari operasi penghapusan dan pembaruan dan tidak dapat dilepaskan untuk digunakan kembali, sehingga diperlukan pemeliharaan rutin. | Dalam hashing statis dan dinamis, memori selalu dikelola dan penanganan luapan bucket dilakukan untuk memperluas kemampuan hashing statis. |
Singkatnya, pilih yang terurut. Indeksasi untuk kueri rentang dan hashing untuk pencarian kecocokan persis pada kunci.
Apa itu Collision?
Tabrakan hash adalah suatu kondisi di mana hash hasil dari dua atau lebih item dalam kumpulan data salah dipetakan ke tempat yang sama dalam hash tersebut. tabel hash.
Cara Mengatasi Tabrakan Hashing
Ada dua teknik yang dapat Anda gunakan untuk menghindari tabrakan hash:
- Mengulang kembali: Metode ini memanggil fungsi hash sekunder, yang diterapkan terus menerus hingga ditemukan slot kosong tempat sebuah record dapat ditempatkan.
- rantai: Metode chaining membangun linked list dari item-item yang kunci hash-nya sama nilainya. Metode ini membutuhkan field link tambahan di setiap posisi tabel.
