Methode Hash

  • Published on
    15-Jan-2016

  • View
    52

  • Download
    0

Embed Size (px)

DESCRIPTION

Methode Hash. Hasing. Kalkulasi terhadap nilai key untuk mendapatkan sebuah alamat disebut fungsi hash. Keuntungan: Nilai key yang sebenarnya dapat dipakai karena diterjemahkan kedalam sebuah alamat. - PowerPoint PPT Presentation

Transcript

  • Methode Hash

  • HasingKalkulasi terhadap nilai key untuk mendapatkan sebuah alamat disebut fungsi hash.Keuntungan:Nilai key yang sebenarnya dapat dipakai karena diterjemahkan kedalam sebuah alamat.Nilai key adalah address space independent bila berkas direorganisasi, fungsi hash berubah tetapi nilai key tetap.Kelemahan :Membutuhkan waktu proses dalam mengimplementasikan fungsi hash.Membutuhkan waktu proses dan akses I/O dalam mengatasi benturan.Jelaslah bahwa tujuan utama dari fungsi hash adalah mengurangi benturan. Kumpulan dari synonim kadang disebut KELAS EKIVALEN. Fungsi hash yg baik adalah mempunyai kelas ekivalen yg kecil dan mempunyai kalkulasi sederhana

  • Penampilan fungsi hash bergantung pada :Distribusi nilai key yang dipakaiBanyaknya nilai key yang dipakai relatif terhadap ukuran dari ruang alamat.Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebabkan benturan.Teknik yang dipakai untuk mengatasi benturan

  • Beberapa fungsi hash yang umum digunakan :

    1. Division RemainderAlamat relatif dari suatu nilai key merupakan sisa dari hasil pembagian nilai key tersebut dengan suatu bilangan yang disebut sebagai bilangan pembagi.Banyak faktor yang harus dipertimbangkan dalam pemilihan pembagi :Jangkauan dari nilai key yang dihasilkan dari opersi KEY MOD DIV adalah 0 sampai DIV-1. Pembagi harus diseleksi untuk mengurangi benturan. Menurut riset dari W.Buchholz, sebaiknya pembagi itu merupakan bilangan prima. Bukan bilangan prima yang mempunyai faktor prima kurang dari 20 akan dapat memberikan jaminan penampilan yang lebih baik.Walaupun telah ditentukan pembagi dengan baik untuk mengatasi benturan, bila ruang alamat dari berkas relatif mendekati penuh, maka peluang terjadinya benturan akan meningkat.

  • Untuk mengukur kepenuhan berkas relatif digunakan Load Factor (Faktor Muat). Load Factor = banyak record dalam berkas

    max. banyak record dalam berkasSemua fungsi Hash mulai bekerja buruk, bila berkas hampir penuh. Jika faktor muat lebih besar dari 0,7 atau 0,8, maka berkas tersebut harus diperbesar dan direorganisir. Karena itu, jika berkas berisi relatif N record, maka ruang alamat harus mempunyai paling sedikit 0,25 N record Untuk faktor muat 0,8)Contoh : Sebuah berkas relatif yang berisi 4000 record, paling sedikit harus mempunyai ruang alamat untuk 5000 record (faktor muat 0,8). Angka yang dekat dengan 5000 dan terdiri dari faktor prima kurang dari 20 adalah angka 5003. Angka ini dipakai sebagai pembagi.Alamat relatif didapat dari sisa pembagian + 1

  • Perbandingan fungsi HashTeknik Division Remainder memberikan penampilan yang terbaik secara keseluruhan.Teknik Mid Square dapat dipakai untuk file dengan load factor cukup rendah akan memberikan penampilan baik tetapi kadang-kadang dapat menghasilkan penampilan yang buruk dengan beberapa collision.Teknik folding adalah teknik yang paling mudah dalam perhitungan tetapi dapat memberikan hasil yang salah, kecuali panjang nilai key = panjang address.

  • Pendekatan terhadap masalah CollisionAda 2 teknik yang digunakan untuk mengatasi collision yaitu:Liear Probing yang merupakan teknik open addressing Agar linear probing dapat dilaksanakan, harus ada penentu apakah address kosong. Ini dapat dilakukan dengan memberi panji (flag) bahwa lokasi tersebut telah penuh setelah record disimpan. Lokasi dasar penyimpanan dengan teknik linear probing dapat dilihat pada gambar berikut:

  • 2. Double HasingYang memakai fungsi hash kedua terhadap hasil dari fungsi hash pertama. Address dari record yang di-hash kembali dapat terletak di primary area atau di Separate Overflow AreaKeuntungan dari metode Separate Overflow adalah menghindari keadan di mana dapat terjadi metode Open Addressing untuk sebuah record yang tidak dapat disimpan dalam home address-nya menggantikan record lain yang terakhir di hash oleh home address-nya.

  • Synonim ChainingPendekatan pemecahan collision yang mengakses synonim dengan fasilitas link list untuk record-recordnya dalam kelas ekivalen. Adapun link list record-record dengan home address yang sama tak akan mengurangi jumlah collision, tetapi akan mengurangi waktu akses untuk me-retrieve record-record yang tak ada di home addressnya.Contoh : KEY HOME ADDRESS ACTUAL ADDRESS Adams20 20 Bates21 21 Coll20 22 Dean21 23 Evans24 24 Flint20 25

    R20 R21 R22 R23 R24 R25 .. Adams .. Bates .. Coll .. Dean .. Evans .. Flint .. ...

    gambar hashing dengan synonim chaining

  • HOME PRIMARY DATA OVERFLOWADDRESS AREA AREA 20Adams .. 0 Coll .. 21Bates .. 1 Dean .. 22 2 Flint .. 23 3 24Evans ..

  • metode hash dinamis, kunci yang telah masuk dapat digeser oleh kunci yang masuk belakanganmenggunakan link (double table), link berupa NOF :number of offsetNOF merupakan jumlah perpindahan dengan incremen tertentu

  • AlgoritmaKonversikan kunci dengan fungsi yang ditentukan Jika collision : cek apakah kunci yang menempati adalah pemilik HA, jika bukan maka lakukan (i), jika ya lakukan langkah (ii)pindahkan kunci tersebut dan linknya dgn incremen kunci yang dipakai sebelumnyacek apakah apakah ada link, jika ya hitung link = index + (incremen(index) * NOF))

  • tentukan probe address dgn nilai incremen kunci yg menempati Home Address (HA) atau link terakhir dari HAhitung nilai NOF,jumlah perpindahan kunci dari HA atau link terakhir HA sampai alamat kucni ditempatkan, dan letakan pada link di HA atau link terakhir HA

  • CatatanKunci yang mengalami collision ditempatkan pada alamat yang dicari dgn incremen kunci yg menempati HA atau link terakhir dari HAKunci yg menempati bukan pada HA-nya akan digeser oleh pemilik HANilai NOF dihitung berdasarkan jumlah perpindahan kunci dgn incremen yg ditentukan dan nilai NOF diletakan pd HA atau link terakhir dari HA

  • Macam-macam HashHashing dengan kunci Modulud NHashing dengan kunci Modulud PHashing dengan LipatanHashing dengan pengkuadratanHashing dengan konversi radix

  • Hashing dengan kunci Modulud N

    Satu fungsi hash yang paling popular yang mempunyai keuntungan yaitu menghasilkan nilai dalam rentang ruang alamat (0) sampai dengan (N-1), di implementasikan dengan N, dimana N adalah ukuran tabel atau berkas. Hasil fungsi modulus adalah sisa pembagian kunci oleh N

    F (kunci) = kunci mod N

  • Contoh :

    Ada kunci 30 dan 40, dimana N = 12

    Maka :

    30 mod N = 6, didapat dari 30 dibagi 12 hasilnya 2 dengan sisa 640 mod N = 4, didapat dari 40 dibagi 12 hasilnya 3 dengan sisa 4

  • Hashing dengan kunci Modulud P

    Fungsi ini merupakan variasi fungsi kunci modulus N,

    F (kunci) = kunci mod P

    Dengan P sebagai bilangan prima terkecil yang lebih besar atau sama dengan N, dan N adalah ukuran tabel. P ini menjadi ukuran tabel baru yang menggantikan N

  • Contoh :

    Ada kunci 30 dan 40, dengan N = 12, maka P = 13

    30 mod P = 4, didapat dari 30 dibagi 13 hasilnya 2 sisa 4

    40 mod P = 1, didapat dari 40 dibagi 13 hasilnya 3 sisa 1

  • Hashing dengan lipatan

    Fungsi ini akan melipat digit pada batasan yang ditentukan berdasarkan kondisi digit awal dan digit yang akan dihasilkan.Contoh : ada kunci 9 digit 589 976 124

    Selanjutnya akan kita lipat mengikuti lipatan kertas

  • 9 7 6

  • Penjumlahan dari susunan yang telah dibuat

    Mengabaikan Carrymenggunakan Carry

  • Hashing dengan pengkuadratan

    Hashing ini cara kerjanya adalah mengkuadratkan kunci. Hasil pengkuadratan kemudian dapat dikombinasikan dengan pemotongan atau lipatan untuk mendapatkan alamat yang diijinkan.Contoh :Pengkuadratan kunci 782

  • Hashing dengan konversi Radix

    Dalam konversi radix, kunci dianggap dalam base selain 10, yang kemudian di konversi ke dalam basis 10.Contoh = ada kunci 5 6 7 8 dalam base 13

    Posisi :3210 5678