Macam-Macam Fungsi Hash Abas Ali Pangera, Dony Ariyus, Jurusan Teknik Informatika, STMIK AMIKOM Yogyakarta, Jl. Ring Road Utara, Condong Catur, Sleman, Yogyakarta - Indonesia Fungsi hash terdapat empat macam diantaranya: 1. Fungsi Modulo: Home address dicari dengan cara mencari sisa hasil bagi nilai kunci dengan suatu nilai tertentu f (key) → key mod n Dengan nilai n dapat berupa 2 kemungkinan, yaitu : – Banyaknya ruang alamat yang tersedia – Bilangan prima terdekat yang berada di atas nilai banyaknya data, setelah itu banyaknya ruang alamat disesuaikan dengan n 2. Metode Pemotongan: Home address dicari dengan memotong nilai kunci ke jumlah digit tertentu yang lebih pendek 3. Metode Pelipatan: Diandaikan kunci rekaman ditulis di atas kertas dan dilipat ke dalam bagian-bagian yang sama panjang, lalu setiap bagian dijumlahkan 4. Metode Pengkuadratan: Home address dicari dengan mengkuadratkan setiap digit pembentuk kunci, lalu semua hasilnya dijumlahkan 5. Penambahan Kode ASCII: Metode ini dapat digunakan jika kunci bukan berupa kode numerik. Home address dicari dengan menjumlahkan kode ASCII setiap huruf pembentuk kunci. Dengan menggunakan metode hashing, maka secara otomatis hubungan korespondensi satu satu antara kunci rekaman dengan alamat rekaman menjadi hilang. Selalu ada kemungkinan terjadinya peristiwa dimana terdapat dua buah rekaman dengan kunci yang berbeda namun memiliki home address yang sama, Kejadian ini dinamakan sebagai Collision atau Tabrakan atau Tumbukan Kriteria fungsi hash yang baik harus memiliki: y Dapat mendistribusikan setiap rekaman secara merata, sehingga dapat meminimalkan terjadinya collision y Dapat dieksekusi dengan efisien, sehingga waktu tidak habis hanya untuk menghitung home address saja Karena collision dapat dipastikan akan selalu terjadi, maka dikatakan bahwa output dari fungsi hash (home address) bukanlah merupakan alamat unik yang pasti ditempati oleh rekaman yang diproses, namun hanya berupa kemungkinan alamat yang bisa ditempati. Jika home address dari suatu rekaman ternyata sudah ditempati rekaman lain, maka harus dicarikan alamat lain untuk ditempati rekaman tersebut. Proses pencarian alamat lain ini dinamakan sebagai Collision Resolution, Metode Collision Resolution terdiri dari • Metode Coalesced Hashing • Metode LICH dan EISCH • Metode Progressive-overflow • Metode Bucket • Metode Pembagian Linear Metode Coalesced Hashing
Metode resolusi yang menggunakan penunjuk untuk menghubungkan elemen-element dari sebuah rantai sinonim. Coalesced hashing terjadi bila terdapat usaha untuk menyisipkan sebuah rekaman dengan home address yang sudah diokupasi oleh rekaman dari rantai yang memiliki home address yang berbeda Algoritma Coalesced Hashing • Lakukan hashing pada semua kunci rekaman yang akan disisipkan untuk mendapatkan home address • Jika home address kosong, sisipkan rekaman pada lokasi tersebut, jika rekaman kembar akhiri program dengan pesan rekaman kembar jika tidak – Cari lokasi terakhir rantai sinonim dengan mengikuti penunjuk pada meda penghubung – Cari lokasi paling bawah dalam berkas, jika tidak ditemukan akhiri program dengan pesan”berkas penih” – Sisipkan rekaman ke dalam lokasi yang kosong sudah teridentifikasi dan atur medan penghubung rekaman terakhir dalam rantai sinonim agar menunjuk ke lokasi rekaman yang baru saja disisipkan Misalnya dilakukan penyisipan rekaman dengan kunci: 38, 51, 40,61,83,24 dan 60 ke dalam berkas dengan kapasitas 11
Penjelasan algoritma: • 38 mod 11 = 5, jadi kunci 38 diletakan pada alamat ke lima •
51 mod 11=7, jadi kunci 51 diletakan pada alamat ketujuh
•
40 mod 11=7, karena alamat ketujuh telah diisi oleh 51, maka kunci 40 mencari rantai terakhir dari sinonim yaitu 10, 40 diletakan pada alamat ke 10 dengan memberi medan penghubung pada alamat ketujuh, bahwa keberadaan 40 bukan pada alamat ke tujuh melainkan pada alamat kesepuluh
•
61 mod 11=6, karena alamat keenam masih kosong maka, 61 diletakan pada alamat keenam
•
83 mod 11=6, karena 6 telah diisi oleh 61, maka kunci 83 diletakkan pada alamat terakhir pada rantai sinonim yang paling besar dan masih kosong, karena alamat 10 telah diisi oleh 40 maka, alamat terbesar yang masih kosong adalah 9, maka 83 disisipkan pada alamat kesembilan
•
24 mod 11=2, karena alamat kedua masih kosong, maka 24 langsung disisipkan
•
60 mod 11=5, karena alamat 5 telah ditempati oleh 38, maka 60 diletakan pada rantai sinonim yang paling besar dan masih kosong, alamat kesepuluh dan sembilan telah ditempati, maka alamat terbesar yang masih kosong adalah 8, maka 60 ditempatkan pada alamat tersebut.
Probe rata-rata dari kunci di atas dengan menggunakan algoritma Coalesced hashing adalah sebagai berikut:
Berbagai usaha telah dilakukan untuk mengurangi koalisi pada rantai sinonim untuk mengurangi probe sehingga bisa meningkatkan kinerja. Varian dari coalesced hashing • Mengorganisasikan berkas (dengan atau tanpa overflow) • Menghubungkan item yang terkoalisi ke dalam rantai • Memilih lokasi yang belum ada penghuninya Koalisi dapat dikurangi dengan memodifikasi organisasi berkas dengan cara memisahkan antara area untuk data prime dengan area untuk data overflow dengan bentuk seperti: • Area prime adalah ruang alamat yang cocok dengan fungsi hash • Overflow adalah area yang hanya berisi rekaman yang bersinonim Dengan menggunakan Rumus •
• •
Jika faktor alamat mengecil maka ukuran overflow akan meningkat Jika ruang alamat kecil dan overflow besar akan banyak terdapat probe pembacaan yang lebih besar. Maka diperlukan suatu algoritma untuk mengatasi masalah tersebut seperti : – LICH (Late Insertion Standard Coalesced hashing) – EISCH ( early insertion standard coalesced hashing )
Metode LICH dan EISCH LICH (Late Insertion Standard Coalesced hashing) y Rekaman yang baru disisipkan pada akhir rantai sinomim y Kata standar memiliki arti tidak adanya overflow y Misalnya akan dilakukan penyisipan rekaman dengan kunci 48,51,40,61,83,24 dan 60 ke dalam berkas dengan kapasitas 11
Probe rata-rata dari algoritma ini adalah:
EISCH (early insertion standard coalesced hashing) y Menyisipkan rekaman baru pada posisi rantai sinonim tepat sesudah rekaman yang disimpan pada home address
y Medan penghubung yang berada pada home address diarahkan ke rekaman yang baru saja disimpan y Dilakukan penyisipan rekaman dengan kunci 38,51,40,61,83,24, 60, 20 dan 94 ke dalam berkas dengan kapasitas 11
Probe rata-rata dari algoritma ini adalah:
Metode Progressive Overflow • Kerugian dari coalesced hashing adalah diperlukan penyimpanan tambahan untuk medan penghubung, bila penyimpanan tambahan tidak tersedia, maka penghubung yang bersifat fisik tidak tersedia • Perlu dipertimbangkan teknik resolusi kolusi yang menggunakan konversi untuk menentukan kemana rekaman harus dicari • Coba bayangkan jika terjadi overflow, dan diambil alamat paling terakhir pada berkas • Metode progressive overflow, bila lokasi yang akan ditempati telah terisi maka lokasi selanjutnya dilihat apakah belum ditempati Disisipkan rekaman dengan kunci 38, 51,40,61,83,24,60,20 dan 94 pada berkas dengan kapasitas 11 maka Hash (kunci) = kunci modulus 11
Probe rata-rata menggunakan algoritma ini adalah:
Kelemahan dari metode progressive overflow adalah rata-rata probe yang sangat tinggi dari metode sebelumnya, oleh sebab itu tidak tepat untuk mereduksi kolusi bagaimanapun metode ini lebih efektif dibandingkan dengan berkas sekuensial. jika pada metode ini, untuk menghapus pesan diberi tanda “tombstone” pada posisi rekaman yang dihapus Metode Bucket • Bucket adalah unit penyimpanan yang berada diantara rekaman dengan berkas, juga sebuah unit dengan informasi yang dapat diakses dan dipindahkan antara peralatan penyimpanan • Jumlah rekaman yang diletakkan pada suatu bucket disebut dengan faktor-blocking • Jika faktor blocking meningkat jumlah akses terhadap penyimpanan akan mengecik karera rekaman yang akan berkolisi dapat disimpan dalam sutu alamat yang sama
Disisipkan rekaman dengan kunci 38, 51,40,61,83,24,60,20 dan 94 pada berkas dengan kapasitas 11 dan raktor blocking =2 maka fungsi hashnya Hash (kunci) = kunci modulus 11
Probe rata-rata pada algoritma ini adalah:
Metode Pembagian Linear y Pembagian linear merupakan varian dari progressive overflow y pada progressive overflow inkremen untuk menuju ke lokasi berikutnya adalah konstant 1 y pada pembagian linear bersifat variable
Algoritma Pembagian Linear • Hash kunci yang akan disisipkan ke dalam berkas untuk memperoleh home address untuk menyimpan berkas • Jika home address kosong, sisipkan rekaman ke dalam lokasi tersebut jika tidak maka: – Tentukan inkremen dengan menghitung hasil bagi kunci dengan ukuran berkas, jika hasilnya nol, maka inkremennya adalah = 1 – Beri harga awal pencacah untuk menghitung lokasi yang akan dicari dengan 1 – Selama jumlah lokasi yang dicari lebih kecil dari pada ukuran berkas maka: • Hitung alamat yang akan dicari berikutnya dengan menambahkan inkremen terhadap alamat terakhir dan kemudian cari modulusnya terhadap ukuran berkas
•
Jika alamat tersebut tidak ada yang menempati, maka sisipkan rekaman serta akhiri penyisipan dengan sukses • Jika rekaman yang menempati memiliki kunci yang sama dengan yang akan disisipkan , akhiri proses dengan pesan “rekaman dobel” • Tambahkan 1 pada pencacah pencarian lokasi – Akhiri proses dengan pesan “berkas penuh” Disisipkan rekaman dengan kunci 38, 51,40,61,83,24,60,20 dan 94 pada berkas dengan kapasitas 11, maka Fungsi hashnya adalah 11
Probe rata-rata pada metode ini adalah:
Daftar Pustaka Ariyus,Dony,2006, “Computer Security”, Andi Offset, Yogyakarta Ariyus, Dony,2005,” kamus hacker”, Andi offset, Yogyakarta Bob DuCharme, 2001,” The Operating System Handbook or, Fake Your Way Through Minis and Mainframes” Singapore: McGraw-Hill Book Co Bill Venners.1998. “Inside the Java Virtual Machin”e . McGraw-Hill. Deitel, Harvey M, 2004 “ operating systems” 3th Edition, Massachusetts: Addison-Wesley Publshing Company Gary B. Shelly, 2007, ”Discovering Computers: Fundamentals” Thomson Gollmann, Dieter,1999 “Computer Security” Jhon Willey & Son Inc, Canada Grosshans,D. 1986,” File system: design and implementation”, Englewwod Cliffs, New Jersey : Prentice-Hall Inc. Harvey M Deitel dan Paul J Deitel. 2005. Java How To Program. Sixth Edition. Prentice Hall. Hoare, C.A.R. 1985” Communication sequential processes”Englewood Cliffs, New Jersey, Prentice Hall Inc Jean Bacon, Tim Harris, 2003 “Operating Systems: Concurrent and Distributed Software Design” Massachhussets. Addison Wesley Kenneth H Rosen. 1999. “Discrete Mathematics and Its Application”. McGraw Hill. Madnick,Stuart E dan John J. Donovan, 1974 “ operating system”, Singapore: McGraw-Hill Book Co Michael Kifer and Scott A. Smolka, 2007 Introduction to Operating System Design and Implementation The OSP 2 Approach, Springer-Verlag London Microsoft 1999. Microsoft Windows User Experience. Microsoft Press. Milenkovie, Milan. 1992. “Operationg system: Concepts and Design”, Singapore: McGraw-Hill Book Co Randall Hyde. 2003. The Art of Assembly Language. First Edition. No Strach Press Robert betz, 2001 “Intoduction to Real-time operation system”, Department of Electrical and Computer Engineering University of Newcastle, Australia
Robert Love. 2005. Linux Kernel Development . Second Edition. Novell Press Ron White,1998, How Computers Work, Fourth Edition, Que corporation, A Division of Macmillan Computer Publishing, USA Shay, William A. 1993, “ Introduction to Operationg System” New York: HarperCollins College Publishers Silberschatz, Peter Galvin, dan Grag Gagne. 2000. “Applied Operating System, 1s”t “ John Wile & Hiil Book Co Silberschatz, A., dan Galvin, P.2003, “Operating Sistem Concept. Sixth Edition”. Massachhussets. Addisson- Wasley Silberschatz, Peter Galvin, dan Grag Gagne. 2005. “Operating Systems Concepts”. Seventh Edition. John Wiley & Sons. Stalling, William, 1995, “Operating Sistems”. New Jersey. Prentice – Hall Stalling, William, 1996” Computer Organization and Architecture”. New Jersey. Prentice – Hall Stalling William, 1995, “Network and Internetwork Security” Prentice-Hall, USA Tanenbaum, Andrew S, 1992 “Modern Operating Sistems”. New Jersey. Prentice – Hall Taenbaum, Andrew S, 2006, “Operating Systems Design and Implementation, Third Edition” Massachusetts
