Pengertian Hashing
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. Ide dasarnya adalah menghitung posisi record yang dicari dalam array,
bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau
kunci disebut fungsi hash (hash function) dan array yang digunakan disebut tabel hash (hash
table). Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record
dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record
tersebut.
Secara teori, kompleksitas waktu (T(n)) dari fungsi hash yang ideal adalah O(1). Untuk
mencapai itu setiap record membutuhkan suatu kunci yang unik. Fungsi hash menyimpan nilai
asli atau kunci pada alamat yang sama dengan nilai hashnya. Pada pencarian suatu nilai pada
tabel hash, yang pertama dilakukan adalah menghitung nilai hash dari kunci atau nilai aslinya,
kemudian membandingkan kunci atuau nilai asli dengan isi pada memori yang beralamat nomor
hashnya. Dengan cara ini, pencarian suatu nilai dapat dilakukan dengan cepat tanpa harus
memeriksa seluruh isi tabel satu per satu.
Selain digunakan pada penyimpanan data, fungsi hash juga digunakan pada algoritma
enkripsi sidik jari digital (fingerprint) untuk mengautentifikasi pengirim dan penerima pesan.
Sidik jari digital diperoleh dengan fungsi hash, kemudian nilai hash dan tanda pesan yang asli
dikirim kepada penerima pesan. Dengan menggunakan fungsi hash yang sama dengan pengirim
pesan, penerima pesan mentransformasikan pesan yang diterima. Nilai hash yang diperoleh oleh
penerima pesan kemudian dibandingkan dengan nilai hash yang dikirim pengirim pesan. Kedua
nilai hash harus sama, jika tidak, pasti ada masalah.
Hashing selalu merupakan fungsi satu arah. Fungsi hash yang ideal tidak bisa diperoleh
dengan melakukan reverse engineering dengan menganalisa nilai hash. Fungsi hash yang ideal
juga seharusnya tidak menghasilkan nilai hash yang sama dari beberapa nilai yang berbeda .
Jika hal yang seperti ini terjadi, inilah yang disebut dengan bentrokan (collision). Kemungkinan
terjadinya bentrokan tidak dapat dihindari seratus persen. Fungsi hash yang baik dapat
meminimalkan kemungkinan terjadinya bentrokan.
2. Macam - Macam Fungsi Hash
Fungsi Hash (dilambangkan dengan h(k)) bertugas untuk mengubah k (key) menjadi
suatu nilai dalam interval [0....X], dimana "X" adalah jumlah maksimum dari record-record
yang dapat ditampung dalam tabel. Jumlah maksimum ini bergantung pada ruang memori yang
tersedia. Fungsi Hash yang ideal adalah mudah dihitung dan bersifat random, agar dapat
menyebarkan semua key. Dengan key yang tersebar, berarti data dapat terdistribusi secara
seragam bentrokan dapat dicegah. Sehingga kompleksitas waktu model Hash dapat mencapai
O(1), di mana kompleksitas tersebut tidak ditemukan pada struktur model lain.
Ada beberapa macam fungsi 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 messagediggest.
Ada pula Secure Hash Algorithm (SHA), sebuah algoritma standar yang menghasilkan
message-diggest yang lebih besar (60-bit) dan serupa dengan MD4.
3. Bentrokan Pada Fungsi Hash
Fungsi hash bukan merupakan fungsi satu-ke-satu, artinya beberapa record yang
berbeda dapat menghasilkan nilai hash yang sama / terjadi bentrokan. Dengan fungsi hash yang
baik, hal seperti ini akan sangat jarang terjadi, tapi pasti akan terjadi. Jika hal seperti ini terjadi,
record-record tersebut tidak bisa menempati lokasi yang sama. Ada dua macam kebijakan
resolusi bentrokan pada tabel hash, yaitu kebijakan resolusi bentrokan di luar tabel dan
kebijakan resolusi bentrokan di dalam tabel. Harus diperhatikan juga teknik-teknik penempatan
record agar mudah dicari jika dibutuhkan.
Kebijakan resolusi bentrokan di luar tabel
Artinya tabel hash bukan lagi menjadi array of records, tetapi menjadi array of
pointers. Setiap pointer menunjuk ke senarai berkait yang berisi record tersebut. Metode seperti
ini dinamakan chaining. Dalam bentuk sederhananya berupa senarai berkait dari recordrecord
yang menghasilkan nilai hash yang sama. Penambahan record dapat dilakukan dengan
menambah senarai berisi record tersebut. Untuk pencarian pada tabel, pertama-tama dicari nilai
hash terlebih dahulu, kemudian dilakukan pencarian dalam senarai berkait yang bersangkutan.
Untuk menghapus suatu record, hanya menghapus senarainya saja.
Kelebihan dari metode chaining ini chaining ini adalah proses penghapusan yang relarif
mudah dan penambahan ukuran tabel hash bisa ditunda untuk waktu yang lebih lama karena
penurunan kinerjanya berbanding lurus meskipun seluruh lokasi pada tabel sudah penuh.
Bahkan, penambahan ukuran tabel bisa saja tidak perlu dilakukan sama sekali karena penurunan
kinerjanya yang linier. Misalnya, tabel yang berisi record sebanyak dua kali lipat kapasitas yang
direkomendasikan hanya akan lebih lambat dua kali lipat dibanding yang berisi sebanyak
kapasitas yang direkomendasikan. Kekurangan dari metode chaining ini sama dengan
kekurangan dari senarai berkait. Operasi traversal pada senarai berkait memiliki performa cache
yang buruk.
Struktur data lain dapat digunakan sebagai pengganti senarai berkait. Misalnya dengan
pohon seimbang, kompleksitas waktu terburuk bisa diturunkan menjadi O(log n) dari yang
sebelumnya O(n). Namun demikian, karena setiap senarai diharapkan untuk tidak panjang,
struktur data pohon ini kurang efisien kecuali tabel hash tersebut memang didesain untuk
jumlah record yang banyak atau kemungkinan terjadi bentrokan sangat besar yang mungkin
terjadi karena masukan memang disengaja agar terjadi bentrokan.
Kebijakan resolusi bentrokan di dalam tabel
Berbeda dengan kebijakan resolusi bentrokan di luar tabel, pada kebijakan resolusi di
dalam tabel data disimpan di dalam hash tabel tersebut, bukan dalam senarai berkait yang bisa
bertambah terus menerus. Dengan demikian data yang disimpan tidak mungkin bisa lebih
banyak daripada jumlah ruang pada tabel hash. Jika suatu record akan dimasukkan ke dalam
tabel hash pada lokasi sesuai nilai hash-nya dan ternyata lokasi tersebut sudah diisi dengan
record lain maka harus dicari lokasi alternatif yang masih belum terisi dengan cara tertentu.
Cara ini disebut Open Addressing.
Ada beberapa metode untuk menemukan lokasi baru yang masih kosong. Dalam proses
menemukan lokasi baru ini harus menggunakan pola tertentu agar record yang disimpan tetap
bisa dicari dengan mudah saat dibutuhkan kemudian.
Metode-metode yang sering digunakan adalah:
1. Linear probing
Dengan menambahkan suatu interval pada hasil yang diperoleh dari fungsi hash sampai
ditemukan lokasi yang belum terisi. Interval yang biasa digunakan adalah 1.
Gambar 2. Resolusi bentrokan dengan Linear Probing
2. Quadratic probing / squared probing
Hampir sama dengan linear probing, hanya saja pada quadratic probing, hasil yang
diperoleh dari fungsi hash ditambahkan dengan kuadrat dari interval yang digunakan.
3. Double hashing
Pada metode double hashing, jika lokasi yang diperoleh dengan fungsi hash sudah
terisi, maka dilakukan proses hash lagi sampai ditemukan lokasi yang belum terisi.
Perbandingan antara metode chaining dan open addressing
Keunggulan metode chaining dibanding open addressing:
1. Lebih mudah diimplementasikan dengan efektif dan hanya membutuhkan struktur data dasar.
2. Metode chaining tidak rawan terhadap data-data yang berkumpul di daerah tertentu. Metode
open addressing membutuhkan algoritma hash yang lebih baik untuk menghindari
pengumpulan data di sekitar lokasi tertentu.
3. Performa menurun secara linier. Meskipun semakin banyak record yang dimasukkan maka
semakin panjang senarai berantai, tabel hash tidak akan penuh dan tidak akan menimbulkan
peningkatan waktu pencarian record yang tibatiba meningkat yang terjadi bila menggunakan
metode open addressing.
4. Jika record yang dimasukkan panjang, memori yang digunakan akan lebih sedikit
dibandingkan dengan metode open addressing.
Gambar 3. Perbandingan waktu yang diperlukan untuk melakukan pencarian. Saat tabel
mencapai 80% terisi, kinerja pada linear probing(open addressing)menurun drastis.
Untuk ukuran record yang kecil, keunggulan metode open addressing dibandingkan dengan
chaining diantaranya
a. Ruang yang digunakan lebih efisien karena tidak perlu menyimpan pointer atau mengalokasi
tempat tambahan di luar tabel hash.
b. Tidak ada waktu tambahan untuk pengalokasian memori karena metode open addressing
tidak memerlukan pengalokasian memori.
c. Tidak memerlukan pointer.
Sebenarnya, penggunaan algoritma apapun pada tabel hash biasanya cukup cepat, dan
persentase kalkulasi yang dilakukan pada tabel hash rendah. Penggunaan memori juga jarang
berlebihan. Oleh karena itu, pada kebanyakan kasus, perbedaan antar algoritma ini tidak
signifikan.
Metode-metode lain
Selain metode-metode yang sudah disebutkan di atas, ada juga beberapa metode lain
diantaranya :
1. Coalesced hashing
Gabungan dari chaining dan openaddressing. Coalesced hashing menghubungkan ke
tabel itu sendiri. Seperti open addressing, metode ini memiliki keunggulan pada penggunaan
tempat dan cache dibanding metode chaining. Seperti chaining, metode ini menghasilkan lokasi
penyimpanan yang lebih menyebar, tetapi pada metode ini record yang disimpan tidak mungkin
lebih banyak daripada ruang yang disediakan tabel.
2. Perfect hashing
Jika record yang akan digunakan sudah diketahui sebelumnya, dan jumlahnya tidak
melebihi jumlah ruang pada tabel hash, perfect hashing bisa digunakan untuk membuat tabel
hash yang sempurna, tanpa ada bentrokan.
3. Probabilistic hashing
Kemungkinan solusi paling sederhana untuk mengatasi bentrokan adalah dengan
mengganti record yang sudah disimpan dengan record yang baru, atau membuang record yang
baru akan dimasukkan. Hal ini bisa berdampak tidak ditemukannya record pada saat pencarian.
Metode ini digunakan untuk keperluan tertentu saja.
4. Robin Hood hashing
Salah satu variasi dari resolusi bentrokan double hashing. Ide dasarnya adalah sebuah
record yang sudah dimasukkan bisa digantikan dengan record yang baru jika nilai pencariannya
(probe count – bertambah setiap menemukan termpat yang sudah terisi) lebih besar daripada
nilai pencarian dari record yang sudah dimasukkan. Efeknya adalah mengurangi kasus terburuk
waktu yang diperlukan untuk pencarian.
KESIMPULAN
Struktur hash table ini akan menghemat pencarian karena proses lookup-nya
menggunakan algoritma binary search (pencarian biner) yang terbukti lebih cepat dari pada
sequential search (pencarian beruntun).
Perubahan struktur membawa keuntungan tambahan dengan tidak terbatasnya jumlah
record maksimum yang dapat disimpan oleh hash table. Selain itu partisi tabel menjadi bagianbagian
yang diproses secara terpisah dan menggunakan hash function sebagai selektor partisi
merupakan penerapan lain dari strategi divide and conquer.
Dapat disimpulkan bahwa struktur hash table yang memanfaatkan implementasi lookup
dengan binary search menggabungkan keunggulan dari struktur hash table dan algoritma
binary search
contoh table hasing di bawah.
h( ) | nama (A) | nama(B) | |
| 0 | ani->anni | ani | a |
| 1 | | anni | b |
| 2 | | | c |
| 3 | dani | dani | d |
| 4 | | | e |
| 5 | | | f |
| 6 | | | g |
| 7 | | | h |
| 8 | | | i |
| 9 | | | j |
| 10 | | | k |
| 11 | | | l |
| 12 | | | m |
| 13 | nani | nani | n |
| 14 | | | o |
| 15 | | | p |
| 16 | | | q |
| 17 | rini | rini | r |
| 18 | sani->soni | sani | s |
| 19 | | soni | t |
| 20 | | | u |
| 21 | | | v |
| 22 | | | w |
| 23 | | | x |
| 24 | | | y |
| 25 | | | z |
