Tuesday, January 18, 2011

Metode Pembagian prosesor

Posted by Margiyono















-->

Beberapa metode yang digunakan untuk mongkonversikan Kunci
menjadi kombinasi tertentu yang akan digunakan fungsi hash, yaitu :
Metode Pembagian
Dengan metode ini kita dapat memilih suatu perubah m yang nilainya > dibanding
banyaknya kunci dalam K, misalnya adalah n,dan biasanya dipilih suatu bilangan prima.
Fungsi Hash-nya adalah :
H(k) = k mod m --à untuk alamat kunci 0 s.d. m-1
H(k) = k mod m + 1 --à untuk alamat kunci 1 s.d. m
Contoh :
Diketahui 5 buah nomor mahasiswa adalah 10347, 87492, 34212 dan 88688
yang akan disimpan kedalam array L yang terdiri dari 100 buah alamat yang
masing-masing alamat terdiri dari 2 karakter, yaitu : 00..99.
Cara untuk menentukan fungsi hash-nya adalah :
Langkah pertama dipilih dahulu bilangan prima yang dekat dengan 99, misalnya m=97.
Dengan menggunakan fungsi Hash H(k) = k mod m, maka :
H(10347) = 65, H(87492) = 95, H(34212) = 68, H(88688) = 30
Metode Midsquare
Dalam metode ini, kunci yang diketahui dikuadratkan, dan fungsi Hash-nya adalah :
H(k) = l
Nilai l diperoleh dengan menghapus digit-digit pada kedua sisi dari k2, dengan
catatan bahwa banyaknya digit disebelah kiri dan sebelah kanan harus sama.
Jika tidak sama, maka pada digit kiri seolah-olah ditambahkan sejumlah trailing zero,
sehingga akan menghasilkan alamat yang benar.
Sehingga penyelesaian untuk kasus seperti diatas adalah sbb :
k 10347 87492 34212 88688
k2 107060409 76548500564 1170460944 7865561344
H(k) 06 85 46 56
Penjumlahan Digit
Dalam Penjumlahan digit, kunci yang diketahui bisa dipecah menjadi beberapa
kelompok yang masing-masing terdiri dari beberapa buah digit, misalnya
2 buah digit. Kemudian digit-digit dari kelompok yang ada dijumlahkan.
Pemecahan dan penjumlahan terus dilakukan jika jumlah keseluruhan kelompok
yang ada masih > dari banyaknya alamat yang dipakai.
Sehingga penyelesaian untuk kasus seperti diatas adalah sbb :
H(10347)=1+03+47=51
H(87492)=8+74+92=174=1+74=75
H(34212)=3+42+12=57
H(88688)=8+86+88=182=1+82=83
Tabrakan adalah suatu keadaan dimana dua buah atau lebih record (rekaman) yang mempunyai
data kunci yang berbeda mempunyai alamat hash yang sama. Prosedur yang baik untuk
mengatasi adanya tabrakan antara lain terhadap perbandingan banyaknya data kunci (n)
dalam K, dan banyaknya alamat hash (m) dalam L.
Beberapa cara untuk mengatasi kemungkinan tabrakan :
  1. Pengalamatan Terbuka (Open Addressing)
  2. Penggandengan (chaining)
Secara umum, cara untuk mengatasi tabrakan dengan pengalamatan terbuka
(open Addressing) adalah sebagai berikut :
Bila sebuah rekaman (record) dengan kunci k akan disisipkan ke dalam tabel alamat hash.
Berdasarkan fungsi hash yang dipakai, alamat untuk kunci k tersebut dihitung, misalnya
pada alamat h. Jika ternyata bahwa lamat h sudah terisi, maka harus dicari alamat lain
yang masih kosong. Cara yang termudah adalah dengan mencari alamat berikutnya
yang kosong. Cara ini disebut dengan linear probing.
Secara umum, cara untuk mengatasi tabrakan dengan pengalamatan terbuka
(open Addressing) adalah sebagai berikut :
Bila sebuah rekaman (record) dengan kunci k akan disisipkan ke dalam tabel alamat
hash. Berdasarkan fungsi hash yang dipakai, alamat untuk kunci k tersebut dihitung,
misalnya pada alamat h. Jika ternyata bahwa lamat h sudah terisi, maka harus d
icari alamat lain yang masih kosong. Cara yang termudah adalah dengan m
encari alamat berikutnya yang kosong. Cara ini disebut dengan linear probing.
Contoh :
Fungsi hash terhadap suatu rekaman adalah sebagai berikut :
Rekaman
A
B
C
K
P
Q
R
Y
Z
H(k)
5
6
7
5
0
1
2
9
0
Maka rekaman-rekaman di atas akan tersimpan dalam memori sebagai berikut
Rekaman
P
Q
R
Z
-
A
B
C
K
Y
Alamat
0
1
2
3
4
5
6
7
8
9
Penggandengan (chaining) merupakan metode lain yang digunakan untuk mengatasi adanya collision resolution.
Metode ini pada prinsipnya memanfaatkan senarai berantai (yang juga bisa
diimplementasikan dengan array) yang dipasang pada setiap alamat hash l
engkap dengan senarai berantai yang menyimpan rekaman-rekaman yang mempunyai alamat hash yang sama.
Contoh :
Diketahui rekaman-rekaman terdiri dari :
34 56 123 78 93 70 100 21 11 77 28
Carilah nilai hash-nya dari rekaman-rekaman tersebut dengan menggunakan metode
pembagian (alamat hash yang disiapkan misalnya 10 buah yaitu alamat yang bernilai
0 s.d. 9) dan gunakanlah cara penggandengan (chaining) apabila terjadi tabrakan.
Penyelesian :
Fungsi Hash dipilih misalnya adalah k mod 10, sehingga nilai hash yang diperoleh
adalah sebagai berikut :
Rekaman
34
56
123
78
93
70
100
21
11
77
28
H(k)
4
6
3
8
3
0
0
1
1
7
8

0 comments: