TEKNIK KALKULASI ALAMAT

Teknik Kalkulasi Alamat

R(NILAI KEY) <> ADDRESS.
Adalah dengan melakukan kalkulasi terhadap nilai key, hasilnya adalah alamat relatif. Ide dasar dari kalkulasi alamat adalah mengubah jangkauan nilai key yang mungkin, menjadi sejumlah kecil alamat relative. Salah satu kelemahan dari teknik pengalamatan relative adalah ruang harus disediakan sebanyak jangkauan nilai key, terlepas dari berapa banyak nilai key. Salah satu masalah dari teknik ini adalah ditemukannya alamat relative yang sama untuk nilai key yang berbeda. Seperti di bawah ini adalah maksud dari keadaan itu;
Keadaan dimana :
R(K1) = R(K2) Disebut benturan atau
K1 ¹ K2 collision
Sedangkan nilai K1 dan K2 disebut synonym.
Ket : Synonim merupakan dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.

Teknik-teknik yang terdapat pada kalkulasi alamat :
Dalam teknik kalkulasi terdapat macam – macamnya dan sebagai berikut;
- Scatter storage techniques
- Randomizing technique
- Key-to-address transformation methods
- Direct addressing techniques
- Hash table methods
- Hashing

Teknik Hashing
Akan di jelaskan keuntungan dan kerugian dari teknik ini;
Keuntungan pemakaian Hashing :
- Nilai key yang sebenarnya dapat dipakai sehingga dapat di terjemahkan ke dalam sebuah alamat.
- Nilai key merupakan address space independent bila berkas direorganisasi, fungsi hash berubah tetapi nilai key tetap.
Kelemahan dati hasing :
- Distribusi nilai key yang dipakai
- Banyaknya nilai key yang dipakai relative terhadap ukuran dari ruang alamat
- Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebakan benturan
- Teknik yang dipakai untuk mengatasi benturan
Penampilan fungsi hash bergantung pada :
- Distribusi nilai key yang dipakai
- Banyaknya nilai key yang dipakai relative terhadap ukuran dari ruang alamat
- Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebabkan benturan
- Teknik yang dipakai untuk mengatasi benturan
Beberapa fungsi hash yang umum digunakan :
- Division Remainder
- Mid Square
- Folding
KEY TO ADDRESS TRANSFORMATION METHODS
Teknik yang digunakan dalam teori mengoreksi kesalahan-kode ini diterapkan untuk menyelesaikan masalah menangani file besar. dalam Pendekatan baru ini ke file menangani masalah digambarkan dengan desain khusus untuk menampilkan kelayakan. dari Efektivitas merupakan lebih lanjut diilustrasikan dengan membandingkan hasil uji yang diperoleh dari simulasi perhitungan, yang menggunakan data khas, terhadap nilai-nilai dihitung dari model yang ideal.
DIRECT ADDRESSING
Semua instruksi lain yang diperlihatkan menggunakan pengalamatan langsung, yang berarti bahwa data yang direferensikan sebenarnya disimpan dalam struktur lain - baik sebuah register atau lokasi memori.

TABEL HASH
Adalah merupakan struktur data yang menggunakan fungsi hash untuk efisien peta pengidentifikasi tertentu atau kunci (misalnya, nama-nama orang) untuk dihubungkan nilai (misalnya, nomor telepon mereka). Fungsi dari hash digunakan untuk mengubah kunci ke indeks (hash) dari array elemen (dalam slot atau ember) dimana nilai yang sesuai yang akan dicari.
Dalam banyak situasi, tabel hash ternyata lebih efisien daripada pohon pencarian atau lainnya tabel struktur lookup. Untuk alasan ini, mereka banyak digunakan di berbagai jenis komputer perangkat lunak , terutama untuk array asosiatif , pengindeksan database , cache , dan set .
Keuntungan
Keuntungan utama dari tabel hash atas struktur tabel data lainnya adalah kecepatan. Keuntungan ini lebih jelas ketika jumlah entri yang besar (ribuan atau lebih). tabel Hash dapat sangat efisien ketika jumlah maksimum entri dapat diprediksi dari sebelumnya, sehingga ember array dapat dialokasikan sekali dengan ukuran optimal dan tidak pernah diubah ukurannya.
2. Jika himpunan pasangan kunci-nilai adalah tetap dan dikenal lebih dulu sehingga insersi dan penghapusan tidak diijinkan, yang dapat mengurangi biaya rata-rata lookup pilihan hati-hati dari fungsi hash, ember ukuran meja, dan struktur data internal. Secara khusus, satu mungkin dapat menyusun fungsi hash yang tabrakan-bebas, atau bahkan sempurna.
Kerugian
1. Untuk aplikasi pengolahan string tertentu, seperti spell-checking , tabel hash mungkin kurang efisien daripada mencoba , automata terbatas , atau array Judy . Juga, jika setiap tombol diwakili oleh sejumlah kecil bit yang cukup, maka, bukan sebuah tabel hash, yang dapat menggunakan tombol langsung sebagai indeks ke array nilai.
2. Meskipun rata-rata biaya per operasi adalah konstan dan cukup kecil, dengan biaya operasi tunggal dapat cukup tinggi. Secara khusus, jika tabel hash menggunakan ukuran dinamis , penyisipan atau penghapusan operasi yang memerlukan waktu sebanding dengan jumlah entri.Hal ini dapat di katakan kelemahan yang serius secara real-time atau aplikasi interaktif.

3. Hash tabel dalam pameran umumnya miskin pemukiman referensi -yaitu, data yang akan diakses didistribusikan tampaknya secara acak di memori. Hal ini Karena tabel hash menyebabkan pola akses berupa melompat-lompat, ini dapat memicu cache mikroprosesor yang menyebabkan penundaan yang lama. struktur data seperti array, mencari dengan pencarian linear , akan lebih cepat jika meja relatif kecil dan tombol yang integer atau string singkat lainnya.
4. Tabel Hash menjadi sangat tidak efisien bila ada banyak tabrakan. Sementara itu hash distribusi yang tidak merata sangat tidak mungkin muncul secara kebetulan, seorang dengan pengetahuan dari fungsi hash mungkin dapat memberikan informasi untuk hash yang menciptakan perilaku-kasus terburuk dengan menyebabkan tabrakan yang berlebihan, yang mengakibatkan kinerja yang sangat buruk yaitu, sebuah serangan penolakan layanan . Dalam aplikasi kritis, baik universal hashing dapat digunakan atau struktur data dengan jaminan terburuk lebih baik mungkin lebih disukai.


SCATTER STORAGE TECHNIQUES

Sebuah metode dan aparatus untuk melakukan penyimpanan dan pengambilan dalam suatu sistem penyimpanan informasi yang diungkapkan menggunakan teknik hashing. Untuk mencegah kontaminasi dari media penyimpanan dengan secara otomatis berakhir catatan, teknik pengumpulan sampah digunakan yang menghapus semua berakhir catatan di lingkungan dari penyelidikan ke dalam sistem storge data.. Lebih khususnya, masing-masing probe untuk penyisipan, pengambilan atau penghapusan merekam adalah kesempatan untuk mencari seluruh rangkaian catatan ditemukan untuk catatan berakhir dan kemudian menghapusnya dan menutup rantai.Koleksi ini sampah secara otomatis menghapus catatan kontaminasi berakhir di sekitar probe, sehingga secara otomatis decontaminating ruang penyimpanan.. Karena tidak ada kontaminasi jangka panjang dapat membangun dalam sistem ini, akan sangat berguna untuk basis data yang besar yang banyak digunakan dan yang memerlukan akses cepat disediakan oleh hashing.


RANDOMIZING TECHNIQUE
Meskipun secara historis "teknik pengacakan" manual (seperti menyeret kartu, gambar potongan kertas dari tas, memintal roulette wheel) yang umum, saat ini teknik otomatis sebagian besar digunakan. . Seperti kedua memilih sampel acak dan permutasi acak dapat dikurangi menjadi hanya memilih nomor acak, nomor acak generasi sekarang metode yang paling umum digunakan, baik hardware nomor acak generator dan nomor acak generator-pseudo .
metode pengacakan Non-algoritmik meliputi:
• Casting Yarrow batang (untuk I Ching )
• Lempar dadu
• Menggambar sedotan
• Shuffling cards Mengocok kartu
• Roulette wheels Roulette roda
• Menggambar potongan kertas atau bola dari kantong
• " Lottery mesin "