Teknik Kalkulasi Alamat dalam Sistem Berkas
Perhitungan (kalkulasi) terhadap nilai kunci atribut untuk mendapatkan nilai suatu alamat disebut dengan Fungsi hash.
Fungsi hash dikatakan baik bila memiliki kalkulasi yang sederhana dan memiliki kelas ekuivalen (synonim) yang kecil(memiliki kalkulasi yang mudah tetapi memiliki benturan alamat yang sedikit).
Salah satu masalah dari teknik ini adalah ditemukannya alamat relatif yang sama untuk nilai key yang berbeda.
Keadaan dimana :
R(K1) = R(K2) ,disebut benturan
K1 K2 ,atau collision
Sedangkan nilai key K1 dan K2 disebut synonim. Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.
R(K1) = R(K2) ,disebut benturan
K1 K2 ,atau collision
Sedangkan nilai key K1 dan K2 disebut synonim. Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.
A. DIVISION REMAINDER
Membagi nilai key field dengan nilai tertentu, dan sisa pembagian tersebut dijadikan alamat relatifnya. Tujuannya adalah agar alamat yang akan digunakan bisa berbeda sekecil mungkin (menghemat memori) dan menghindari benturan yang bakal terjadi.
Membagi nilai key field dengan nilai tertentu, dan sisa pembagian tersebut dijadikan alamat relatifnya. Tujuannya adalah agar alamat yang akan digunakan bisa berbeda sekecil mungkin (menghemat memori) dan menghindari benturan yang bakal terjadi.
Contoh:
asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai kunci sebagai berikut :
12, 21, 68, 38, 52, 70, 44, 18
Maka:
(12 mod 11) + 1 = 1 + 1 = 2 ; simpan 12 dilokasi 2
asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai kunci sebagai berikut :
12, 21, 68, 38, 52, 70, 44, 18
Maka:
(12 mod 11) + 1 = 1 + 1 = 2 ; simpan 12 dilokasi 2
Maka:
(12 mod 11) + 1 = 1 + 1 = 2 ; simpan 12 dilokasi 2
(21 mod 11) + 1 = 10 + 1 = 11 ; simpan 21 dilokasi 11
(68 mod 11) + 1 = 2 + 1 = 3 ; simpan 68 dilokasi 3
(38 mod 11) + 1 = 5 + 1 = 6 ; simpan 38 dilokasi 6
(52 mod 11) + 1 = 8 + 1 = 9 ; simpan 52 dilokasi 9
(70 mod 11) + 1 = 4 + 1 = 5 ; simpan 70 dilokasi 5
(44 mod 11) + 1 = 0 + 1 = 1 ; simpan 44 dilokasi 1
(18 mod 11) + 1 = 7 + 1 = 8 ; simpan 18 dilokasi 8
Sehingga
(12 mod 11) + 1 = 1 + 1 = 2 ; simpan 12 dilokasi 2
(21 mod 11) + 1 = 10 + 1 = 11 ; simpan 21 dilokasi 11
(68 mod 11) + 1 = 2 + 1 = 3 ; simpan 68 dilokasi 3
(38 mod 11) + 1 = 5 + 1 = 6 ; simpan 38 dilokasi 6
(52 mod 11) + 1 = 8 + 1 = 9 ; simpan 52 dilokasi 9
(70 mod 11) + 1 = 4 + 1 = 5 ; simpan 70 dilokasi 5
(44 mod 11) + 1 = 0 + 1 = 1 ; simpan 44 dilokasi 1
(18 mod 11) + 1 = 7 + 1 = 8 ; simpan 18 dilokasi 8
Sehingga
index 1 2 3 4 5 6 7 8 9 10 11
Nilai Kunci 44 12 68 - 70 38 - 18 52 - 21
Nilai Kunci 44 12 68 - 70 38 - 18 52 - 21
Ada perhitungan faktor muat (load factor) yaitu, jika memiliki sejumlah record yang akan ditempatkan ke dalam memori, maka setidaknya harus menyediakan memori yang kapasitasnya melebihi dari jumlah record tersebut.
Misalkan, memiliki 4000 record, maka sebaiknya memiliki memory space sebanyak 5000 alamat.
Faktor muat dihitung dengan cara membagi jumlah record dalam file dengan jumlah maksimum record dalam file (alamat yang tersedia).
Semakin besar nilai faktor muat maka semakin baik teknik ini digunakan.
Faktor muat untuk contoh di atas adalah 4000/5000 = 0,8.
Semakin besar nilai faktor muat maka semakin baik teknik ini digunakan.
Faktor muat untuk contoh di atas adalah 4000/5000 = 0,8.
B. MID SQUARE.
Teknik ini dilakukan dengan cara melakukan kuadratisasi nilai key field dan diambil nilai tengahnya sebanyak jumlah digit yang diinginkan.
Misalkan, nilai keynya = 123456790, setelah dikuadratkan hasilnya = 15241578997104100 dan diambil 4 digit di tengahnya, yaitu 8997. Jadi, alamat memori untuk data tersebut di 8997.
C.HASHING BY FOLDING.
Teknik ini dilakukan dengan cara ’melipat’ nilai dari kunci atribut sebanyak digit yang dibutuhkan (dari kanan), kemudian dijumlahkan. Nilai terbesar dari jumlah tersebut dibuang (jika melebihi digit yang dibutuhkan).
C.HASHING BY FOLDING.
Teknik ini dilakukan dengan cara ’melipat’ nilai dari kunci atribut sebanyak digit yang dibutuhkan (dari kanan), kemudian dijumlahkan. Nilai terbesar dari jumlah tersebut dibuang (jika melebihi digit yang dibutuhkan).
Misalkan untuk nilai key 123456790, maka empat angka di belakang setelah dilipat menjadi 0976, angka tersebut ditambahkan dengan empat angka kedua (dari kanan) yaitu 2345 dan angka 1 paling kiri :
0976
2345
1
——– +
4321
Maka, alamat dari data tersebut adalah di 4321.
0976
2345
1
——– +
4321
Maka, alamat dari data tersebut adalah di 4321.
0 komentar:
Post a Comment