Struktur Data Hash

5 min readJun 20, 2021

Halo sobat dira, kembali lagi bersama kita dengan artikel yang positif. Kali ini kita akan membahas tentang Hash / Hashing, Hashing adalah teknik yang dilakukan untuk melakukan pencarian elemen pada suatu struktur data, tanpa melakukan pencarian linear.

Hasing dapat di implementasikan dengan dua langkah yaitu :

Sebuah elemen dikonversi menjadi integer menggunakan fungsi hash. Elemen ini dapat digunakan sebagai indeks untuk menyimpan elemen asal, yang dapat ditemukan di tabel hash.
Elemen disimpan dalam tabel hash yang dapat dibuka dengan cepat menggunakan kunci hash.

hash = hashfunc(key)
index = hash % array_size

Dari contoh diatas untuk melakukan hashing kita memerlukan hash function. Fungsi hash / hash function adalah fungsi yang dapat digunakan untuk memetakan sekumpulan data pada ukuran arbitrari menjadi sekumpulan data dengan ukuran yang tetap, yang dapat ditemukan di tabel hash. Nilai yang dikembalikan oleh fungsi hash disebut nilai hash, kode hash, sum hash, atau sekadar hash.

Hash Table

Hasil dari proses hashing bisa kita simpan ke dalam hash table. Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Untuk memperoleh mekanisme hashing yang bagus, memiliki fungsi hash yang bagus adalah hal yang amat penting. Hash yang tanpa cacat diperoleh dengan memenuhi beberapa persyaratan:

1. Mudah untuk dikomputasi: Hash yang bagus harus ringan untuk proses komputasi dan tidak menjadi algoritme terpisah.

2. Distribusi yang seragam: Hash yang bagus memberikan distribusi yang seragam di seluruh tabel hash sehingga tidak berakhir menjadi clustering.

Sedikit collision: Collision terjadi saat sepasang elemen dipetakan ke nilai hash yang sama. Hal ini harus dihindari.Catatan: Sebagus apa pun suatu fungsi hash, collision masih mungkin terjadi. Oleh karena itu, untuk menjaga performa tabel hash, mengelola collision melalui beberapa teknik resolusi collision amat penting untuk dilakukan.

Tabrakan / collision

Didalam melakukan hash, mungkin akan terjadi collision / tabrakan yang dimana ketika kita melakukan hashing namun key dari hasil hashing kita bertabrakan dengan index dari hash yang lain, untuk menghindari hal tersebut kita memerlukan cara untuk mengatasi hal tersebut, cara tersebut antara lain :

Linear Probing

Pada open addressing, selain linked list, semua catatan entri disimpan dalam array. Saat entri baru disisipkan, indeks hash dari nilai setelah hashing akan dikomputasi dan array akan diuji (dari indeks setelah hashing). Jika slot pada indeks yang mengalami hashing tidak terisi, maka rekam entri akan disisipkan pada slot di indeks hashing. Jika tidak, teruskan probe sequence hingga slot kosong ditemukan.

Probe sequence adalah sequence yang diikuti saat menelusuri entri. Dalam probe sequence yang berbeda, Anda dapat memiliki interval yang berbeda di antara slot atau probe entri yang mengikutinya.

Saat melakukan pencarian entri, array akan dipindai dengan urutan yang sama hingga elemen target atau slot yang tidak digunakan ditemukan. Hal ini mengindikasikan tidak adanya kunci di dalam tabel. Nama “open addressing” merujuk pada keadaan di mana lokasi atau alamat item tidak dapat ditentukan oleh nilai hash value.

2. Quadratic Probing

Quadratic probing serupa dengan linear probing dan satu-satunya perbedaan adalah interval antara adalah interval di Antara probe atau slot entri. Di sini, saat slot pada indeks hashing untuk rekam entri telah ditempati, Anda harus melakukan penelusuran hingga Anda menemukan slot kosong. Interval di antara slot dikomputasi dengan menambahkan nilai arbitrary polynomial yang mengikutinya pada indeks hashing awal.

3. Double Hashing

Double hashing serupa dengan linear probing dan satu-satunya perbedaan adalah interval antar probe. Di sini, interval di antara probe dihitung menggunakan dua fungsi hash.

4. Separate Chaining

Separate chaining adalah salah satu cara resolusi collision yang paling sering digunakan. Cara ini biasanya diimplementasikan menggunakan linked list (seranai berantai; seranai bertaut; daftar bertaut). Pada separate chaining, setiap elemen pada tabel hash adalah linked list. Untuk menyimpan elemen di tabel hash, Anda harus menyisipkannya ke linked list khusus. Jika terdapat collision (dua elemen yang memiliki nilai hash yang sama) maka simpan kedua elemen di linked list yang sama.

Contoh penerapan Hashing

Diketahui bahwa kita memiliki suatu table yang berisi key dan value.