TEKNIK KALKULASI ALAMAT
DAFTAR KELOMPOK
Andre Porandika
Fitrah Syauqi
Henry Dwi Permana
Linda Ernita Sari
Nusye Marlisa
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},
- nilai m tidak terlalu besar
- asumsikan bahwa tidak ada 2 unsur yang berbagi kunci yang sama
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
- metode Chaining
- metode Coalesced Hasing
- metode Chained Progressive Overflow
- metode Bucket
Metode open addressing adalah dengan cara mencari alamat-alamat selanjutnya yang masih kosong:
Contoh persoalan Linear Probing:
- fungsi hash yang digunakan ialah: f(key) = key mod 10
- ruang alamat yang tersedia ialah: 10 address
- metode hashing yang di gunakan ialah : open addessing dengan linear probing jarak 3
- urutan key yang masuk ialah 15,30,12,10,40,33,20,31
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
