Anggota:
Lucky Rahmadeni :50408961
Handi :50408410
Arry Ardiantara :50408163
Yugi Safari Nurhakim :50408890
*Hash Table
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:
1. 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,
(B) mengakses posisi nomor dalam array data karakter pertama kunci numerik menggunakan setara unik dan modul panggilan,
(C) 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,
(D) iteratif menerjemahkan setiap data karakter kunci menjadi karakter acak baru dengan menggunakan modul menelepon, modul hashing, dan langkah-langkah (b) dan (c),
(E) 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,
(F) menggabungkan dan scaling karakter komposit sehingga setara numerik diperoleh dengan menggunakan operasi yang telah ditentukan untuk menghasilkan alamat memori data, dan
(G) 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
.jpg)
• 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.
.jpg)
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.
itulah Materi yang kami dapat, mohon maklum apabila ada kekurangan, dan terima kasih sudah mau meluangkan waktu anda.
Read More.. Read More..
