Macam-Macam Hasing

Hai teman teman, hari ini penulis akan ngeblog nihhh.. pada nungguinkan. Hehe, becanda. Disini penulis akan nge-blog tentang organisasi file secara langsung yang lebih spesifik lagi ke macam macam hasing, yang minggu lalu jadi topik di kuliah sistem berkas. Yuk dicek >>

Organisasi Berkas Secara Langsung

Macam –Macam Hashing

Hash Function adalah Sebuah fungsi matematis yang melakukan konversi terhadap string masukan yang panjang menjadi menjadi string lain dengan panjang yang selalu sama, tidak bergantung pada panjang stringmasukannya, dan biasanya dengan ukuran yang jauh lebih kecil daripada string masukannya. Fungsi hash pada umumnya digunakan untuk mempercepat table look-up, atau untuk membandingkan data (misalnya mencari data tertentu dalam sebuah basis data, mendeteksi data yang terduplikasi dalam sebuah file berukuran besar, dan sebagainya).

Pada era saat ini ada berbagai macam hash function yang sudah ada dan sering digunakan diantaranya :

a. Fungsi modulo

- Home address dicari dengan cara mencari sisa hasil bagi nilai key dengan suatu nilai tertentu.

- Fungsi: f(key) = key mod n

- Dengan n adalah:

** Banyaknya ruang alamat yang tersedia

** Atau bilangan prima terdekat yang berada di atas nilai banyak data,setelah itu banyaknya ruang alamat disesuaikan dengan n

Jumlah lokasi memori yang tersedia dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya.

Secara umum, rumusnya

h(k)= k mod m.

Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hashtersebut menempatkan record dengan kunci k pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.

b. Fungsi Pemotongan

- Home address dicari dengan memotong nilai key ke jumlah digit tertentu yang lebih pendek.

- Contoh: NIM yang tadinya 9 digit, dipotong hanya menjadi 3 digit!

c. Fungsi Pelipatan

- Dilakukan pelipatan terhadap record key dengan bagian yang sama panjang, lalu setiap bagian dijumlahkan

- NIM 8 digit dibagi dua digit, hingga menjadi 4 buah.

- Misal: 22002521, dibagi 22 00 25 21 kemudian dijumlahkan: 68

Metode ini membagi nilai asli ke dalam beberapa bagian, kemudian menambahkan nilai-nilai tersebut, dan mengambil beberapa angka terakhir sebagai nilai hashnya

d. Fungsi Pengkuadratan

- Home address dicari dengan mengkuadratkan setiap digit pembentuk key, lalu semua hasilnya dijumlahkan

- Contoh: 22002211, semua digit dikuadratkan dan dijumlah

e. Fungsi Penambahan Kode ASCII

- Jika key bukan kode numerik, home address dicari dengan menjumlahkan kode ASCII setiap huruf pembentuk key

ADE = 65 + 68 + 69 = 192

Contoh Soal :

1.      Berapa home address dan rekaman rekaman dengan kunci tiga digit nim terakhir anda bila diketahui berkas memiliki kapasitas 11 rekaman (N=11)

2.      Carilah home address NIM anda masing masing dengan ketentuan :

a.       Hasing dengan pemotongan (3 digit terakhir)

b.      Hasing dengan lipatan (bagi 3 lipatan) tentukan home address dengan dan tanpa carrie

c.       Hasing dengan pengkuadratan

d.      Hasing dengan penjumlahan code ASCII

Jawab :

Maaf ya, jika tulisannya sulit terbaca. Semoga bermanfaat teman teman ^^