Metode hashing
Berapakah home-address dan rekaman dengan kunci 3 digit nim terakhir anda, bila diketahui memiliki kapasitas 11 rekaman (N. 11)
Carilah home-address nim masing-masing
a. Hashing dengan pemotongan (3 digit terakhir)
b. Hashing dengan lipatan dan tentukan home-address dengan carry ataupun tanpa carry (3 digit terakhir)
c. Hashing dengan pengkuadratan
d. Hashing dengan penjumlahan kode Ascii
Jawab
2014 – 31 – 187
Menggunakan 3 digit terakhir yaitu 187. Jadi 187 Mod 11 = 17 sisa 0
Dengan pemotongan
Hanya memotong 3 digit terakhir saja 187. Jadi Home-addressnya adalah 187
Dengan lipatan
- dengan carry
201431187, dilipat dengan 3 bagian. Sehingga menghasilkan 201 | 431 | 187
Lalu angka tersebut dijumlahkan, dengan memperhatikan carrynya
201
431
187 +
1619
- tanpa carry
201431065, dilipat dengan 3 bagian. Sehingga menghasilkan 201 | 431 | 187. Tetapi untuk lipatan yang ganjil, angkanya dibalik. Sehingga menghasilkan 102 | 431 | 781.
Lalu angka tersebut dijumlahkan.
102
431
781 +
314
Dengan pengkuadratan
digit terakhir dikuadratkn 187 = 12 + 82 + 72 = 113
. Dengan penjumlahan Ascii
1 = 49
8 = 56
7 = 55
Lalu dijumlahkan 49 + 56 + 55 = 160
Metode Open Addressing
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-addresing dengan linier probing jarak 3
Urutan kunci yang masuk adalah 20, 31, 33, 40, 10, 12, 30, dan 15
Kunci
|
F (key)
|
Proses
|
Address
|
20
|
0
|
0
|
0
|
31
|
1
|
1
|
1
|
33
|
3
|
3
|
3
|
40
|
0
|
0, 3, 6
|
6
|
10
|
0
|
0, 3, 6, 9
|
9
|
12
|
2
|
2
|
2
|
30
|
0
|
0, 3, 6, 9, 2, 5
|
5
|
15
|
5
|
5, 8
|
8
|
Kunci
| |
0
|
20
|
1
|
31
|
2
|
12
|
3
|
33
|
4
| |
5
|
30
|
6
|
40
|
7
| |
8
|
15
|
9
|
10
|
Metode Coalesced Hashing
1. Bila terjadi tumbukan dalam pemasukan kunci rekaman, maka dapat dicari alamat yang paling besar atau paling akhir
Contoh :
Akan dilakukan penyisipan rekaman dengan kunci 38, 51, 40, 61, 83, 24, 60
- Langkah pertama untuk menjawab adalah lakukan proses hashing untuk semua kunci dengan mod 11
38
|
38 mod 11
|
5
|
51
|
51 mod 11
|
7
|
40
|
40 mod 11
|
7
|
61
|
61 mod 11
|
6
|
83
|
83 mod 11
|
6
|
24
|
24 mod 11
|
2
|
60
|
60 mod 11
|
5
|
Lalu akan menghasilkan table berikut :
Alamat
|
Rekaman
|
Metode Penghubung
|
0
| ||
1
| ||
2
|
24
| |
3
| ||
4
| ||
5
|
38
|
10
|
6
|
61
|
9
|
7
|
51
|
8
|
8
|
40
| |
9
|
83
| |
10
|
60
|
Komentar
Posting Komentar