003
- 9 Maret 2020-

Data Structure (Kelas Besar)
Nama : Muhammad Andika Putra
NIM : 2301865994



"Hashing" adalah teknik yang digunakan secara unik untuk mengidentifikasi objek dari sekelompok objek serupa. Beberapa contoh bagaimana cara kerja hashing dalam kehidupan ialah:

1. Di universitas, setiap mahasiswa diberi nomor unik yang dapat mereka gunakan untuk mengambil informasi tentang diri mereka.
2. Di perpustakaan, setiap buku diberi nomor unik tersendiri yang nantinya digunakan untuk menentukan informasi tentang buku, seperti posisinya yang tepat di perpustakaan atau siapa penggunanya.
Kedua contoh tersebut adalah contoh dari penggunaan hash ke siswa dan buku dengan nomor unik.

Asumsikan bahwa anda memiliki objek dan Anda ingin menetapkan kunci untuk memudahkan pencarian. Untuk menyimpan kunci, Anda dapat menggunakan simple array atau data structure dimana kunci(integer) dapat digunakan sebagai index untuk menyimpan nilai. Bagaimanapun, dalam kasus ini kuncinya sangat besar dan tidak dapat menggunakan index secara langsung, Anda harus menggunakan hashing.

Dalam hashing, kunci besar dikonversikan menjadi kunci kecil dengan menggunakan fungsi hash. Setelah itu nilai disimpan di data structure yang disebut hash table. Gagasan hashing adalah untuk mendistribusikan nilai secara ragam di seluruh array. Setiap elemen diberi kunci(kunci yang dikonversi). Dengan kunci itu, Anda dapat mengakses elemen. Menggunakan kunci, algoritma (fungsi hast) menghitung indeks yang menunjukkan dimana nilai dapat ditemukan atau dimasukkan.

Hashing diimplementasikan dalam dua langkah:

Elemen dikonversi menjadi integer dengan menggunakan fungsi hash. Elemen ini dapat digunakan sebagai indeks untuk menyimpan elemen asli, yang jatuh ke tabel hash.
Elemen disimpan di tabel hash di mana ia dapat dengan cepat diambil menggunakan kunci hash.

hash = hashfunc (kunci)
index = hash% array_size

Dalam metode ini, hash tidak tergantung pada ukuran array dan kemudian dikurangi menjadi indeks (angka antara 0 dan array_size - 1) dengan menggunakan operator modulo (%).

Fungsi hash
Fungsi hash adalah fungsi apa pun yang dapat digunakan untuk memetakan kumpulan data dari ukuran arbitrer ke kumpulan data dengan ukuran tetap, yang termasuk dalam tabel hash. Nilai yang dikembalikan oleh fungsi hash disebut nilai hash, kode hash, jumlah hash, atau hanya hash.

Untuk mencapai mekanisme hashing yang baik, penting untuk memiliki fungsi hash yang baik dengan persyaratan dasar berikut:

Mudah dikomputasi: Seharusnya mudah dikomputasi dan tidak harus menjadi algoritma itu sendiri.

Distribusi seragam: Ini harus menyediakan distribusi seragam di seluruh tabel hash dan tidak boleh menghasilkan pengelompokan.

Kurang tabrakan: Tabrakan terjadi ketika pasangan elemen dipetakan ke nilai hash yang sama. Ini harus dihindari.

Catatan: Terlepas dari seberapa baik fungsi hash, tabrakan pasti akan terjadi. Oleh karena itu, untuk mempertahankan kinerja tabel hash, penting untuk mengelola tabrakan melalui berbagai teknik resolusi tabrakan.

Perlu fungsi hash yang baik

Mari kita memahami perlunya fungsi hash yang baik. Asumsikan bahwa Anda harus menyimpan string dalam tabel hash dengan menggunakan teknik hashing {"abcdef", "bcdefa", "cdefab", "defabc"}.

Untuk menghitung indeks untuk menyimpan string, gunakan fungsi hash yang menyatakan sebagai berikut:

Indeks untuk string tertentu akan sama dengan jumlah nilai ASCII dari karakter modulo 599.

Karena 599 adalah bilangan prima, itu akan mengurangi kemungkinan mengindeks string yang berbeda (tabrakan). Disarankan agar Anda menggunakan bilangan prima jika modulo. Nilai ASCII dari a, b, c, d, e, dan f masing-masing adalah 97, 98, 99, 100, 101, dan 102. Karena semua string berisi karakter yang sama dengan permutasi yang berbeda, jumlahnya akan 599.

Fungsi hash akan menghitung indeks yang sama untuk semua string dan string akan disimpan dalam tabel hash dalam format berikut. Karena indeks semua string sama, Anda dapat membuat daftar pada indeks itu dan memasukkan semua string dalam daftar itu.



Sumber: https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/