Dalam teknik kalkulasi alamat pada organisasi berkas relative memiliki 6 cara dalam mengatasi benturan,antara lain :
1. Scatter diagram techniques
Scatter diagram atau bias kita sebut juga diagram hambur/pencar
menggunakan sebuah grafik yang terdiri dari dua sumbu yaitu sumbu
horizontal dan sumbu vertical. Pada sumbu horizontal berisi nilai-nilai
dari suatu variable dan sumbu vertikal mewakili pengukuran dari
variabel lain untuk mempelajari korelasi antara dua variable. Diagram
ini juga tidak selalu menunjukkan atau membentuk suatu efek karena satu
variabel terhadap variable yang lainnya tetapi mencerminkan keberadaan
(serta sebagai jenis / kekuatan) dari suatu hubungan, yang mungkin tipe
seperti kuat linier (positif atau negatif korelasi), kuadrat atau
eksponensial hubungan, outliner, teredam (sinusoidal hubungan), dll.
Maka dalam hal ini Scatter Diagram dapat menghasilkan analisis,yaitu
yang disebut dengan Regression Analysis.
Dalam
penggunaannya,scatter diagram digunakan untuk menunjukkan kedekatan
antara beberapa peristiwa atau pengamatan di dua pengukuran atau
menentukan apakah terdapat karakteristik antara dua korelasi. Korelasi
menyatakan bahwa jika salah satu variable berubah,maka variable yang
lain juga ikut berubah. Meskipun hal ini menandakan adanya hubungan
sebab akibat, namun ini tidak selalu terjadi karena tidak menutup
kemungkinan jika korealsinya terdapat ketiga karakteristik atau lebih.
Agar lebih jelas dalam pembahasan diagram berserak ini kita ambil contoh sebagai berikut: (dikutip dari google)
Hubungan
dua variable dapat digambarkan dalam diagram berserak. Pada diagram ini
variable independen digambarkan pada skala horisontal (skala X), sedang
varible dependen digambarkan pada skala horsontal (skala Y).
Selanjutnya pasangan 2 variable digambarkan pada giagram ini.
Apabila
gambar titik-titik pada diagram itu menunjukkan suatu garis lurus, maka
berarti ada hubungan sempurna antara variable yang satu dengan yang
lainnya.Beberapa hal yang perlu diperhatikan dalam menggambar garis pada
diagram berserak adalah :
garis yang digambar harus sedekat mungkin dengan semua titik yang ada di
dalam diagram berserak.Jumlah titik-titik yang berada pada
masing-masing bagian garis yakni bagian atas dan bawah harus sama.Garis
itu harus digambar sedemikian rupa, sehingga titik yang berada di bagian
atas dan bawah mempunya jarak yang sama.
Variable X dan Y
(iklan dan penjualan)
Dua variable tersebut dapat digambarkan dalam diagram berserak sebagai berikut :
2. Randomizing techniques
Teknik Acak sederhana terinspirasi oleh metode probabilistik
petajalan yang berguna untuk transformasi, menjadikan area bebas
benturan/tabrakan (collision) dan menggambarkan metode transformasi
iteratif yang memungkinkan seseorang untuk mencarikan solusi masalah
lebih mudah.
Baik Randon samples (Contoh acak) dan Random
permutations (permutasi acak) dapat mengurangi pemilihan angka secara
acak yang sederhana. Metode generasi angka secara acak sekarang paling
umum digunakan. Baik hardware random number generators dan pseudo-random
number generators.
3. Key to address transformation methods
Dalam penyimpanan dan pengambilan isi data dari lokasi memory di
komputer dengan pengalamatan langsung dimana komputer memberikan data ke
lokasi memori eksternal spesifik yang berasal dari kunci karakter
suatu data, salah satu dari metode tersebut yaitu dengan menggunakan
angka yang setara dengan karakter baru pada nomor posisi array.
Menterjemahkan kunci karakter data pertama dan seterusnya lalu lebih
acak ,karakter pada karakter dengan key-to-address transformation
(transformasi kunci suatu alamat)ini menggunakan modul hashing.
Beberapa
penumuan yang berkaitan dengan penyimpanan dan pengambilan informasi
biasanya berkaitan dengan key-to-address transformation atau prosedur
hashing. Objek dari penemuan ini menghasilkan seperangkat penyimpanan
alamat yang statistik dan secara acak.
Cluster dan gaps sering
terjadi dalam menentukan cara pengalamatan, disesuaikan dengan memory
atau bin address dan sering diturunkan dengan cara konversi kunci atau
transformasi alamat secara acak. Key-to-address transformation
dimaksudkan untuk memisahkan cluster dengan membuat distribusi
penyimpanan alamat yang hampir seragam, yang dikenal sebagai hashing
atau randomizing. Jadi idealnya, key-to-address transformation harus
menghasilkan alamat yang unik dari beberapa doumen lain atau record dan
100% penyimpanan memori yang dialokasikan ,pendistribusiannya haruslah
seragam dan semua ruang kosong harus terisi.
Sayangnya, baik
pengacakan lengkap maupun keseragaman yang lengkap tidak menyalurkan
hasil ketika kunci dijabarkan ke alamat dengan konversi acak biasa atau
teknik hashing. Hasilnya sering tidak dapat diprediksi dan overflows
yang tidak diinginkan.
Contoh:
Perhatikan catatan kunci X6, dalam kode EBCDIC huruf X adalah 231 dan karakter 6 dalam EBCDIC dalam notasi desimal adalah 246.
Key-to-address transformation menunjukkan penemuan dengan menggunakan
tabel dalam operasi penterjemahan. Satu atau lebih karakter dari kunci
record dianggap sebagai alamat tabel untuk penterjemahan awal. Setelah
sebuah karakter diterjemahkan lalu digabungkan dengan operator logika
yang tepat, logika matematika aritmatik , operasi boolean dengan
karakter kunci lain atau table entri.
4. Direct addressing techniques
Adalah teknik sederhana yang bekerja dengan baik ketika U sebagai semesta (nilai ruang kemungkinan ditandai dengan K).
U = {0,1, …. ,m-1},
Pada direct addressing techniques, instruksi lain yg diperlihatkan dengan menggunakan pengalamatan langsung,artinya data yg direferensikan sebnarnya disimpan didalam strutur lain,baik itu sebuah register ataupun lokasi memorii.
5. Hash table methods
Hash Table juga merupakan metode yang digunakan untuk mengatasi benturan yang terjadi bila ada key yang memiliki alamat yang sama. Pada metode ini linear list menyimpan data ke direktori, tetapi struktur data hash tersebut juga digunakan. Hash table akan mengambil nilai yang nantinya akan dihitung dari nama berkas dan akan mengembalikannya ke sebuah penunjuk nama berkas yang ada di-linear list. Oleh karenanya, ia dapat memotong banyak biaya pencarian direktori (dipercepat). Memasukkan dan mendelete berkas juga lebih mudah dan cepat. Walupun demikian beberapa aturan harus dibuat untuk mncegah benturan, situasi dimana kedua nama berkas pada hash mempunyai based yang sama. Kesulitan paling rawan dalam hash table adalah ukurannya yang tetap dari hash table dan kebergantungan fungsi hash dengan ukuran hash table tersebut.
Contoh, kita membuat suatu linear-probing seperti contoh hash sebelumnya, kita buat hash table yang dapat menampung 128 data. Fungsi hash akan mengubah nama berkas menjadi nilai dari 0 sampai 127. Jika kita membuat berkas ke 129 maka ukuran tabel hash harus diperbesar sampai misalnya 256 dan kita membutuhkan suatu fungsi hash yang baru yang nantinya dapat memetakan nama berkas dari jangkauan 0 sampai 255, dan kita juga harus mengatur data direktori yang sebelumnya sudah ada agar dapat memenuhi fungsi hash yang baru. Untuk alternatifnya kita juga dapat mengunakan chained-overflow hash table, karena setiap hash table mempunyai daftar yang saling terkait (linked list) dari nilai individual dan kita dapat mengatasi tabrakan dengan cara menambah tempat pada daftar tersebut. Pencarian bias saja menjadi lambat, karena pencarian nama memerlukan tahap pencarian pada daftar yang terkait. Tetapi operasi ini lebih cepat dibandingkan dengan pencarian linear terhadap seluruh direktori.
6. Hashing
Hashing dalam bahasa indonesia memiliki arti "penyincangan", metode Hashing pastinya digunakan untuk mengatasi benturan maupun mengurangi banyaknya ruang address yang digunakan dari key yang mempunyai cakupan nilai yang cukup luas ke nilai address yang telah dipersempit.
Untuk melakukan konversi (Pemetaan) dari record key ke address rekaman digunakan suatu fungsi yang di namakan fungsi hash:
bentuk fungsi hash:
F(key) = address
Cara mengatasi benturan dengan hashing menggunakan metode-metode sebagai berikut:
Metode open addressing adalah dengan cara mencari alamat-alamat selanjutnya yang masih kosong:
Contoh persoalan Linear Probing:
Jawab:
Metode Chaining:
Chaining (penggandengan) merupakan metode yang digunakan untuk
mengatasi kemungkinan adanya tabrakan alamat – alamat yang sama.
Dengan demikian, jika kita melihat pada sebuah alamat lengkap dan menyimpan rekaman - rekaman
yang mempunyai alamat yang sama, maka kita akan melihat adanya
sebuah senarai berantai tunggal berkepala denga kepalanya adalah alamat hash.
Contoh, jika kita mempunyai rekaman-rekaman yang record keynya ialah:
34 56 123 78 93 70 100 21 11 77 28
dan fungsi hash yang dipilih adalah k mod 10. Dengan demikian, alamat hash akan terdiri
dari sepuluh address yang bernomor 0 sampai 9.
Info: http://www.google.com
http://www.patents.com
http://www.webee.technion.ac.il
http://www.kakos.com.gr
0 komentar:
Posting Komentar