Berikut adalah beberapa hasil pencarian yang kelompok kami dapatkan. Pencarian bahan cukup membingungkan karena kelompok kami harus bersusah payah untuk mendapatkan sumber yg kami inginkan, dan semoga apa yang kami sajikan cukup bermanfaat.
Dalam ilmu komputer , sebuah tabel hash atau hash peta adalah 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 hash digunakan untuk mengubah kunci ke indeks (hash) dari array elemen (dalam slot) dimana nilai yang sesuai yang akan dicari.
Idealnya fungsi hash harus memetakan setiap tombol untuk indeks slot yang berbeda, tapi ini jarang dicapai dalam praktek (kecuali tombol hash tetap; entri baru yaitu tidak pernah ditambahkan ke tabel setelah penciptaan). Kebanyakan desain tabel hash berasumsi bahwa "hash collisions" (pasang kunci yang berbeda dengan nilai hash yang sama) adalah normal dan harus diakomodasi dalam beberapa cara.
Dalam tabel hash dimensioned, baik biaya rata-rata (jumlah instruksi ) untuk setiap pencarian independen dari jumlah elemen yang tersimpan dalam tabel. Banyak desain tabel hash juga memungkinkan insersi sewenang-wenang dan penghapusan dari-nilai pasangan kunci, pada rata-rata konstan.
Dalam banyak situasi, tabel hash ternyata lebih efisien daripada pohon pencarian atau lainnya tabel struktur lookup. Untuk alasan ini, Hash table banyak digunakan di berbagai jenis komputer perangkat lunak , terutama untuk array asosiatif , pengindeksan database , cache , dan set .
tabel Hash seharusnya tidak akan membuat kita bingung dengan daftar hash dan pohon hash digunakan dalam kriptografi dan transmisi data .
Key-to-address Transformation Methods
Penyimpanan atau pengambilan catatan dari penyimpanan komputer atau memori pada
umumnya dilakukan dengan scanning, atau langsung menangani. Pemindaian file
catatan untuk mengambil satu record tertentu membutuhkan perbandingan kunci
dengan kunci satu record dengan satu record lainnya sampai kecocokan ditemukan.
Pengalamatan langsung melibatkan setiap record ke lokasi tertentu biasanya
berdasarkan kunci rekaman. Pengalamatan langsung menyediakan cara yang paling
cepat dalam mengakses catatan dalam file tunggal, tetapi proses transformasi
kunci rekaman, ke alamat yang sesuai atau lokasi di mana catatan dapat
ditemukan, memiliki beberapa kerugian. Baik pengacakan lengkap ataupun hasil
distribusi sepenuhnya seragam ketika tombol yang dikonversi ke alamat bahkan
oleh transformasi konversi acak atau teknik hashing. Sebuah proses transformasi
atau hashing yang disediakan di sini tidak hanya mengarah ke tingkat yang lebih
besar dari keacakan, tapi begitu umum bahwa efektif untuk kedua jenis statis
dan volatile file.
Cara kerja:
Dalam menyimpan dan mengambil data dalam dan dari lokasi memori di komputer dengan pengalamatan langsung dimana komputer memberikan data ke spesifik lokasi memori eksternal berasal dari data karakter kunci, metode ini terdiri dari (Data) menyimpan sebagai array dalam memori komputer meja unordered n karakter kunci dengan menggunakan modul program, n merupakan nomor data karakter kunci yang tersedia untuk data, setiap data karakter kunci yang secara acak ke posisi yang berbeda dalam array, masing-masing karakter data kunci memiliki posisi yang unik dalam array.
Mengakses posisi nomor dalam array data karakter pertama kunci numerik menggunakan setara unik dan modul panggilan.
Menggunakan setara numerik dari karakter baru pada nomor posisi dalam array, menerjemahkan data karakter kunci dahulu lalu ke yang lain lagi, karakter yang lebih acak, dengan transformasi kunci-ke-alamat menggunakan modul hashing.
Iteratif menerjemahkan setiap data karakter kunci menjadi karakter acak baru dengan menggunakan modul menelepon, modul hashing, dan langkah-langkah (2) dan (3).
Memilih setiap karakter acak baru dan karakter yang berdekatan dalam array dengan operasi di modul hashing untuk membentuk setara numerik komposit untuk setiap data karakter kunci.
Menggabungkan dan scaling karakter komposit sehingga setara numerik diperoleh dengan menggunakan operasi yang telah ditentukan untuk menghasilkan alamat memori data, dan
Menyimpan dan mengambil data dalam dan dari alamat data memori dengan menggunakan modul pemanggilan.
Direct Addressing Techniques
Pengalamatan langsung sangat bernama karena nilai yang akan disimpan dalam
memori diperoleh secara langsung mengambilnya dari lokasi memori lain. Sebagai
contoh:
MOV A, 30h
Instruksi ini akan membaca data dari alamat RAM Internal 30 (hexidecimal) dan
menyimpannya dalam Akumulator.
Pengalamatan langsung umumnya cepat karena, meskipun nilai yang akan isnt
dimuat termasuk dalam instruksi tersebut, maka dengan cepat diakses karena
disimpan di RAM Internal 8051s. Hal ini juga jauh lebih fleksibel daripada
Segera Mengatasi karena nilai yang akan diambil adalah apa saja yang ditemukan
di alamat yang diberikan - yang mungkin variabel.
Juga, penting untuk dicatat bahwa bila menggunakan pengalamatan langsung suatu
instruksi yang merujuk ke alamat antara 00h dan 7Fh mengacu pada memori
internal. Setiap instruksi yang merujuk ke alamat antara 80h dan FFh merujuk ke
register kontrol SFR yang mengendalikan mikrokontroler 8051 itu sendiri.
Pertanyaan jelas yang mungkin timbul adalah, "Jika langsung menangani
alamat dari 80h sampai FFh mengacu pada SFRs, bagaimana saya bisa mengakses
bagian atas 128 byte Internal RAM yang tersedia pada 8052?" Jawabannya
adalah: Anda tidak bisa mengaksesnya menggunakan pengalamatan langsung.
Sebagaimana dinyatakan, jika Anda langsung merujuk pada alamat 80h melalui FFh
Anda akan mengacu pada suatu SFR. Namun, Anda dapat mengakses 8052s atas 128
byte RAM dengan menggunakan mode pengalamatan berikutnya, "tidak langsung
berbicara."
Randomizing Technique
Dalam ilmu komputer , fungsi pengacakan (Randomizing technique) atau mengacak
fungsi adalah algoritma atau prosedur yang menerapkan secara acak dipilih
fungsi antara dua spesifik set , cocok untuk digunakan dalam algoritma acak .
fungsi mengacak terkait dengan generator bilangan acak dan fungsi hash , namun
memiliki persyaratan agak berbeda, dan sering membutuhkan algoritma spesifik.
Fungsi mengacak digunakan untuk mengubah algoritma yang baik yang diharapkan
untuk kinerja input acak, menjadi algoritma yang memiliki kinerja yang sama
untuk masukan apapun.
Sebagai contoh, mempertimbangkan algoritma sorting seperti quicksort , yang
telah berjalan diharapkan menjadi kecil saat barang input disajikan secara
acak, tapi sangat lambat ketika mereka disajikan dalam perintah tertentu yang tidak
menguntungkan. Fungsi mengacak dari bilangan bulat 1 sampai n dengan bilangan
bulat 1 hingga n bisa digunakan digunakan untuk rerrange item n masukan dalam
"" urutan acak, sebelum memanggil algoritma itu. Ini diubah (acak)
algoritma akan punya waktu berjalan yang kecil, apa pun urutan yang kita
masukan.
Dalam teori, fungsi pengacakan diasumsikan benar-benar acak, dan hasil fungsi
tak terduga algoritma berbeda setiap kali dijalankan. Teknik pengacakan tidak
akan bekerja jika, pada setiap pelaksanaan algoritma pengacakan fungsi selalu
melakukan pemetaan yang sama, atau pemetaan sepenuhnya ditentukan oleh beberapa
parameter eksternal dapat diamati (seperti waktu startup program). Dengan
sebuah pengacakan "-pseudo" fungsi, seseorang bisa secara prinsip membangun
urutan fungsi telepon seperti yang selalu akan menghasilkan "buruk"
kasus untuk algoritma deterministik yang mendasarinya. Untuk itu urutan
panggilan, biaya rata-rata akan lebih dekat untuk biaya-kasus terburuk,
daripada biaya rata-rata untuk input acak.
Dalam prakteknya, Namun, perhatian utama adalah bahwa beberapa
"buruk" kasus untuk algoritma deterministik mungkin terjadi dalam
praktek jauh lebih sering daripada itu akan diprediksi secara kebetulan.
Misalnya, dalam varian naif dari quicksort, kasus terburuk adalah ketika
barang-barang input yang telah disortir - yang merupakan kejadian yang sangat
umum dalam berbagai aplikasi. Untuk algoritma tersebut, bahkan permutasi
pseudo-random tetap mungkin cukup baik. Meskipun "menghasilkan pseudo-acak"
algoritma masih akan memiliki banyak "buruk" kasus-kasus seperti
aslinya, mereka akan mengetahui perintah khusus yang akan sangat tidak mungkin
muncul dalam aplikasi nyata. Jadi, dalam satu praktek sering menggunakan fungsi
pengacakan yang berasal dari nomor acak generator-pseudo , sebaiknya unggulan
dengan eksternal "acak" data seperti's waktu startup program.
Hashing
Keuntungan pemakaian Hashing :
Nilai key yang sebenarnya dapat dipakai karena diterjemahkan kedalam sebuah alamat.
Nilai key adalah address space independent bila berkas direorganisasi, fungsi hash berubah tetapi nilai key tetap.
Kelemahannya :
Membutuhkan waktu proses dalam mengimplementasikan fungsi hash.
Membutuhkan waktu proses dan akses I/O dalam mengatasi benturan.
Hashing dapat digunakan bersama-sama dengan pencarian tabel.
Penampilan fungsi hash bergantung pada :
Distribusi nilai key yang dipakai.
Banyaknya nilai key yang dipakai relatif 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
Division Remainder
Pada division remainder, alamat relatif dari suatu nilai key merupakan sisa
dari hasil pembagian nilai key tersebut dengan suatu bilangan yang disebut
sebagai bilangan pembagi.
Contoh :
Bila DIV adalah pembagi, KEY adalah nilai key dan ADDR adalah alamat relatif,
maka dalam bahasa Pascal, fungsi R(NILAI KEY) ADDRESS dapat di implementasikan
:
ADDR := KEY MOD DIV
Dalam bahasa COBOL :
DIVIDE KEY BY DIV GIVING TEMP REMAINDER ADDR
Sisa pembagian (Sebagai hasil dari fungsi MOD pada Pascal), dapat dijabarkan
sebagai berikut :
ADDR := KEY - DIV * TEMP
ADDR Harus merupakan bilangan integer.
Banyak faktor yang harus dipertimbangkan dalam pemilihan pembagi :
Jangkauan dari nilai key yang dihasilkan dari opersi KEY MOD DIV adalah 0 sampai DIV-1. Nilai dari DIV menentukan ukuran "relatif address space". Jika diketahui berkas relatif terdiri dari N record dan dianggap hanya satu record dapat disimpan dalam sebuah alamat relatif, maka akan didapat DIV > N.
Pembagi harus diseleksi untuk mengurangi benturan. Penyelidikan menunjukkan bahwa pembagi yang berupa bilangan genap akan cenderung jelek, terutama dengan nilai key-nya yang dominan ganjil.
Menurut riset dari W.Buchholz, sebaiknya pembagi itu merupakan bilangan prima. Tetapi riset lain dari V.Y.Lum, menyatakan pembagi yang bukan bilangan prima akan memberikan hasil yang sama baik seperti bilangan prima.
Menurut pendapatnya, bukan bilangan prima yang mempunyai faktor prima kurang dari 20 akan dapat memberikan jaminan penampilan yang lebih baik.
Walaupun kita telah menentukan pembagi dengan baik untuk mengatasi benturan, bila ruang alamat dari berkas relatif mendekati penuh, maka peluang terjadinya benturan akan meningkat.
Untuk mengukur kepenuhan berkas relatif digunakan Load Factor (Faktor Muat).
Load Factor = banyak record dalam berkas dibagi max. banyak record dalam berkas
Biasanya load factor yang sering digunakan adalah 0.7 atau 0.8.
Jika load factor lebih besar dari 0.7 atau 0.8 maka berkas tersebut harus
diperbesar dan direorganisasi.
Jadi jika kita ingin menyimpan sebanyak n record pada suatu berkas dan load
factor adalah 0.8, maka max. banyak record pada berkas adalah 1.25 n.
Contoh
:
Kita ingin membuat berkas yang terdiri dari 4000 record.
Load Factor (Faktor muat) = 0.8
maka max. banyak record pada berkas :
(1.25) n = (1.25) . 4000
= 5000
Bilangan pembagi : 5003
Mid Square Hashing
Untuk mendapatkan alamat relatif, nilai key dikuadratkan, kemudian beberapa
digit diambil dari tengah .
Dari nilai key yang dikuadratkan kita cari tengah-tengahnya.
Jumlah nilai key yang dikuadratkan, dari nilai key 123456789 = 17 digit.
Kita
mulai dari digit ke 8 dihitung dari kiri, maka alamat relatif = 8750
(karena ditentukan 4 digit sebagai alamat relatif).
Hashing by folding
Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian,
setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan
alamat relatif.
Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah.
Hasilnya, digit yang tertinggi dibuang (bila diperlukan).
Contoh :
Nilai key 123456789 dan alamat relatif sebanyak 4 digit. Nilai key dibagi
menjadi bagian-bagian yang terdiri dari 4 digit, mulai dari sebelah kanan.
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
Menghasilkan :
1
2 3 4 5
9 8 7 6 +
_______
1 3 2 2 1 alamat relatif
Perbandingan Fungsi Hash
Teknik Division Remainder memberikan penampilan yang terbaik secara keseluruhan.
Teknik Mid Square dapat dipakai untuk file dengan load factor cukup rendah akan memberikan penampilan baik tetapi kadang-kadang dapat menghasilkan penampilan yang buruk dengan beberapa collision.
Teknik folding adalah teknik yang paling mudah dalam perhitungan tetapi dapat memberikan hasil yang salah, kecuali panjang nilai key = panjang address.
Scatter Storage
Sebuah cara melihat organisasi tersebar penyimpanan tabel (Tabel hash) sebagai
pohon biner disajikan. sudut pandang ini menyebabkan langsung ke algoritma untuk
memasukkan entri baru dalam tabel tersebut, yang diharapkan menghasilkan lebih
rendah daripada yang lain kali pengambilan sebanding metode, terutama jika meja
hampir penuh. Hal ini ditunjukkan bagaimana metode ini subsumes kedua metode
sebelumnya (seperti linear hasil bagi) dan metode perbaikan yang diusulkan oleh
Brent pada tahun 1973. Hasil percobaan Monte Carlo dan dari analisis teoretis
mengkonfirmasi manfaat dari metode yang diusulkan.
Demikian tugas kami yang telah dibuat. Mohon maaf apabila ada salah - salah kata. Terima Kasih.
Tidak ada komentar:
Posting Komentar