HASHING TABLE

BASIC

Dalam dunia komputasi, hash table (hash map) adalah struktur data yang mengimplementasikan tipe data abstrak array asosiatif, struktur yang dapat memetakan kunci ke nilai. Dalam C ++ dan Java mereka adalah bagian dari standard library, sementara Python dan Go telah membangun kamus dan peta.

Hash table adalah kumpulan pasangan nilai kunci yang tidak teratur, di mana setiap kunci unik.

HASHING
Ide pokok dalam hashing adalah untuk mendistribusikan entri (key/value pairs) di seluruh array bucket. Stelah diberi key, algoritma menghitung indeks yang menunjukkan di mana entri dapat ditemukan:

index = f(key, array_size)

Biasanya dilakukan dalam dua langkah:

hash = hashfunc(key)

index = hash % array_size

Dalam metode ini, hash tidak tergantung pada ukuran array, dan kemudian dikurangi menjadi indeks (angka antara 0 danarray_size − 1) menggunakan modula operator (%).

Dalam kondisi ukuran array dapat dibagi 2, operasi sisanya dikurangi menjadi masking, yang meningkatkan kecepatan, tetapi dapat meningkatkan masalah dengan fungsi hash yang buruk.

Hash Function:

Secara sederhana, hash function memetakan sejumlah value ke integer kecil yang dapat digunakan sebagai indeks dalam hash table.

Fungsi hash yang baik harus memiliki syarat berikut:

• Dihitung secara efisien.
• Sebaiknya mendistribusikan kunci secara seragam (Setiap posisi meja memiliki kemungkinan yang sama untuk setiap kunci)

Choosing a hash function

Persyaratan dasar adalah bahwa function tersebut harus menyediakan distribusi nilai hash yang seragam. Distribusi yang tidak seragam akan meningkatkan jumlah tabrakan dan biaya penyelesaiannya.
Keseragaman kadang-kadang sulit untuk dipastikan dengan desain, tetapi dapat dievaluasi menggunakan uji statistik.

Perfect hash function

Jika semua key diketahui sebelumnya, prefect has function dapat digunakan untuk membuat perfect hash table yang tidak memiliki tabrakan. Jika minimal perfect hashing digunakan, setiap lokasi di hast table dapat digunakan juga.

Hash Table:

Struktur data yang menyimpan data secara asosiatif. Dalam hash table, data disimpan dalam format array, di mana setiap nilai data memiliki nilai indeks uniknya sendiri.

Collision Handling:

Karena fungsi hash memberi kita angka kecil untuk big key, ada kemungkinan bahwa dua kunci menghasilkan nilai yang sama. Situasi di mana key map yang baru dimasukkan ke slot yang sudah ditempati di hash table disebut collision dan harus ditangani menggunakan beberapa teknik penanganan tabrakan. Berikut adalah cara-cara untuk menangani collision:

·         Chaining: Intinya adalah untuk membuat setiap sel hash table menunjuk ke linked list yang memiliki nilai fungsi hash yang sama. Chaining sederhana tetapi membutuhkan memori tambahan di luar meja.

·         Open Addressing: Dalam open addressing, semua elemen disimpan dalam hash table itu sendiri. Setiap table entry berisi catatan atau NIL. Saat mencari elemen, kita satu per satu memeriksa table slot hingga elemen yang diinginkan ditemukan atau jelas bahwa elemen tersebut tidak ada dalam table.