Hashing, Hash Table, Fungsi Hash, COLLISION Merupakan satu kesatuan dalam pembahasan HASHING Pada Struktur Data. Untuk pengertian Hashing bisa sobat lihat pada Progam Hashing After inserting, deleting, & appending Struktur Data yang telah kita bahas pada artikel sebelumnya. Oke berikut ini
Latihan Soal HASHING Hash Table, Fungsi Hash Struktur Data
1. Jelaskan definisi Hash Table dan Struktur Hash table secara lengkap?Jawaban HASHING Hash Table, Fungsi Hash Struktur Data
2. Sebutkan keunggulan struktur Hash Table dibandingkan dengan struktur table biasa? Jelaskan !
3. Buatlah ilustrasi gambar yang menunjukkan struktur Hash Table dengan menggunakan link list? Beserta penjelasannya!
4. Sebutkan beberapa metode yang digunakan Hash Table? Jelaskan masing-masing metode tersebut?
5. Buat contoh program dengan menggunakan Hash Table?
1. Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.
2. Kelebihan dari hash table antara lain sebagai berikut:
- Hash table relatif lebih cepat
- Kecepatan dalam insertions, deletions, maupun searching relatif sama
3. Gambar yang menunjukkan struktur Hash Table dengan menggunakan link list:
4. Metode-metode Hash Table yang sering digunakan adalah:
1. Linear probing5. Contoh Program Menggunakan Hash Table => Program Menggunakan Hash Table Struktur Data
Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus
(h+1) mod m.
2. Quadratic probing / squared probing
Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat menentukan sendiri formula yang akan digunakan.
Contoh formula quadratic probing untuk mencari alamat baru:
h,(h+i2)mod m,(h-i2)mod m, … ,(h+((m-1)/2)2)mod m, (h-((m-1)/2)2)mod m
dengan i = 1,2,3,4, … , ((m-1)/2)
Mksud formula di atas adalah jika alamat h telah terisi, maka alamat lain yang digunakan adalah (h+1)mod m, jika telah terisi gunakan alamat (h-1)mod m, jika telah terisi gunakan alamat (h+4)mod m, jika telah terisi gunakan alamat (h-4)mod m, dan seterusnya.
Jadi jika m=23,maka nilai maksimal i adalah : ((23-1)/2)=11.
3. Double hashing
Sesuai dengan namanya, alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh hash function awal telah terisi tentu saja berbeda dengan hash function awal itu sendiri.
Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.
•> Metode-metode lain
Selain metode-metode yang sudah disebutkan di atas, ada juga beberapa metode lain diantaranya :
1. Coalesced hashing
Gabungan dari chaining dan openaddressing. Coalesced hashing menghubungkan ke tabel itu sendiri. Seperti open addressing, metode ini memiliki keunggulan pada penggunaan tempat dan cache dibanding metode chaining. Seperti chaining, metode ini menghasilkan lokasi penyimpanan yang lebih menyebar, tetapi pada metode ini record yang disimpan tidak mungkin lebih banyak daripada ruang yang disediakan tabel.
2. Perfect hashing
Jika record yang akan digunakan sudah diketahui sebelumnya, dan jumlahnya tidak melebihi jumlah ruang pada tabel hash, perfect hashing bisa digunakan untuk membuat tabel hash yang sempurna, tanpa ada bentrokan.
3. Probabilistic hashing
Kemungkinan solusi paling sederhana untuk mengatasi bentrokan adalah dengan mengganti record yang sudah disimpan dengan record yang baru, atau membuang record yang baru akan dimasukkan. Hal ini bisa berdampak tidak ditemukannya record pada saat pencarian. Metode ini digunakan untuk keperluan tertentu saja.
4. Robin Hood hashing
Salah satu variasi dari resolusi bentrokan double hashing. Ide dasarnya adalah sebuahrecord yang sudah dimasukkan bisa digantikan dengan record yang baru jika nilai pencariannya (probe count – bertambah setiap menemukan termpat yang sudah terisi) lebih besar daripada nilai pencarian dari record yang sudah dimasukkan. Efeknya adalah mengurangi kasus terburuk waktu yang diperlukan untuk pencarian.
