Tugas 07 Sistem Berkas "ORGANISASI BERKAS HASHING"

TUGAS 07

SISTEM BERKAS

ORGANISASI BERKAS

HASHING

Disusun oleh:

Asti Widyaningsih

121051032

JURUSAN TEKNIK INFORMATIKA

FAKULTAS TEKNOLOGI INDUSTRI

INSTITUT SAINS & TEKNOLOGI AKPRIND

YOGYAKARTA

2015

Diketahui:

Ditanyakan:

a.     Penempatan nilai-nilai kunci

b.   Rata-rata akses

Menggunakan metode:

1.      K MOD N

2.      K MOD P

3.      Midsquaring

4.      Penjumlahan Digit

5.      Multiplication

6.      Trunction

7.      Folding

8.      Konversi Radix

Jawaban:

Kunci yang akan digunakan adalah Kode. Kode diketahui terdiri dari huruf dan angka. Untuk itu, asumsi yang digunakan yaitu:

IPBU diasumsikan sebagai angka 0

TIFS diasumsikan sebagai angka 1

Spasi diasumsikan sebagai tidak ada/dihilangkan

Sehingga data menjadi:

Maka kuncinya adalah: 011101, 011102, 111103, 121202, 121201, 122105

METODE K MOD N

Diketahui:
N=6
P=7
alamat indeks= 0 sd 6

Jawab:
H(011101) = 011101 MOD 6 = 1
H(011102) = 011102 MOD 6 = 2
H(111103) = 111103 MOD 6 = 1 (collision)
H(121202) = 121202 MOD 6 = 2 (collision)
H(121201) = 121201 MOD 6 = 1 (collision)
H(122105) = 122105 MOD 6 = 5 (collision)

Penempatan Kunci:

Penyelesaian collision dengan metode LISCH.

Rata-rata akses: 10/6=1,67 detik

METODE K MOD P

Diketahui:

alamat indeks= 0-96

M=97

Jawab:

H(011101) = 011101 MOD 97 = 43
H(011102) = 011102 MOD 97 = 44
H(111103) = 111103 MOD 97 = 38
H(121202) = 121202 MOD 97 = 49
H(121201) = 121201 MOD 97 = 48
H(122105) = 122105 MOD 97 = 79

Penempatan Kunci:

Rata-rata akses: 6/97=0,0625 detik

Diketahui:
alamat indeks= 1-97

Jawab:

H(011101) = 011101 MOD 97+1 = 44
H(011102) = 011102 MOD 97+1 = 45
H(111103) = 111103 MOD 97+1 = 39
H(121202) = 121202 MOD 97+1 = 50
H(121201) = 121201 MOD 97+1 = 49
H(122105) = 122105 MOD 97+1 = 80

Penempatan Kunci:

Rata-rata akses: 6/97=0,0625 detik

METODE MIDSQUARING

Terjadi collision pada kunci 122105, penyelesaiannya menggunakan metode LISCH.

Penempatan Kunci:

Rata-rata akses: 7/100=0,07 detik

PENJUMLAHAN DIGIT

2 digit sehingga alamat indeks= 0 sd 99.

H(011101) = 01 + 11 + 01 = 13

H(011102) = 01 + 11 + 02 = 14

H(111103) = 11 + 11 + 03 = 25

H(121202) = 12 + 12 + 02 = 26

H(121201) = 12 + 12 + 01 = 25 (collision)

H(222105) = 12 + 21 + 05 = 38

Terjadi collision pada kunci 121201, penyelesaiannya menggunakan metode LISCH.

Penempatan Kunci:

Rata-rata akses: 7/100=0,07 detik

MULTIPLICATION

2 digit sehingga alamat indeks= 0 sd 99.
H(011101) = 01 | 11 | 01 = 11 * 01 = 11
H(011102) = 01 | 11 | 02 = 11 * 02 = 22
H(111103) = 11 | 11 | 03 = 11 * 03 = 33
H(121202) = 12 | 12 | 02 = 12 * 02 = 24
H(121201) = 12 | 12 | 01 = 12 * 01 = 12
H(122105) = 12 | 21 | 05 = 21 * 05 = 105 = 10

Penempatan Kunci:

Rata-rata akses: 6/100=0,06 detik

TRUNCTION

3 digit sehingga alamat indeks= 0 sd 999.

Pemotongan dilakukan pada 3 digit terakhir.

Penempatan Kunci:

Rata-rata akses: 6/1000=0,006 detik

FOLDING

2 digit sehingga alamat indeks= 0 sd 99.
Folding by boundary (non carry)

H(011101) = 01 | 11 | 01 = 10 + 11 + 10 = 31
H(011102) = 01 | 11 | 02 = 10 + 11 + 20 = 41
H(111103) = 11 | 11 | 03 = 11 + 11 + 30 = 52
H(121202) = 12 | 12 | 02 = 21 + 12 + 20 = 53
H(121201) = 12 | 12 | 01 = 21 + 12 + 10 = 43
H(122105) = 12 | 21 | 05 = 12 + 21 + 50 = 83

Penempatan Kunci:

Rata-rata akses: 6/100=0,06 detik

KONVERSI RADIX

Basis kunci = 2.

2 digit sehingga alamat indeks 0-99.

H(011101) = 1 * 2^4 + 1 * 2^3 + 1 * 2^2 + 1 * 2^0 = 16+8+4+1 = 29

H(011102) = 1 * 2^4 + 1 * 2^3 + 1 * 2^2 + 2 * 2^0 = 16+8+4+2 = 30

H(111103) = 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 1 * 2^2 + 3* 2^0 = 32+16+8+4+3 = 63

H(121202) = 1 * 2^5 + 2 * 2^4 + 1 * 2^3 + 2 * 2^2 + 2 * 2^0 = 32+32+8+8+2 = 82

H(121201) = 1 * 2^5 + 2 * 2^4 + 1 * 2^3 + 2 * 2^2 + 1 * 2^0 = 32+32+8+8+1 = 81
H(122105) = 1 * 2^5 + 2 * 2^4 + 2 * 2^3 + 1 * 2^2 + 5 * 2^0 = 32+32+16+4+5 = 89

Penempatan Kunci:

Rata-rata akses: 6/100=0,06 detik