struktur data (hashing)

22
STRUKTUR DATA (HASHING)

Upload: wauna

Post on 15-Jan-2016

203 views

Category:

Documents


34 download

DESCRIPTION

STRUKTUR DATA (HASHING). Metode Hashing. Untuk mengatasi kerugian korespondensi satu-satu, digunakan hashing Untuk mengurangi banyaknya ruang alamat yang digunakan untuk pemetaan dari key yang memiliki cakupan yang luas ke nilai alamat yang memiliki cakupan yang dipersempit - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: STRUKTUR DATA (HASHING)

STRUKTUR DATA

(HASHING)

Page 2: STRUKTUR DATA (HASHING)

Metode Hashing

• Untuk mengatasi kerugian korespondensi satu-satu, digunakan hashing

• Untuk mengurangi banyaknya ruang alamat yang digunakan untuk pemetaan dari key yang memiliki cakupan yang luas ke nilai alamat yang memiliki cakupan yang dipersempit

• Untuk itu dibutuhkan fungsi HASH• Output fungsi HASH adalah home address dari

record yang keynya diproses• Fungsi : f(key) = address

Page 3: STRUKTUR DATA (HASHING)

Macam-macam Fungsi HASH

• Fungsi modulo• Home address dicari dengan cara

mencari sisa hasil bagi nilai key dengan suatu nilai tertentu.

• Fungsi: f(key) = key mod n• Dengan n adalah:

• Banyaknya ruang alamat yang tersedia• Atau bilangan prima terdekat yang berada di

atas nilai banyak data, setelah itu banyaknya ruang alamat disesuaikan dengan n

Page 4: STRUKTUR DATA (HASHING)

Macam-macam Fungsi HASH

• Fungsi Pemotongan• Home address dicari dengan memotong nilai key

ke jumlah digit tertentu yang lebih pendek.• Contoh: NIM yang tadinya 8 digit, dipotong hanya

menjadi 2 digit!• Fungsi Pelipatan

• Dilakukan pelipatan terhadap record key dengan bagian yang sama panjang, lalu setiap bagian dijumlahkan

• NIM 8 digit dibagi dua digit, hingga menjadi 4 buah.

• Misal: 22002521, dibagi 22 00 25 21 kemudian dijumlahkan: 68

Page 5: STRUKTUR DATA (HASHING)

Macam-macam Fungsi HASH

• Fungsi Pengkuadratan• Home address dicari dengan mengkuadratkan

setiap digit pembentuk key, lalu semua hasilnya dijumlahkan

• Contoh: 22002211, semua digit dikuadratkan dan dijumlah

• Fungsi Penambahan Kode ASCII• Jika key bukan kode numerik, home address

dicari dengan menjumlahkan kode ASCII setiap huruf pembentuk key

• ADE = 65 + 68 + 69 = 192

Page 6: STRUKTUR DATA (HASHING)

Collision (Tabrakan)

• Dengan menggunakan hashing, maka hubungan korespondensi satu-satu antara record key dengan alamat record akan hilang

• Selalu ada kemungkinan dimana terdapat dua buah record dengan key yang berbeda namun memiliki home address yang sama = tabrakan

Page 7: STRUKTUR DATA (HASHING)

Kriteria Fungsi HASH yang baik

• Dapat mendistribusikan setiap record secara merata, sehingga dapat meminimalkan terjadinya tabrakan

• Dapat dieksekusi secara efisien sehingga waktu tidak habis untuk menghitung home address nya saja

Page 8: STRUKTUR DATA (HASHING)

Collision Resolution

• Karena collision dapat dipastikan akan dapat terjadi, maka output dari suatu fungsi hash tidak selalu unik, namun hanya berupa kemungkinan suatu alamat yang dapat ditempati

• Jika suatu home address sudah ditempati oleh record lain, maka harus dicarikan alamat lain

• Proses pencarian alamat lain tersebut disebut collision resolution

Page 9: STRUKTUR DATA (HASHING)

Metode Collision Resolution

• Open Addressing• Chaining• Coalesced Hashing• Chained Progressive Overflow• Bucket

Page 10: STRUKTUR DATA (HASHING)

Metode Open Addressing

• Alamat alternatif dicari pada alamat-alamat selanjutnya yang masih kosong

• Cara:• Linear Probing

• Pencarian dilakukan dengan jarak pencarian tetap• Quardratic Probing

• Pencarian dilakukan dengan jarak pencarian berubah dengan perubahan tetap

• Double Hashing• Pencarian dilakukan menggunakan fungsi hash kedua.

Pertama hash untuk mencari home address, kedua untuk pencarian jika terjadi collision. Fungsi hash kedua tidak boleh menghasilkan nilai 0

Page 11: STRUKTUR DATA (HASHING)

HASHING

• Fungsi hash diimplementasikan untuk menyimpan kode yang cukup besar ke dalam indeks yang lebih kecil sehingga mempercepat pencarian.contoh :

Posisi (indeks) Kode buku

0 1023000

101 4321101

772 1002772

773 7671773

• Tujuan penggunaan fungsi hash adalah agar 2 buah kunci yang berbeda tidak mempunyai nilai hash yang sama (untuk menghindari colllision/hash clash)

Page 12: STRUKTUR DATA (HASHING)

METODA HASHING

• Dalam implementasi fungsi hash sering digunakan untuk mengkonversikan himpunan kunci rekaman menjadi himpunan alamat memori (subskrip dalam array)

• Aspek yang perlu dipertimbangkan dalam pemilihan fungsi hash adalah :

a. Fungsi hash harus mudah dan cepat dihitung

b. Fungsi hash sebisa mungkin mendistribusikan posisi yang dimaksud

Page 13: STRUKTUR DATA (HASHING)

Home address dicari dengan cara mencari sisa hasil bagi nilai key dengan suatu nilai tertentu.Fungsi: f(key) = key mod nDengan n adalah:

Banyaknya ruang alamat yang tersediaAtau bilangan prima terdekat yang berada di atas nilai banyak data, setelah itu banyaknya ruang alamat disesuaikan dengan n

Hashing dengan Kunci Modulus N

Page 14: STRUKTUR DATA (HASHING)

Hashing dengan Kunci Modulus N

f (kunci) = kunci mod N

N = ukuran tabel atau berkas

Page 15: STRUKTUR DATA (HASHING)

N = 12

30 mod N = 6 menghasilkan 2 sisa 640 mod N = 4 menghasilkan 3 sisa 450 mod N = 2 menghasilkan 4 sisa 260 mod N = 0 menghasilkan 5 sisa 0

Page 16: STRUKTUR DATA (HASHING)

Kunci mod P merupakan variasi fungsi kunci mod N

Hashing dengan Kunci Modulus P

P = sebagai bilangan prima terkecil

yang lebih besar atau sama dengan N

f (kunci) = kunci mod P

Page 17: STRUKTUR DATA (HASHING)

Untuk N = 12 maka P = 1330 mod P = 4 menghasilkan 2 sisa 440 mod P = 1 menghasilkan 3 sisa 1

Untuk N = 15 maka P = 1750 mod P = 16 menghasilkan 2 sisa

1670 mod P = 2 menghasilkan 4 sisa 2

Page 18: STRUKTUR DATA (HASHING)

Hashing dengan pengkuadratan

Fungsi hashing dengan cara pengkuadratan kunci

Carilah pengkuadratan dari 782Jawab F (782) =

Page 19: STRUKTUR DATA (HASHING)

Hashing dengan konversi Radix

Kunci 5 6 7 8 dalam Base 13

Page 20: STRUKTUR DATA (HASHING)

Hashing Lipatan

Page 21: STRUKTUR DATA (HASHING)

Penjumlahan dari susunan lipatan

385976 Mengabaikan carry421672

Page 22: STRUKTUR DATA (HASHING)

385976 Dengan carry421782