📋 Daftar Isi
Fungsi Hash memetakan elemen pada indeks array dari
hash table harus mempunyai sifat berikut:
- Mudah dihitung
- Dua key yang berbeda akan dipetakan pada dua sel yang berbeda pada array
Meminimalkan Collision (kondisi di mana nilai data yang berbeda mendapatkan nilai hashing atau posisi pada hash table yang sama). Membagi key secara rata pada seluruh sel.
Hash Function: Trucation
Sebagian dari key dapat dibuang/diabaikan, bagian key sisanya digabungkan untuk membentuk index. Contoh:
Cepat, tetapi sering gagal untuk membagi key secara merata pada seluruh index array
Hash Function: Folding
Data dipecah menjadi beberapa bagian, kemudian tiap bagian tersebut digabungkan lagi dalam bentuk lain. Contoh:
Penyebaran index hash table lebih baik daripada truncation
Hash Function: Modular Arithmetic
Melakukan konversi data ke bentuk bilangan bulat, dibagi dengan ukuran hash table, dan mengambil hasil sisa baginya sebagai indeks. Contoh: Ukuran hash table = 100
Metode paling baik karena memberikan penyebaran index yang baik dan dapat memastikan berada di interval tertentu.
Bagaimana Hash Function untuk String?
Konversi non integer key ke nilai integer, kemudian gunakan hash function untuk memetakannya ke index hash table.
(
Contoh:
Misalkan string = HAI. Ambbil nilai ASCII dari masing-masing huruf (H,A,I). Kemudian petakan menggunakan hash function, misal:
H = 72 % 6 = 0
A = 65 % 6 = 5
I = 73 % 6 = 1
72, 65 dan 73 merupakan integer key sedangkan 0,5,1 adalah index array
Contoh Pemetaan Key
Bagaimana pemetaan key berikut ke index array hash table?
- Hash (x) = x mod 10, Key : 45, 72, 39, 48, 56, 77, 91, 63, 84, 90
- Hash (x) = x mod 6, Key : 45, 72, 40, 49, 14
Materi Lengkap
Silakan baca juga beberapa artikel menarik kami tentang Heap dan Hash, daftar lengkapnya adalah sebagai berikut.
