Selasa, 21 Juni 2016

Manajemen Kolisi & Collision Resolution

Firman Giri Febriyanto 06.46 Tidak ada komentar :
Manajemen Kolisi & Collision Resolution


 Kriteria Fungsi Hash Yang Baik
  • Dapat mendistribusikan setiap rekaman secara merata, sehingga dapat meminimalkan terjadinya collision (tabrakan)
  • Dapat dieksekusi secara efisien, sehingga waktu tidak habis hanya untuk menghitung home address saja

Collision (Tabrakan)
  • Dengan menggunakan metode hashing, maka secara otomatis hubungan korespondensi satu-satu antara kunci rekaman dengan alamat rekaman menjadi hilang
  • Selalu ada kemungkinan terjadinya peristiwa dimana terdapat dua buah kunci yang berbeda namun memiliki home address yang sama
  • Kejadian seperti ini dinamakan Collision atau Tabrakan atau Tumbukan

Manajemen Kolisi
  • Semakin sedikit jumlah kolisi, maka makin baik bagi fungsi hashing tersebut, karena makin sedikit jumlah waktu yang diperlukan untuk melihat tempat yang berbeda dalam menemukan rekaman yang diinginkan.
  • Beberapa cara untuk mengantisipasi kolisi adalah dengan mengganti fungsi hashing, atau mengkombinasikan faktor packing.
  • Faktor packing suatu berkas adalah perbandingan (rasio) antara jumlah rekaman yang disimpan dalam berkas dengan kapasitas berkas, atau dapat dinyatakan sbb :
    Factor Packing = Jumlah Rekaman Yang Disimpan
                    Jumlah Total Lokasi Penyimpanan
Resolusi Kolisi
  • Yang menjadi tujuan utama metode resolusi adalah menempatkan rekaman synonim pada suatu lokasi yang membutuhkan probes tambahan yang minimum pada home address rekaman tersebut. Synonim adalah dua atau lebih nilai key yang berbeda pada   hash ke home address yang sama
  • Salah satu penyelesaian yang dapat dilakukan adalah dengan memberikan petunjuk pada lokasi rekaman sinonim.
  • Karena collision dapat di pastikan akan selalu terjadi, maka dapat dikatan bahwa output dari fungsi hash (home-address) bukanlah merupakan alat yang unik yang pasti ditempati oleh rekaman yang diproses, namun hanya berupa kemungkinan alamat yang bisa ditempati
  • Jika home-addrees dari suatu rekaman ternyata sudah ditempati rekaman lain, maka harus di carikan alamat lain untuk ditempati oleh rekaman tersebut
  • Proses pencarian alamat lain ini dinamakan sebagai Collision Resolution.

Berikut beberapa Metode Untuk Mengatasi Kolisi / Tubrukan :
1. Metode Open Addressing
  • Alamat alternatif dicari pada alamat-alamat selanjutnya yang masih kosong, salah satu nya dengan cara Linier Probing
  • Linier Probing :Pencarian dilakukan dengan jararak pencarian yang fix (tetap), biasanya satu-satu
  • Linier Probing Contoh : Sesuai dengan namanya jika lokasi yang telah ditempati telah terisi, maka dilihat lokasi selanjutnya apakah masih belum terisi
  • Fungsi Hash yang dipakai adalah : f(key) = key mod 10
  • Ruang alamat yang tersedia : 10 alamat
  • Metode collision resolution yang dipakai adalah open addressing dengan linier probing jarak 3
  • Urutan kunci yang masuk adalah 20, 31, 33, 40, 10, 12, 30, dan 15 
     2. Metode Coalesced Hashing
    • Bila terjadi tumbukan dalam pemasukan kunci rekaman maka dapat dicari alamat yang paling besar / paling akhir
    • Contoh : misalkan akan dilakukan penyisipan rekaman-rekaman dengan kunci 38, 51, 40, 61, 83, 24, dan 60
    • Langkah 1 lakukan proses hashing semua kunci dengan kunci modulus 11 (11 adalah kapasitas berkas), maka dihasilkan :

sumber : slide bu dine


Organisasi Berkas Secara Langsung & Metode Hashing

Firman Giri Febriyanto 06.30 Tidak ada komentar :

Organisasi Berkas Secara Langsung & Metode Hashing


Organisasi Berkas Langsung
  • Organisasi berkas langsung digunakan untuk menemukan suatu rekaman tidak melalui proses pencarian, namun bisa langsung menuju alamat yang ditempati oleh rekaman.
  • Hal ini digunakan dengan cara menyimpan rekaman pada alamat yang sama dengan nilai kunci rekaman tersebut
  • Contoh : Rekaman dengan kunci 50 akan di simpan pada alamat 50
  • Sehingga untuk menemukan sebuah rekaman cukup melihat nilai kunci dan menuju kealamat yang ditunjuk oleh kunci rekaman tersebut, contoh jika ingin melihat rekaman dengan kunci 28 langsung saja menuju alamat 28 tersebut.
  • Harus tersedia 1 ruang untuk setiap kemungkinan penyimpanan kunci rekaman, meskipun dalam rekaman tersebut data nya sudah tidak ada.
  • Contoh dalam suatu universitas yang memiliki ribuan mahasiswa pasti ada bebera nomor yang kosong untuk beberapa alasan, misalnya sudah lulus, mengundurkan diri, DO, Cuti, dsb
  • SEHINGGA TIDAK SEMUA RUANG DIMANFAATKAN UNTUK MAHASISWA AKTIF

Korespondensi Satu-Satu
  • Dengan menerjemahkan langsung dari kunci rekaman kealamat rekaman, maka akan berlaku suatu hubungan korespondensi satu-satu antara kunci dengan alamat rekaman.
  • Hal ini menyebabkan harus disediakannya ruang yang sangat besar untuk menampung stiap kemungkinan nilai kunci yang ada.
  • Contohnya : untuk menyimpan data karyawan yang kuncinya adalah NIP (Terdiri dari 9 digit) dibutuhkan sebanyak satu milyar alamat, karena kemungkinan yang dapat muncul dari kode 9 digit adalah mulai dari angka 000000000 hingga 999999999
Kerugian korespondensi Satu-Satu
  • Korespondensi satu-satu ini akan mengakibatkan pemborosan ruang penyimpanan atau terjadi banyak alamat yang tidak dipergunakan alias kosong.
  • Contoh : Kode NIP yang diawali dengan tiga digit kode departemen, yang tidak mungkin ada kode departemen 000. sehingga alamat 000000000 sampai dengan 999999999 (sebayak sejuata alamat) tidak akan terpakai karena tidak ada rekaman dengan NIP dianatar range tersebut.

Metode Hashing
  • Untuk mengatasi kerugian yang timbuldari cara korespondensi satu-satu tersebut, amak digunakan metode lain yang disebut dengan metode hashing.
  • Metode hashing pada intinya digunakan untuk melakukan pemetaan (melakukan konversi) dari kunci rekaman yang memiliki cakupan nilai yang luas ke nilai alamat yang memiliki cakupan yang lebih sempit
  • Bentuk fungsi hash : f(key) >> address
Macam-Macam Fungsi Hash
1. Hashing dengan kunci Modulus N
suatu fungsi hash yang paling popular dan paling sering di implementasikan adalah modulus N, dimana : f(kunci) = kunci mod N
  • Dengan N sebagai ukuran tabel atau berkas. Hasil fungsi modulus adalah sisa hasil bagi oleh N
  • Contoh N = 12 maka : 
30 Mod N = 6, dimana 30 dibagi 12 mengasilkan 2 sisa
      40 Mod N = 4, dimana 40 dibagi 12 menghasilkan 3 sisa 4
Keuntungan arti fungsi ini adalah hanya menghasilkan nilai dalam rentang ruang alamat (0) 
sampai dengan (N-1)

2. Hashing dengan Pemotongan
  • Alternatif lain untuk fungsi hashing adalah pemotongan.
  • Contoh Nilai NIP yang tadinya 9 digit dipotong menjadi hanya 3 digit, dengan mengambil 3 nomor terakhir. Misalnya : NIP 132312090 akan memiliki home address 090 atau 90


3. Hashing dengan Lipatan
  • Diandaikan kunci rekaman ditulis diatas kertas den dilipat kedalam bagian-bagian yang sama panjang, lalu setiap bagian dijumlahkan
  • Contoh, NIP yang 9 digit dibagi kedalam 3 bagian masing-masing 3 digit, terus dilipat pada bagian-bagian tersebut. 
  • Dijumlahkan akan menghasilkan 633 (dengan carrier) atau 533 (tanpa carrier)

4. Hashing dengan Pengkuadratan
  • Hashing dengan pengkuadratan adalah menentukan home-address sebuah rekaman dengan mengkuadratkan rekaman tersebut. Hasil kuadratan ini kemudian dapat dikombinasikan dengan pemotongan atau lipatan untuk mendapat alamat yang di izinkan. Sebagai contoh :
  • NIP : 132312090 memiliki home address :
1^2+3^2+2^2+3^2+1^2+2^2+0^2+9^2+0^2 = 1+9+4+9+1+4+0+81+0 =109

5. Penambahan Kode ASCII
  • Metode ini dapat digunakan jika kunci bukan berupa kode numerik. Home address dicari dengan menjumlahkan kode ASCII setiap huruf pembentuk kunci
  • Contoh : rekaman dengan kunci ADE memiliki home address = 65 + 68 + 69 = 20 





sumber : slide bu dine
Langganan: Postingan ( Atom )

Ads Inside Post

Recent Posts

Sports

Formulir Kontak

Nama

Email *

Pesan *