MANAJEMEN KOLISI & COLLISION RESOLUTION

Metode Untuk Mengatasi Kolisi / Tubrukan :

1. Metode Open Addressing

• Alamat alternatif dicari pada alamat-alamat selanjutnya yang masih kosong, salah satu nya dengan cara Linier Probing
• Linier Probing :Pencarian dilakukan dengan jararak pencarian yang fix (tetap), biasanya satu-satu
• 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 addressing dengan linier probing jarak 3
• Urutan kunci yang masuk adalah 20, 31, 33, 40, 10, 12, 30, dan 15 
  

2. Metode Coalesced Hashing

• Bila terjadi tumbukan dalam pemasukan kunci rekaman maka dapat dicari alamat yang paling besar / paling akhir
• Contoh : misalkan akan dilakukan penyisipan rekaman-rekaman dengan kunci 38, 51, 40, 61, 83, 24, dan 60
• Langkah 1 lakukan proses hashing semua kunci dengan kunci modulus 11 (11 adalah kapasitas berkas), maka dihasilkan :

PILE FILE

1. Merupakan organisasi file yang strukturnya sangat sederhana dan jarang sekali digunakan dalam pengolahan data elektronik.
2. Digunakan sebagai pembanding dalam mengevaluasi organisasi file lainnya yang strukturnya lebih baik 

Karakteristik Pile File

1. Penyusunan urutan record-recordnya, dilakukan berdasarkan kronologis masuknya data
2. Panjang setiap field & recordnya bervariasi
3. Elemen data yg disimpan pd masing-masing record kemungkinan bervariasi
4. Bentuk / struktur organisasinya sederhana
5. Data / informasi yg masuk ke dlm file, disimpan tanpa diproses terlebih dulu
6. Pembentukan Pile File dpt dilakukan dgn mudah & cepat
7. Pencarian record data di dalam Pile File sangat sulit

Structure dan Manipulation

• Struktur record pd pile file, harus terdiri dari elemen-elemen data yg saling berhub., dimana pd setiap elemen data diberikan Identitas, sehingga mempunyai Arti.

• Identitas dari elemen data tsb, bisa berupa nama secara eksplisit, seperti : Umur, ataupun berupa kode , attribute.

• Struktur di atas disebut : “ Self Describing Fields “

•  Cth : Umur = 40  ( Attribute_name, Value)

• Attribute_name pd pile file dpt menjadi :

• Complex-attribute, bila attribute tsb terbagi-bagi lagi dlm sejumlah attribute_name,  Value pairs

• Pencarian record-record pada pile file dilakukan dengan cara menentukan beberapa attribute di dlm search-argumentnya.

• Attribute-attribute yg ditulis pada search argument disebut  “Key Attribute“, sedangkan attribute-attribute lainnya disebut “Goal Data“. Key menentukan record-record yg akan dicari sedangkan Goal Data merupakan elemen-elemen data

Penggunaan Pile File

• Pile File merupakan struktur dasar dan tidak terstruktur.

• Penggunaannya dapat digunakan pada:

1. File-file system

2. File Log (mencatat kegiatan)

3. File-file Penelitian / medis

4. File teks

5. config.sys

Performance Dari Pile File :

1. Record Size (R)

   File density dari pile file dipengaruhi oleh 2 faktor, yaitu :

• Kebutuhan utk menyimpan attribute_name bersama-sama dengan datanya.
• Data yang tidak dibutuhkan / data yangg tidak ada tidak perlu disiapkan(disediakan tempat / lokasinya)

2. Fetch Record (TF)

   Waktu yang dibutuhkan untuk menemukan lokasi sebuah record sangat lama. Hal ini disebabkan karena semua record harus ditelusuri untuk mencari elemen yang menjadi Key-attribute.

3. Get Next Record (TN)

  Record-record tidak disusun berdasarkan urutan tertentu, maka record berikutnya yang akan diakses bisa berada dimana saja.

4. Insert Record (TI)

   Menyisipkan sebuah record baru dpt dilakukan dgn cepat dan mudah, hal ini disebabkankarena pd pile file tdk terdpt struktur record maupun urutan penyusunan record.

5. Update Record (TU)

• Mencari lokasi yang akan diupdate
• Merubah status record lama menjadi invalid
• Kemudian tulis record baru pada akhir file

6. Read Entire (TX)

  Proses membaca seluruh record pada pile, dilakukan dgn cara membaca record dari awalsampai akhir pile.

7. Reorganization (TY)

• Record-record yg sudah di update / didelete   memiliki  Tombstone Mark ygmenyatakan   record tsb sudah tdk valid lagi.
• Kemudian record-record invalid yg sudah tdk   dibutuhkan tsb secara periodik dihilangkan   dgn cara, mengcopy pile file yg lama menjadi   pile file yg baru. Dimana record yg invalid   tdk dicopy.

ORGANISASI BERKAS SECARA LANGSUNG & METODE HASHING

Organisasi Berkas Langsung

• Organisasi berkas langsung digunakan untuk menemukan suatu rekaman tidak melalui proses pencarian, namun bisa langsung menuju alamat yang ditempati oleh rekaman.
• Hal ini digunakan dengan cara menyimpan rekaman pada alamat yang sama dengan nilai kunci rekaman tersebut
• Contoh : Rekaman dengan kunci 50 akan di simpan pada alamat 50
• Sehingga untuk menemukan sebuah rekaman cukup melihat nilai kunci dan menuju kealamat yang ditunjuk oleh kunci rekaman tersebut, contoh jika ingin melihat rekaman dengan kunci 28 langsung saja menuju alamat 28 tersebut.
• Harus tersedia 1 ruang untuk setiap kemungkinan penyimpanan kunci rekaman, meskipun dalam rekaman tersebut data nya sudah tidak ada.
• Contoh dalam suatu universitas yang memiliki ribuan mahasiswa pasti ada bebera nomor yang kosong untuk beberapa alasan, misalnya sudah lulus, mengundurkan diri, DO, Cuti, dsb
• SEHINGGA TIDAK SEMUA RUANG DIMANFAATKAN UNTUK MAHASISWA AKTIF

Korespondensi Satu-Satu

• Dengan menerjemahkan langsung dari kunci rekaman kealamat rekaman, maka akan berlaku suatu hubungan korespondensi satu-satu antara kunci dengan alamat rekaman.
• Hal ini menyebabkan harus disediakannya ruang yang sangat besar untuk menampung stiap kemungkinan nilai kunci yang ada.
• Contohnya : untuk menyimpan data karyawan yang kuncinya adalah NIP (Terdiri dari 9 digit) dibutuhkan sebanyak satu milyar alamat, karena kemungkinan yang dapat muncul dari kode 9 digit adalah mulai dari angka 000000000 hingga 999999999

Kerugian korespondensi Satu-Satu

• Korespondensi satu-satu ini akan mengakibatkan pemborosan ruang penyimpanan atau terjadi banyak alamat yang tidak dipergunakan alias kosong.
• Contoh : Kode NIP yang diawali dengan tiga digit kode departemen, yang tidak mungkin ada kode departemen 000. sehingga alamat 000000000 sampai dengan 999999999 (sebayak sejuata alamat) tidak akan terpakai karena tidak ada rekaman dengan NIP dianatar range tersebut.

Metode Hashing

• Untuk mengatasi kerugian yang timbuldari cara korespondensi satu-satu tersebut, amak digunakan metode lain yang disebut dengan metode hashing.
• Metode hashing pada intinya digunakan untuk melakukan pemetaan (melakukan konversi) dari kunci rekaman yang memiliki cakupan nilai yang luas ke nilai alamat yang memiliki cakupan yang lebih sempit
• Bentuk fungsi hash : f(key) >> address

Macam-Macam Fungsi Hash

1. Hashing dengan kunci Modulus N

suatu fungsi hash yang paling popular dan paling sering di implementasikan adalah modulus N, dimana : f(kunci) = kunci mod N

• Dengan N sebagai ukuran tabel atau berkas. Hasil fungsi modulus adalah sisa hasil bagi oleh N

• Contoh N = 12 maka : 

30 Mod N = 6, dimana 30 dibagi 12 mengasilkan 2 sisa

      40 Mod N = 4, dimana 40 dibagi 12 menghasilkan 3 sisa 4

Keuntungan arti fungsi ini adalah hanya menghasilkan nilai dalam rentang ruang alamat (0) 

sampai dengan (N-1)

2. Hashing dengan Pemotongan

• Alternatif lain untuk fungsi hashing adalah pemotongan.

• Contoh Nilai NIP yang tadinya 9 digit dipotong menjadi hanya 3 digit, dengan mengambil 3 nomor terakhir. Misalnya : NIP 132312090 akan memiliki home address 090 atau 90

 

3. Hashing dengan Lipatan

• Diandaikan kunci rekaman ditulis diatas kertas den dilipat kedalam bagian-bagian yang sama panjang, lalu setiap bagian dijumlahkan

• Contoh, NIP yang 9 digit dibagi kedalam 3 bagian masing-masing 3 digit, terus dilipat pada bagian-bagian tersebut. 
• Dijumlahkan akan menghasilkan 633 (dengan carrier) atau 533 (tanpa carrier)

4. Hashing dengan Pengkuadratan

• Hashing dengan pengkuadratan adalah menentukan home-address sebuah rekaman dengan mengkuadratkan rekaman tersebut. Hasil kuadratan ini kemudian dapat dikombinasikan dengan pemotongan atau lipatan untuk mendapat alamat yang di izinkan. Sebagai contoh :

• NIP : 132312090 memiliki home address :

1^2+3^2+2^2+3^2+1^2+2^2+0^2+9^2+0^2 = 1+9+4+9+1+4+0+81+0 =109

5. Penambahan Kode ASCII

• Metode ini dapat digunakan jika kunci bukan berupa kode numerik. Home address dicari dengan menjumlahkan kode ASCII setiap huruf pembentuk kunci

• Contoh : rekaman dengan kunci ADE memiliki home address = 65 + 68 + 69 = 20