Teknik Hashing
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
1 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.
Metode Diagram Berserak (The scatter diagram)
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 :
1. garis yang digambar harus sedekat mungkin dengan semua titik yang ada di dalam diagram berserak.
2. Jumlah titik-titik yang berada pada masing-masing bagian garis yakni bagian atas dan bawah harus sama.
3. Garis itu harus digambar sedemikian rupa, sehingga titik yang berada di bagian atas dan bawah mempunya jarak yang sama.
