Struktur Data : Hash Table

Posted on

1.      Hash table adalah Hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Menurut bahasanya, hash berarti memenggal dan kemudian menggabungkan. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat.

2.      Keunggulan dari implementasi  hash  table : menggunakan  binary search  tidak  akan  terlihat  dengan  jelas. Akan   tetapi ,  pada kasus dengan  jumlah  record  yang sangat  besar, lebar lokasi penyimpanan yang kecil,  dan banyaknya  record  yang  mempunyai  angka hash   yang sama, pengimplementasian  binary  search   dapat mengefisienkan waktu dengan perbedaan waktu akses yang  lebih cepat  dari pada  menggunakan  metode  standar  hash table.

Hash Table dengan link List
Pada struktur   linked list, selain disimpan   data  record yang dimasukan,  disimpan  juga   field   kunci yang dihasilkan  dari  rumus  (1 ). Metode penyimpanan pada struktur  ini berupa terurut menaik berdasar  field   kunci yang  disimpan.
Metode penyimpanan  record  pada struktur  baru  ini agak  berbeda dengan metode penyimpanan pada struktur  hash  table  standar,  namun metode ini masih  menggunakan keunggulan  dari  hash  table  yaitu  pembangkitan kunci dan penggunaan  hash function untuk menentukan  lokasi  record dalam  tabel.
4. Ada beberapa macam fungsi/metode hash  yang relatif sederhana yang dapat digunakan dalam penyimpanan database :
a. Metode Pembagian Bersisa (division-remainder method)
Jumlah lokasi memori yang tersedi 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 hash  tersebut 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. Melipat (folding)
Metode ini membagi nilai asli ke dalam beberapa bagian, kemudian menambahkan nilai-nilai tersebut, dan mengambil beberapa angka terakhir sebagai nilai hashnya.
c. Transformasi Radiks (radix transformation)
Karena nilai dalam bentuk digital, basis angka  atau radiks dapat diganti sehingga menghasilkan urutan angka-angka yang berbeda. Contohnya nilai desimal (basis 10) bisa ditransformasikan kedalam heksadesimal (basis 16). Digit atas hasilnya bisa dibuang agar panjang nilai hash dapat seragam.
d. Pengaturan ulang digit (digit rearrangement)
Metode ini mengubah urutan digit dengan pola tertentu. Contohnya mengambil digit ke tiga sampai ke enam dari nilai aslinya, kemudian membalikan urutannya dan menggunakan digit yang terurut terbalik itu sebagai nilai  hash. Fungsi  hash  yang bekerja dengan baik untuk penyimpanan pada database belum tentu bekerja dengan baik untuk keperluan kriptografi atau pengecekan kesalahan. Ada beberapa fungsi hash terkenal yang digunakan untuk keperluan kriptografi. Diantaranya adalah fungsi hash message-diggest, contohnya MD2, MD4, dan MD5, digunakan untuk menghasilkan nilai  hash  dari tanda tangan digital yang disebut message-diggest. Ada pula Secure Hash Algorithm (SHA), sebuah algoritma standar yang menghasilkan message-diggest yang lebih besar (60-bit) dan serupa dengan MD4

contoh hash table :
1. program hash table 1
2. program hash table 2

Gravatar Image
Suka jalan-jalan, naik sepeda, bermain code-code asal tidak suka mengkode cinta. Hubungi email : andhika.na@gmail.com jika anda butuh website untuk personal maupun bisnis.

One thought on “Struktur Data : Hash Table

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.