HASHING
Hashing
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Tujuan hashing adalah sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan datam dan penghapusan data dapat dilakukan dengan cepat.
Hash Table
Hash table adalah salah satu struktur data yang digunakan dalam penyimpanan data sementara. Hash table menggunakan memori penyimpanan utama berbentyj array dengan tambahan algoritma untuk mempercepat pemrosesan data.
Hash Function
Hash Function adalah suatu fungsi sederhana untuk mendaoatkan nilai hash dari nilai kunci(key value) suatu data.
Ada beberapa hal dalam membuat hash function antara lain :
· Ukuran array/ table size (m)
· Key value/ nilai yang di dapat dari data (k)
· Hash value/ hash index/index yang dituju (h)
Beberapa metode pentuk untuk membangun hash functions antara lain:
- Mid – square
- Division (most common)
- Folding
- Digit Extraction
- Rotating Hash
Mid – square
Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus. Jika terjadi overflow, gunakan tipe data int panjang atau gunakan string sebagai perkalian jika luapan masih terjadi. Kemungkinan tabrakan di tengah-tengah hashing rendah, tidak usang. Jadi, dalam peluang, jika tabrakan terjadi, itu ditangani menggunakan beberapa peta hash.
Contoh:
Nilai
|
Di kuadratkan
|
Nilai di ekstraksi
|
4765
|
22705225
|
7052
|
3725
|
13875625
|
8756
|
Algoritma dalam mid – square
- Pilih nilai seed. Ini adalah langkah penting karena untuk nilai seed yang sama, urutan nomor acak yang sama dihasilkan.
- Ambil kuadrat dari nilai seed dan perbarui seed dengan jumlah digit tertentu yang terjadi di square. Catatan: Semakin besar jumlah digit, semakin besar keacakannya.
- Kembalikan kuncinya.
Division
Jumlah lokasi memori tersedia dihitung , kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa(nilai hashnya).
Secara umum rumus division sebagai berikut :
h(z) = z mod M
Keterangan:
z = key/ suatu lokasi memori yang beralamat h(z)
M = jumlah lokasi memori yang tersedia pada array
Contoh:
Ukuran table = 97
COBB
Abjad
|
Nilai ASCII
|
C
|
67
|
O
|
79
|
B
|
66
|
B
|
66
|
total
|
278
|
H(z) = 278 mod 97 = 84
HIKE
Abjad
|
Nilai ASCII
|
H
|
72
|
I
|
73
|
K
|
75
|
E
|
69
|
total
|
289
|
H(z) = 289 mod 97 = 95
ABCD
Abjad
|
Nilai ASCII
|
A
|
65
|
B
|
66
|
C
|
67
|
D
|
68
|
total
|
266
|
H(z) = 278 mod 97 = 72
Folding
Metode lipat berfungsi dalam 2 langkah :
- Bagi nilai kunci menjadi beberapa bagian dimana setiap bagian memiliki jumlah digit yang sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lainnya.
- Tambahan bagi individu. Yaitu memperoleh jumlah part 1 + part + .. + part n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.
Contoh:
Key = 6632
Parts = 66 dan 32
Jumlah = 98
Hash value = 98
Digit Extraction
Mendapatkan hash key dengan cara mengambil digit – digit tertentu dari sebuah string
untuk dijadikan hash keynya.
Contoh: terdapat string yaitu 14568, jika kita mengambil digit 1, digit 3, dan digit 5 maka
hash keynya adalah 158.
Rotating Hash
Mendapatkan hash key maka di lakukan rotasi untuk menggeser digit sehingga
menemukan alamat hash key baru.
Contoh :
Hash key = 3456
Hasil rotasi = 6543
Collision
Ada 2 cara untuk menangani collision :
· Linear Probing
Mencari slot kosong berikutnya dan letakkan string disana.
Code :
void linear_probing(item, h[]) {
hash_key = hash(item);
i = has_key;
while ( strlen(h[i] != 0 ) {
if ( strcmp(h[i], item) == 0 ) {
// DUPLICATE ENTRY
}
}
i = (i + 1) % TABLE_SIZE;
if ( i == hash_key ) {
// TABLE IS FULL
}
}
}
}
h[i] = item;
}
}
· Chaining
Masukkan string ke dalam slot sebagai chained list(linked list).
Code:
void chaining(item, h[]) {
hash_key = hash(item);
trail = NULL, lead = h[hash_key];
while ( lead ) {
if ( strcmp(lead->item, item) == 0 ) { // DUPLICATE ENTRY }
trail = lead; lead = lead->next;
}
}
p = malloc new node;
p->item = item;
p->next = NULL;
if ( trail == 0 ) h[hash_key] = p; else trail->next = p;
Komentar
Posting Komentar