bab i - asanisembiring.files.wordpress.com · web viewmodel pengalamatan ini kemungkinan masih...

Sistem Berkas

BAB VIORGANISASI FILE LANGSUNG

VI.1. LOKASI INFORMASIProses pencarian lokasi record dari suatu file tergantung bagaimana penataan

organisasi file. Organisasi file langsung sering disebut dengan Random access file langsung yang digunakan untuk menyusun record sedemikian hingga probe setiap record konstan atau satu, sehingga :f(key) merujuk ke alamat record. Dengan demikian setiap kunci berubah menjadi alamat dengan menggunakan fungsi hash, dimana key adalah alamat unik.

Penempatan dilakukan dengan fungsi tertentu untuk meletakkan suatu record pada tempat yang sudah ada. Perhatikan diagram berikut dalam gambar 6.1.

KONVERSI KEY TERHADAP ALAMAT UNIKDalam melakukan konversi field maka harus memiliki primary key dalam

alamat penyimpanan yang unik dan harus memperhitungkan apakah terdapat kemungkinan composite (dapat diuraikan) dengan suatu formula :

Lokasi A[i] = + m x s ; dimana :A : Suatu array dari beberapa dimensii : Tipe elemen : Lokasi elemen pertama dalam arraym : Jumlah elemen berdasarkan standar orders : Ukuran (dalam unit alamat) suatu elemen dari suatu array

Contoh :Untuk mengkonversi informasi ke dalam alamat unik pada sistem penerbangan

maka nomor penerbangan dari 1 sampai 999 ingin melakukan reservasi setiap tahun dengan sejumlah hari dari 1 sampai 365. Nomor penerbangan dan hari dalam 1 tahun disambung untuk menentukan lokasi record berisi reservasi penerbangan, sehingga :

Lokasi = nomor penerbangan || hari pada tahun tersebut ( || concatenation sambung ). Alamat akan memiliki range dari 001001 sampai dengan 999366.

KONVERSI KEY KE ALAMAT AKTUAL (PROBABLE)Konversi ini butuh suatu fungsi dengan memetakan nilai key ke dalam

pembawa nilai alamat. Konversi ini merujuk fungsi hash yang memerlukan nilai key ganda ke dalam nilai alamat tunggal dengan formula :

Hash (key) adalah alamat aktual dengan inisial alamat yang dapat diketahui pada pelokasian suatu record dalam tabel dikenal home address.

Beberapa fungsi yang memetakan key ke dalam range alamat diterima tetapi ditolak jika fungsi :- Menyebarkan key diantara alamat-alamat- Eksekusi tidak efisien

Bahan Ajar Kuliah : Sinar Sinurat, ST1

Key Space Address Space

0 0

999-9-9999 999-9-9999

Gambar 6.1. Korespondensi antara key dan alamat

Sistem Berkas

Suatu tabrakan (Collision) terjadi saat 2 key dalam alamat yang sama, hashing kemudian dimuat dengan memperhatikan 2 aspek :- Fungsi Hash : mengubah key menjadi alamat- Metode mengatasi tabrakan (collision resolution)

Contoh :Data = 3 13 23 15 16 26 27 37 47 50Menggunakan 13 tempat, berarti : key (3 s/d 50) address (0 s/d 12) maka

|key| >> |address| dimana |x| adalah panjang/jarak key x

VI.2. FUNGSI HASHFungsi hash akan membentuk tabel hash digunakan untuk

mengimplementasikan kamus dalam waktu konstan per operasi. Tabel hash mendukung pemanggilan dan penghapusan pada beberapa item yang sudah dinamai sebelumnya.

Dalam mengimplementasikan tabel hash yang menggunakan array dengan inisialisasi indeks-indeks tertentu maka pelaksanaan proses data dengan memetakan item-item ke dalam indeks dikenal fungsi hash .

f(key) = key mod N ; N adalah ukuran tabel danf(key) = key mod P ; P adalah bilangan prima terkecil (P N)

Contoh : Diberikan data sebagai berikut : 3 13 23 15 16 26 27 37 47 50

maka pemetaan hashing langsung ke alamat tertentu :Indeks : 0 1 2 3 4 5 6 7 8 9 10 11 12Key : 13 26 15 3 16 27 47 23 37 50Jumlah N = 13

f(3) = 3 mod 13 = 3 ; probe = 1 kalif(13) = 13 mod 13 = 0 ; probe = 1 kalif(23) = 23 mod 13 = 10 ; probe = 1 kalif(15) = 15 mod 13 = 2 ; probe = 1 kalif(16) = 16 mod 13 = 3 ; probe = 1 kali ; terjadi tabrakan (collision) ;

untuk mengatasinya gunakan Resolution Linier Probing, jika i berisi data maka lakukan i+1 else i+2 dan seterusnya sampai menemukan ruang kosong, sehingga : probe = 2 kali

f(key) = ((fi-1(key))+1) mod N, jadif(16) = (3+1) mod 13 = 4 f(26) = 26 mod 13 = 0 ; terjadi collision, maka f(26) = (0+1) mod 13 = 1 probe = 2 kalif(27) = 27 mod 13 = 1 ; terjadi collision

f(27) = (1+1) mod 13 = 2 ; terjadi collisionf(27) = (2+1) mod 13 = 3 ; terjadi collisionf(27) = (3+1) mod 13 = 4 ; terjadi collisionf(27) = (4+1) mod 13 = 5 ; probe = 5 kali


f

Sistem Berkas

f(37) = 37 mod 13 = 11 ; probe = 1 kalif(47) = 47 mod 13 = 8 ; probe = 1 kalif(50) = 50 mod 13 = 11 ; terjadi collision

f(50) = (11+1) mod 13 = 12 ; probe = 2 kali berdasarkan data di atas bahwa jumlah data 10 buah, jumlah bucket (hole) = N = 13 saat penyisipan data terjadi probe sebanyak 17 kali, sehingga rata-rata probe = 17/10 = 1,7 kali.

Bandingkan dengan pemetaan file sequential sebagai berikut :Indeks : 0 1 2 3 4 5 6 7 8 9 Key : 3 13 23 15 16 26 27 37 47 50Jumlah N = 10Rata-rata probe = (1+10)/2 = 11/2 = 5.5

Berdasarkan data di atas dapat disimpulkan bahwa :- Pemetaan file sequential lebih lambat dibandingkan dengan pemetaan file langsung- Efisiensi tempat untuk pemetaan file secara langsung 10/13 sedangkan pemetaan

file sequential 10/10Mode waktu akses dapat dilihat pada :- Fungsi- Pengakses

Perlu diketahui bahwa semakin kecil tempat/ jumlah bucket maka kemungkinan tabrakan akan semakin besar. Sedangkan fungsi hash untuk load faktor merupakan faktor muatan yaitu pembanding antara.

Jika jumlah perbandingan terisi dengan jumlah tempat yang tersedia maka akan semakin kecil faktor muatan untuk memperkecil terjadinya tabrakan. Untuk menghindari/ memperkecil tabrakan adalah :- Perbesar tempat- Ganti fungsi resolusi misalnya +2.Hal penting lainnya adalah alat-alat yang mempengaruhi tabrakan antara lain :- Ukuran key- Fungsi resolusi

Hubungan antara key dan address menjadi n-1 sehingga key (n) address,dimana n key dapat memperoleh alamat yang sama. Linier address terjadi bila satu alamat terisi maka key akan lompat terhadap key berikutnya (linier probing).

Contoh : 2 12 22 32 42 Data ini diolah dengan metodologi :

(a) Bucket (b)=10, f(key) = key mod 10 akan selalu tabrakan(b) Bucket (b) = 7, f(key) = key mod 7 (bilangan prima) maka address akan merata

dengan :2 mod 7 = 2 12 mod 7 = 5 22 mod 7 = 132 mod 7 = 4 42 mod 7 = 0

perlu diperhatikan bahwa tidak selamanya penambahan kapasitas dapat memperbaiki waktu akses/ probe tergantung pada :

(a) Fungsi hash(b) Fungsi Resolusi (mengurangi tabrakan)(c) Load factor = jumlah record yang ada (load density) pada ruang yang ada(d) Distribusi dari key, misalnya :

i. 2,3,5,7,11ii. 2,3,4,5,6


f

Sistem Berkas

Jika pada bagian I dan ii diberi fungsi f(key) = key mod 6 maka pada bagian i akan sering terjadi, dan ii key address terletak tepat pada tempatnya (data terletak rapat) dan hubungan hubungan key dan address i-1 dimana record yang memiliki address yang sama maka hasil address semuanya menjadi 0

(e) Urutan key, jika ada 2 fungsi yang mempunyai rata-rata tabrakan yang sama maka diambil fungsi yang memiliki standard deviasi kecil.

ALOKASI FUNGSI HASH- Fungsi hash yang digunakan harus cepat dan dapat mendistribusikan key secara

merata dalam tempat tersebut (jangan ada home address yang sering ditempati, dimana home address lain tidak sampai terdapat rantai yang terlalu panjang untuk menghindari terlalu sering tabrakan)

- Beberapa kemungkinan untuk menghindari tabrakan :(1) h(x) = x mod N ; n adalah jumlah blok/ media simpan yang digunakan(2) h(x0 = x mod P ; P adalah bilangan prima dengan modulo tetap +1

jika P maka addressnya diluar blok jatuh pada modulo + 2(3) Truncation, misalnya :

Indeks : 123 45 6789 123 45 6789Data : 111-11-1111 s/d 999-99-9999Jumlah data 1000 (dengan tujuan agar tempat cukup)Dalam memilih kombinasi key 111-11-1111 s/d 99-99-9999 sedemikian hingga digit key berkisar 4 digit maksimal dan dapat menentukan posisi load factor untuk melakukan posisi pengaksesan.

(4) Folding, jenis-jenis folding ada 2 yaitu :(a) Boundary (batas), yaitu melipat dengan batas misalnya :

Sehingga diperoleh 3 bagian folding yaitu :

3 2 14 5 69 8 7 +

(b) Shifting (pergeseran), adalah suatu proses pergeseran atau pemotongan, misalnya :

9 5 0 8 2 0 1 2 3 +(1) 8 9 3

carry

Carry dapat ditambahkan pada digit terakhir agar diperoleh hasil yang lebih baik dan hasilnya menjadi :

8 9 3 1 + 8 9 4


1 2 3 4 5 6 7 8 9

9 5 0 8 2 0 1 2 3

Sistem Berkas

Perlu diperhatikan bahwa tidak semua carry harus ditambahkan pada digit terakhir,

contoh : (1) 8 9 9 8 9 9 1 +

9 0 0 (dengan shifting terjadi perubahan pada semua angka)

x1 = left (key,3) =

x2 = mid (key, 4, 3) =

x3 = right (key,3) =

x = val (x1) + val (x2) + val (x3)

dimana val untuk mengubah character menjadi numericFolding dapat digunakan untuk mengubah string menjadi integer agar dapat

dijumlahkan.

KUNCI NON NUMERIK (ALPHABETIK)Kunci dapat berupa string, char sebagai contoh :

Anggota (nama, tanggal_lahir, tanggal_nikah, umur) jika dipilih field nama sebagai key (primary key). Pemilihan primary key dilakukan berdasarkan pertimbangan bahwa field tersebut dapat mengidentifikasikan record secara unik. Untuk mengubah key (nama) menjadi integer antara 000 ... 999 digunakan formula :

Address = Ascii (left(key,1)) + Ascii (right(key,1)) mod 1000Model pengalamatan ini kemungkinan masih dapat mengakibatkan tabrakan :

Misalnya : Susilo Yudoyono Sandi Yanto

maka untuk menghindari tabrakan (rantai yang paling panjang) digunakan formula :

Misalnya nama terdapat 30 character maka L = 30/2 = 15 (pekerjaan berkurang Y2)berikut diberikan algoritma sebagai berikut :

function Hash (key : string) : integerbegin

Address = 0i = 1while (i length (key)) dobegin

address = address + ascii (key(i))i = i + 2

endhash = address mod 1000

end

VI.3. COLLISION RESOLUTION


Address = Ascii (key i)L

i=1Address = Ascii (key i)

Y2

i=1atau

Sistem Berkas

Perbaikan collision ini mempengaruhi baik tidaknya file yang akan digunakan dengan fungsi tertentu. Collision resolution merupakan fungsi atau metode khusus yang digunakan mengatasi tabrakan (koalisi), dengan :- Koalisi dapat terjadi pada saat sisip dan cari- Jika Home Address sama maka alamat aktual berbeda- Key N-1 alamat. Alamat sebenarnya record tersebut adalah alamat aktual dan

alamat yang ditempati oleh N record yang sama adalah home address.- Jika tabrakan terjadi kita akan melakukan hashing lagi atau dinamakan Rehashing

yaitu mencari alamat yang lain dengan menggunakan fungsi hash lain dimana fungsinya sama dengan fungsi hash yang pertama, address akan tetap / tidak berpindah.

Perhatikan diagram berikut pada gambar 6.2.

Suatu fungsi dimasukkan ke dalam h atau diolah dengan hash akan memperoleh alamat.

- Fungsi hash digunakan pada saat cari dan sisip

Contoh Kasus :Selesaikan dengan quadratic probing kasus berikut :Diberikan key-key yang akan diinput dalam tabel hash “satu”, “dua”, “tiga”, “empat”, “lima”, “enam”, “tujuh”, “delapan”, “sembilan”, “sepuluh”.

Spesifikasi :- Jumlah blok/bucket (ukuran hash) = 17 (indeks 0 sampai dengan 16)- Fungsi hash h(x) berdasarkan metode perkalian dengan A = 0.618- Fungsi ordinal () total bilangan alpabetik dari huruf-huruf pada key (“a”=1,

“b”=2, “c”=3, ..., “z” = 26)- Collision dipecahkan dengan cara rehashing dengan fungsi

h2(x,i) = -i * ((ord*(x)%5)+1) sehingga penempatan probing ke i adalah hi(x) = h1(x) + h2(x) dengan i =1,2,3, …

Tunjukkan urutan penempatan key-key tersebut dalam tabel dan berapa jumlah collision yang terjadi pada masing-masing penempatan key.


collisionh tempatkan / selesai

rehash

address

h address no

yes

Gambar 6.2. bagan alur Rehashing

Sistem Berkas

Jawab :

Tabel 6.1. Konversi alpabetik dengan fungsi ordinalOrd() Ordinal * A Fractional (AK)Ord(satu) = 19+1+20+21 = 61 61 * 0.618 = 32,698 0.698Ord(dua) = 4 + 21 + 1 = 26 26 * 0.618 = 16.068 0.068Ord(tiga) = 20 + 9 + 7 + 1 = 37 22.866 0.866Ord(empat) = 5 + 13 + 16 + 1 + 20 = 55 33.990 0.990Ord(lima) = 12 + 9 + 13 + 1 = 35 22.630 0.630Ord(enam) = 5 + 14 + 1 + 13 = 33 20.394 0.394Ord(tujuh) = 20 + 21 + 10 + 21 + 8 = 80 49.440 0.440Ord(delapan) = 4+5+12+1+16+1+14=53 32.754 0.754Ord(sembilan) = 19+5+13+2+9+12+1+14=75 46.350 0.350Ord(sepuluh) = 19+5+16+21+12+21+8=102 63.036 0.036

Sebelum melakukan fungsi rehashing terhadap keseluruhan hasil ordinal huruf-huruf dari masing-masing item data diatas maka dapat dilakukan dengan fungsi floor (pendekatan pembulatan nilai ke bawah) pada fungsi hash H(x), seperti pada tabel 6.2. berikut :

Tabel 6.2. Fungsi rehashingFungsi hashH(x) = m.frac(AK)

RehashingH2(x,i) = -i * ((ord(x) % 5) + 1)

H(satu) = 17 * 0.698 = 11H(dua) = 17 * 0.068 = 1H(tiga) = 17 * 0.866 = 14H(empat) = 17 * 0.990 = 16H(lima) = 17 * 0.630 = 10H(enam) = 17 * 0.394 = 6H(tujuh) = 17 * 0.440 = 7H(delapan) = 17 * 0.754 = 12H(sembilan) = 17 * 0.350 = 5H(sepuluh) = 17 * 0.036 = 0

H2(x,1) = -1 * (61 % 5 + 1) = -2H2(x,2) = -2 * (26 % 5 + 1) = -4H2(x,3) = -3 * (37 % 5 + 1) = -9H2(x,4) = -4 * (55 % 5 + 1) = -4H2(x,5) = -5 * (35 % 5 + 1) = -5H2(x,6) = -6 * (33 % 5 + 1) = -24H2(x,7) = -7 * (80 % 5 + 1) = -7H2(x,8) = -8 * (53 % 5 + 1) = -32H2(x,9) = -9 * (75 % 5 + 1) = -9H2(x,10) = -10 *(102 % 5 + 1) = -30

Tabel ini tidak menunjukkan adanya collision.Tabel 6.3. Penempatan probing

i Key H(x) H2(x) Penempatan probingH’(x) = H(x) + H2*(x,i)

12345678910

SatuDua TigaEmpatLimaEnamTujuhDelapanSembilanSepuluh

111141610671250

-2-4-9-4-5-24-7-32-9-30

111141610671250


SepuluhDua

SembilanEnamTujuh

LimaSaturdayDelapan

Tiga

empat

012345678910111213141516

Gambar 6.3. Rehashing

Sistem Berkas

Beberapa kemungkinan dari collision resolution adalah :

(1) Linier resolution (+1 atau next) dengan kondisi tetap berputarMisalnya :

Keadaan ini tidak akan memungkinkan karena akan tetap berulang (infinity loop) dan rehashing pun tidak berguna.

(2) Quadratic resolutionProses quadratic posisi sekarang, kemudian di modulokan. Misalnya B = 1000Hash address (x) = 5 dimana 52 mod 1000 = 25Jika B = 10 maka 52 mod 10 = 5 dan 51 mod 10 = 5 dan seterusnya akan tetap berada di tempat sama (tidak bergerak), untuk menghindari ini digunakan :h(x) = y dan h2(x) = (y2 + y) mod B, Contoh : B = 10 dan Y = 5 maka 52 mod 10 = 5 dan (52 +5) mod 10 = 0 sehingga hi(x) = (hi-1 (x) + P) mod P dimana P = 1,2,3, ...

(3) Linked list pointer


789

X 1 baris2346

Catatan :Kemungkian infinity loop karena walau semua tempat terisi yang seharusnya menyatakan semua tempat terisi akan tetapi proses berlanjut (seperti jarum jam)

Gambar 6.4. Linier resolution

yx

Blok utama

Blok overflow

keyAlamat aktual

Gambar 6.5. Blok utama dan overflow

Sistem Berkas

Dua buah key yang mempunyai suatu address yang sama dinamakan home address (sinonim) dan rangkaian sinonim adalah rantai dimana makin panjang rantai maka makin lama waktu address.

Untuk mengatasi tabrakan terdapat berbagai cara (resolusi) yang digunakan yang pada prinsipnya tergantung organisasi tabel hash yang digunakan.Tabel hash dapat diorganisir dengan cara :(a) Bucket (tabel) digunakan langsung untuk menyimpan record yang mendapat home

address pertama dan record-recor yang menabrak(b) Bucket dibagi 2 yaitu primary dan overflow dengan cara :

- Implementasi array- Scanning dilakukan dari awal (resolusi linier)- Record-record yang ada di bucket linier adalah record-record yang tidak

pernah menabrak tetapi sering ditabrak- Primary adalah yang pertama sekali mendapat home address- Biasanya primary lebih banyak overflow

Misalnya h(x) = y maka h2(x) = (y2 + y) mod B atau hi(x) = (hi-1(x) + P) mod B ; dimana p = 1,2,3…Hash function mengevaluasi H kemudian mencoba H2+12 ; H2+22 ;H2+32; …; H2+n2 ; dengan qwadratic probing dapat diselesaikan dilakukan dengan 2 cara :Cara I :

Maka h(x) x mod 7 dengan demikian :


2 3 5 7 11 13 17 19 23 29

0 1 2 3 4 5 6 7 8 9 Terdapat 10 blok/bucketPrimer 7 blok/ bucketAverflow 3 blok/ bucket

Langsung home address

h(2) = 2 mod 7 = 2h(3) = 3 mod 7 = 3h(5) = 5 mod 7 = 5h(7) = 7 mod 7 = 0h(11) = 11 mod 7 = 4h(13) = 13 mod 7 = 6h(17) = 17 mod 7 = 3h(19) = 19 mod 7 = 5h(23) = 23 mod 7 = 2h(29) = 29 mod 7 = 1

collision

7

2923115

13

7

1923

0123456

012

collision

collision

collision

sikuensial

Gambar 6.6. Qaudratic probing

Sistem Berkas

berarti :

Cara II :

Tabel 6.4. Proses infinitive probingIndeks Key Modulo Address Probe Collision

123456

7

89

H(2)H(3)H(5)H(7)H(11)H(13)H(13)H(17)H(17)H(19)H(23)H(23)H(23)H(23)…..

2 %102 %105 %107 %1011 %1013 %10(13+12) %1017 % 10(17 + 12) %10 19 % 1023 % 10(23+12)%10(23+22)%10(23+32)%10……

23571347893472……

11111111111111….

1

1

1111……

Sehingga untuk sikuensi data diatas apabila diselesaikan dengan quadratic probing akan terjadi collision yang tidak terbatas (infinity) seperti pada item data 23 (tabel 6.4)

Sehingga diperoleh kesimpulan bahwa penggunaan tabel hash yang dibagi menjadi 2 bucket (primer dan overflow) masih lebih baik dibandingkan dengan 1 bucket (primer).

Untuk mengukur efisiensi dan dan address factor adalah :

Efisiensi = tempat yang dipakai / tempat yang dimiliki x 100%

Address factor = jumlah primer / jumlah total tempat x 100%

Contoh :


Total probe = 16 kali

Key : 2 3 5 7 11 13 17 19 23 29

Probe (kali) : 1 1 1 1 1 1 2 3 4 1

Rata-rata probe = 16/10 = 1,6 2 kali

Collision terjadi sebanyak 6 kali

2 3 5 7 11 13 17 19 23 29 0 1 2 3 4 5 6 7 8 9

Terdapat 10 blok/bucket

11 2 3 13 5 7 17 9

0 1 2 3 4 5 6 7 8 9

Gambar 6. 7. Infinitive Probing

Sistem Berkas

Jumlah primer = 100 dan overflow = 10 maka address factor = 100/110 x 100% = 90,9 % sedangkan home address yang

mungkin adalah besaran jumlah primer.

(c) Bucket (table) terbagi 2 yaitu primer dan overflow dengan implementasi primer dan overflow yang ditunjuk oleh pointer.

Hal-hal yang perlu :- Penggunaan implementasi pointer, dari yang lainnya karena pointer

langsung menuju tempat tertentu tanpa melalui blok-blok yang lain.- Pada implementasi pointer, jika terjadi tabrakan pada overflow maka dapat

dilakukan resolusi linier dan tidak mungkin lagi dilemparkan pada bucket primer

(d) Tabel hash (array[0..n-1] of pointer)(1) - Merupakan modifikasi cara yang ketiga

- Digunakan untuk menghindari tabrakan yang masih terjadi bila tempat sudah kosong

- Hanya untuk menyimpan pointer yang akan menuju suatu blok yang akan diisi

- Pointer terhadap array sama dengan hash yang berisi array terhadap pointer dan berisi array dari record

- Kelemahannya adalah semakin banyak tempat yang kosong (tidak terisi)


12n-1

Pointer

Primer

Overflow

Gambar 6.8. Bucket dengan pointer

01n-1

01

m

01

m

pointer

Gambar 6.9. Hash tabel dengan pointer

Sistem Berkas

- Jika semua blok sudah terisi / sudah terpakai maka efisiensinya adalah :Jumlah tempat = n + n x m x P x 1 byte = n (mP + 1) byte dimana P adalah panjang recordBlok yang terisi = n x P byteEfisiensi tempat = nP / (nPm + n) x 100%Contoh : n =1000, m=10, p=100, jumlah record = 100 dan memiliki home address yang berbeda, berarti :Jumlah tempat = n x n x m x P = 100 + (100 x 10 x 1000) = 100 byteBlok yang terisi = n x P = 100 x 100 = 10.000Efisiensi tempat = 10.000 / 100.000 x 100% = 9,8 %

(2) - Pointer pertama adalah pointer yang ditentukan dan tidak pernah menabrak- Pointer yang berikutnya pernah menabrak minimal satu kali- Mneyimpan pointer terhadap rangkaian- Penggunaan akan lebih baik jika rangkaian pointernya sama panjang- Kelemahannya tergantung pada banyaknya pointer yang dipakai- Keuntungannya : tidak mungkin terjadi tabrakan, pointer dapat digunakan

atau tidak digunakan tidak masalah sebab sudah disediakan.

Cara menghitung jumlah pointer yang dipakai untuk n buckets dan N record dimana 1 data merepresentasi 1 pointer dan jumlah pointer = N + nContoh : 10 record dan 2 bucket maka pointer yang dipakai = 10 + 2 = 12 kemungkinannya adalah : 0 – 10 , 1 – 9, 2 – 8, 3 – 7, 4 – 6, 5 – 5

(e) Double hashBertujuan untuk memperkecil masing-masing tabrakan menjadi satu kali dan rata-rata 2 key = 1 home address


Hash table

Gambar 6.10. Hash tabel dengan linked list

01

n

Gambar 6.11. Double hashing

Sistem Berkas

VI.4. METODE BRENT’SSemua metode resolution dianggap sebagai metode statik yang mengakses

semua item berdasarkan alamat. Kemudian bagaimana dengan metode dinamik, salah satu item akan disimpan sekali pemindahan dan metode juga berlaku untuk beberapa item dengan batasan-batasan tertentu terhadap record-record yang tidak tersimpan dalam home address. Keputusan untuk penambahan proses dengan menyisip salah satu item ke dalam tabel hanya sekali akan tetapi pngambilan boleh beberapa kali.

Primary probe chain dari satu record adalah sekuensi lokasi yang dipesan selama penyisipan atau pemanggilan suatu record. Misalnya primary probe chain pada 39 berisi 3 posisi P1, P2 dan P3 yang berhubungan terhadap alamat-alamat. Posisi awal P1 untuk primary probe chain adalah home address.

P1 6 (28)P2 9 (29)P3 1 (empty)

Saat ke tiga posisi dipesan sebelum lokasi kosong ditemukan maka 3 probe dibutuhkan untuk pemanggilan, kemudian 39 dapat disisip pada home addressnya sendiri, jadi 1 probe yang perlu untuk pemanggilan.

Dari contoh di atas kapan dibolehkan untuk memindahkan 28 ? Dengan mencoba memindahkan 28 ke lokasi berikutnya probe chain (28) menjadi :

P1 6 (28) 8 (empty)P2 9 (29)P3 1 (empty)

Pemindahan suatu record dari primary probe chain disebut secondary probe chain (merepresentasi horijontal line) yang berisi 1 entry saat posisi awal yang dipesan adalah empty.

Pada posisi P (empty) jika 28 dipindah terhadapnya 2 probe kemudian akan dibutuhkan terhadap lokasi 28 tetapi akan mengosongkan lokasi 6 sehingga 39 dapat disimpan dan hanya 1 probe yang perlu untuk menemukan 39, 28 butuh 1 lagi probe untuk mengambil 39 yang akan membutuhkan 2 probe yang lebih kecil untuk jaringan pengurangan dari 1 probe oleh pemindahan 28. Perhatikan diagram berikut pada gambar 6.12.


Q1 P1,1 Q1 P1,2 Q1 P1,3 Q1 P1,4

Q2 P2,1 Q2 P2,2 Q2 P2,3

Q3 P3,1 Q3 P3,2

Q4 P4,1

P1Q

P2Q

P3Q

P4QP5Q

Gambar 6.12. Metode Brent’s, probe chain dan ordernya

Sistem Berkas

Contoh :Penyimpanan record dengan suatu bucket misalnya : 27, 18, 29, 28, 39, 13, dan 16 dengan menggunakan fungsi hash.Hash (key) = key mod 11 dan fungsi penambah : i(key) = hasil bagi (key/11) mod 11 sehingga :27 mod 11 = 5 terjadi probe 1 kali18 mod 11 = 7 terjadi probe 1 kali29 mod 11 = 7 terjadi collision sehingga 7 + 2 = 9 terjadi 2 kali probe ( i=1, j=1

nilai s pada penyisipan data 29 adalah 2)28 mod 11 = 6 terjadi probe 1 kali39 mod 6 = 6 terjadi collision sehingga kita mencoba untuk memindahkan

dengan i=1 dan j=1 untuk perhitungan nilai s artinya mencoba memindahkan home address 6 satu offset selama probe chain atau dalam kasus ini kita coba memindahkan 28 ke lokasi 8 disebabjkan lokasi 8 kosong dan terjadi probe 2 kali oleh karena itu sisipkan nilai data 39 langsung ke lokasi 6 kemudian pengurangan jumlah probe dengan 1.

13 mod 11 = 2 terjadi probe 1 kali16 mod 11 = 5 terjadi collision, pertama hitung nilai x dari 6 berapa banyak

kombinasi pada i+j lebih kecil dari 6 ? adalah 10. Dengan i=1, j=1 kita mencoba untuk memindahkan ke yang pertama atau home address pada probe chain dari 16 ke posisi berikutnya, khususnya 27 ke lokasi 7 dari lokasi 5 dan home address 7 terisiUntuk i=1 dan j=2 coba pindahkan 27 ke lokasi 9 (posisi ini terisi)Untuk i=2 dan j=1 pindahkan posisi kedua pada probe chain 16, pada kasus ini data 39 yaitu 9 (juga terjadi kegagalan).Selanjutnya i=1 dan j=3 coba pindahkan 27 ke lokasi 0, lokasi tersebut kosong dan lakukan penyisipan maka posisi 5 kosong dan langsung diisikan nilai 16.

Perhatikan diagram berikut pada tabel 6.5. Tabel 6.5. Order data dengan probe chain

Indeks Key012345678910

27-13--1639182829-


Sistem Berkas

VI.5. PERFECT HASHINGDikatakan perfect hashing (hashing sempurna) jika ada fungsi h sedemikian

yang dapat mengubah key menjadi alamat unik.H (key) alamat unik

Jika h sedemikian maka tidak diperlukan resolusi dan probe=1. Fungsi perfect hashing adalah memetakan key ke dalam alamat unik jika range alamat potensial adalah sama dengan bilangan key dan fungsi tersebut perfect hashing function minimal (dalam ruang).

Contoh 1 :Data : Ani, Budi, Cahyono, anto, Boris, Cynthia; jika digunakan ukuran bucket=10 maka h(x) = y mod 10 ; dimana y adalah bilangan bulat dari konversi karakter menjadi numeric. Perhatikan tabel 6.6. berikut : Tabel 6.6. Konversi karakter menjadi decimal

Char Decimal Char DecimalABCDE

6566676869

FG

….….Z

7071….….90

Sehingga : h(Ani) = (65+78+73) mod 10 = 216 mod 10 = 6h(Budi) = (66+85+68+73) mod 10 = 292 mod 10 = 2h(Cahyono) = (67+65+72+89+79+78+79) mod 10 = 529 mod 10 = 9 h(Anto) = (65+78+84+79) mod 10 = 306 mod 10 = 6 terjadi collisionh(Boris) = (66+79+82+73+83) mod 10 = 383 mod 10 = 3h(Cynthia) = (67+89+78+84+72+73+65) mod 10 = 528 mod 10 = 8

Contoh 2 :Data: Boris, Becker, Andre Agassi, Pete Sampras, Michael Chang, Thomas Muster,

Stefen Edberg, Goran Ivanisevic, Todd martin, Michael StickUkuran bucket = 10 ; pengujian akan dilakukan :

(1) h(x) = ascii (c1(x)) mod 10 ; akan terjadi collision karena terdapat beberapa inisial nama yang sama

(2) h(x) = (ascii (c1(x)) + ascii (cn(x)) mod 10h(1) = (66+82) mod 10 = 8h(2) = (65+13) mod 10 = 8 terjadi collision

(3) h(x) = asii(ci(x)) mod 10h(1) = (66+79+82+73+83+66+69+67+75+69+82) mod 10 = 1h(2) = (65+78+68+82+69+65+83+83+73) mod 10 = 2h(3) = (80+69+84+69+83+65+77+80+82+65+83) mod 10 = 7h(4) = (77+73+67+72+65+69+76+67+72+65+78+71) mod 10 = 2 terjadi collisiondan seterusnya

(4) h(x) = (h0(x) + h1(x) + h2(x)) mod 10 ; dimana h0 = length (x) ; h1 = ascii(c1(x)) dan h2(x) = ascii(c2(x))h(1) = (12+66+82) mod 10 = 0h(2) = (12+65+73) mod 10 = 0 terjadi collision


|x| i=1

Sistem Berkas

(5) h(x) = (h0(x) + h1(x) + h2(x)) mod 10h0 = length (x) ; h1 = T(c1(x)) ; h2 = T(cn(x))T adalah frekwensi / jumlah masing-masing karakter yang terdapat dalam tabel, perhatikan tabel 6.7. berikut :

Tabel 6.7. Tabel asciiHuruf Frekuensi Huruf Frekuensi

ABCDEFGHIJKLMN

1336412145901264

OPQRSTUVWXYZ

4108107120000

h(1) = (12+3+8) mod 10 = 3h(2) = (12+13+9) mod 10 = 4h(3) = (12+1+10) mod 10 = 3 terjadi collision

(6) Kurangi load faktor (menambah ukuran tabel)Tambah ukuran key = 11 sehingga :h(x) = (h0(x) + h1(x) + h2(x)) mod 10h(1) = (12+3+8) mod 11 = 2h(2) = (12+13+9) mod 11 = 3h(3) = (12+1+10) mod 11 = 2 terjadi collisionmaka penambahan ukuran keytidak mempengaruhi tabrakan (collision)

(7) Diberikan tabel sebagai load factor pada tabel 6.8. berikut :Tabel 6.8. Load factor

Huruf Kode Ascii Frekuensi KodeABCDEFGHIJKLMNOP

65666768697071727374757677787980

133641214590126441

78697372817175778274767883828381


Sistem Berkas

QRSTUVWXYZ

81828384858687888990

06107120000

81889391868887888990

h(x) = (h0(x) + h1(x) + h2(x)) mod 10 ; dimana h0 = length (x) ; h1 = kode(c1(x)) dan h2(x) = kode(c2(x))h(1) = (12+69+90) mod 10 = 1h(2) = (12+78+82) mod 10 = 2h(3) = (12+81+93) mod 10 = 6h(4) = (13+83+75) mod 10 = 1 Terjadi collision

VI.6. OPEN HASHING (OPEN ADDRESSING)Open hashing (open addressing) digunakan untuk menyimpan pointer dengan

array dan linked list. Misalnya :Const B = NType data = record

Item : tipe dataNext : ^data

EndHash = array[0..B-1] of ^data

Fungsi yang digunakan adalah h(x) = f(x) mod B. Perhatikan diagram berikut dalam gambar 6.13

Pada open hashing bahwa pencarian dilakukan secara sequential dan jika tidak ditemukan akan dicari pada posisi next.

Keuntungan menggunakan open hashing adalah :(1) Kemungkinan penuh tidak ada(2) Collision tidak masalah disebabkan pointer menyediakan 1 tempat kosong untuk

data dimana item data pertama mendapat home address menjadi awal mata rantai dan yang terakhir menjadi ujung mata rantai

Kelemahannya adalah :


item

item item

item

n

0array

Gambar 6.13. Open addressing

Sistem Berkas

(1) Banyaknya pointer akan menghabiskan lokasi penyimpanan, jumlah pointer = N x B byte dimana N adalah jumlah data dan B adalah bucket dan biasanya untuk memperpendek mata rantai dilakukan dengan menambah bucket dan penyisipa dilakukan diujung rantai agar lebih cepat dan dapat digunakan stack dimana penyisipan dilakukan diawal pada posisi top (dengan metode First In First Out = FIFO)

(2) Cara pencarian dalam mata rantai secara sequentialHal-hal yang perlu diperhatikan dalam memilih struktur file adalah :

(1) Besar tempat yang digunakan(2) Waktu akses untuk pencarian, penyisipan dan penghapusan

HAPUS DATA DALAM LINKED LISTUntuk menghapus data penelusuran dilakukan dengan dengan menempatkan

posisi diawal list sampai ditemukan item data yang dicari. Misalnya Hapus (c, list)

Algoritmanya adalah :Data.item = ’c’Data.^next = data.^next.^next

Probe rata-rata dari open hashing (PR) adalah PR = 1 + N / B ; N adalah jumlah data dan B adalah bucket. Modifikasi untuk memperbaiki kelemahan pointer digunakan untuk menunjuk array data (menunjuk ke lokasi bucket). Kelemahannya adalah sulit untuk menentukan berapa besar bucket array yang harus disediakan. Perhatikan diagram berikut dalam gambar 6.14.

Bubble sort = N2 (jumlah data)

VI. 7. ALGORITMA CICHELLI’S


a b c d

012345

ArrayA10 A20 A30 A40 A50

A15 A25 A35 A45 A55

Gambar 6.14. Pointer merujuk array

Sistem Berkas

Dalam algorima cichelli’s terdapat komponen-komponen fungsi yaitu :h0 = length (key) , h1 = first_character (key) , h2 = last_character (key) dan g = T(x) dimana T adalah nilai yang tergabung dengan karakter individu yang terdapat pada key dan untuk proses ini tersedia kode reserve word bahasa pemrograman pascal. Perhatikan tabel 6.9 berikut :

Tabel 6.9. Nilai character pada reserve word pascalCharacter Nilai Character Nilai Character Nilai

ABCDEFGHIJ

111511015315130

KLMNOPQRST

015151301501466

UVWXYZ

14106060

Dalam algoritma Cichelli’s juga menggunakan fungsi perfect hashing. Contoh 1:

Begin terdiri dari 5 karakter, gunakan tabel 4.9. untuk menyelesaikan P.hash (begin) sehingga : P.hash (begin) = 5 + T(h1(key)) + T(h2(key))

= 5 + T (b) + T(n)= 5 + 15 + 13= 33

berarti keyword begin disimpan pada lokasi alamat 33, total reserve word pascal sebanyak 36 . Jumlah reserve word ada sebanyak 36 buah dan butuh waktu 40 menit berarti dari contoh di atas bahwa nilai hash berkisar dari 2 sampai dengan 37 untuk set data yang merupakan fungsi perfect hash minimal.

Contoh 2 :Digunakan algoritma Cichelli’s untuk menyelesaikan sikuensi cat, ant, dog,

gnat, chimp, rat, toad. Asumsikan nilai maksimum yang boleh diberikan terhadap karakter adalah 4. Hal-hal yang perlu diperhatikan :

- Jika tidak dapat menemukan solusi menggunakan 4 coba dengan nilai yang lebih besar.

- Jika nilai maksimum juga masih kecil berarti tidak memiliki solusi- Jika nilai maksimum sangat besar kita tidak akan menemukan solusi

maksimalFrekuensi karakter pertama dan terakhir adalah a=1, c=2, d=2, g=2, p=1, r=1, t=5 sehingga :cat 7ant 6dog 4gnat 7chimp 3rat 6toad 7


Sistem Berkas

Berikutnya kita mengurut key dalam order menurun berdasarkan jumlah frekuensi untuk menentukan frekuensi karakter pertama dan terakhir. Langkah berikutnya adalah mengecek order untuk melihat jika beberapa key yang memiliki karakter awal dan akhir yang ditunjukkan pada deretan key sebelumnya dicatat bahwa d dan g dari dog dengan memindahkan “dog” ke posisi sebelumnya dengan “gnat” (urutan ke tiga) sehingga :

toad 7gnat 7dog 4cat 7rat 6ant 6chimp 3

berikan nilai karakter t dan d pertama dengan nilai zero (0) dan toad pada hash ke lokasi 4 maka : t=0, d=0 (sebagai inisial) sehingga P.hash (toad) = 4

Kemudian g dalam gnat dengan zero (0) akan terjadi hash komplit di lokasi 4 kemudian menambahkan nilai dengan 1 kemudian hash berada pada lokasi 5 dimana t=0, d=0, g=1 sehingga :

P.hash (toad) = 4 P.hash(gnat) = 5.Karakter awal dan akhir “dog” pada hash sebelumnya berada pada lokasi 4 dan

hasilnya terjadi hash komplit dengan mengulangi ke key sebelumnya yaitu “gnat” dengan mencoba nilai berikutnya pada g dengan penambahan nilai 2 sehingga : t=0, d=0, g=2 sehingga :

P.hash (toad) = 4 P.hash(gnat) = 6.

dengan melanjutkan langsung terhadap “dog” pada hash berada di lokasi 5 sehingga : t=0, d=0, g=2 sehingga :

P.hash (toad) = 4P.hash(gnat) = 6 P.hash(dog) = 5. Tentukan t=0, d=0, g=2 sehingga : P.hash (toad) = 4P.hash(gnat) = 6P.hash(dog) = 5P.hash(cat) = 3

dengan memberikan nilai r=4 untuk menghindari komplik dengan t=0, d=0, g=2, c=0, r=4 sehingga :

P.hash (toad) = 4P.hash(gnat) = 6P.hash(dog) = 5P.hash(cat) = 3P.hash(rat) = 7

dengan memberikan suatu nilai ke a akan menyebabkan collision dan harus kembali, dengan mencoba t=3 kemudian t=0, d=0, g=3, c=0, r=2 sehingga :

P.hash (toad) = 4P.hash(gnat) = 7P.hash(dog) = 6


Sistem Berkas

P.hash(cat) = 3P.hash(rat) = 5Kemungkinan akan tetap komplik sewaktu memberikan suatu nilai terhadap a

dan kembali ke awal, dengan memberikan nilai baru terhadap g =4 maka t=0, d=0, g==4m c=4, r=2 a=3 da p=4 sehingga :

P.hash (toad) = 4P.hash(gnat) = 8P.hash(dog) = 7P.hash(cat) = 3P.hash(rat) = 5P.hash(ant) = 6P.hash(chimp) = 9


bab i - asanisembiring.files.wordpress.com · web viewmodel pengalamatan ini kemungkinan masih...

Documents