Struktur Data - Tabel Hash

Banyak aplikasi memerlukan set dinamis yang hanya mendukung operasi dictionary pada INSERT, SEARCH, dan DELETE. Sebagai contoh, kompilator yang menerjemahkan bahasa pemrograman mempertahankan tabel simbol, di mana kunci elemen adalah string karakter acak sesuai dengan pengenal dalam bahasa. Tabel Hash adalah struktur data yang efektif untuk mengimplementasikan kamus. Ide dasar dari table hash sangat sederhana, dan cukup menarik: Asumsikan bahwa, dengan memberi key, ada cara melompat langsung ke entri untuk key itu. Maka kita tidak akan perlu mencari, kita bisa lansung ke sana dan tentu saja, kita masih harus mencari cara agar itu tercapai.

Asumsikan bahwa kita memiliki data array untuk memegang entri kita. ketika kita memiliki fungsi h (k) yang memetakan setiap key k ke indeks atau integer maka tempat entri terkait akan disimpan, maka kita bisa mencari data [h (k)] untuk menemukan entri dengan kunci k.

Meskipun mencari elemen dalam table hash dapat memakan waktu selama mencari elemen dalam linked list θ(n) pada kasus terburuk, dalam praktiknya, hashing berkinerja sangat baik baik. Dengan asumsi yang wajar, waktu rata-rata untuk mencari elemen di table Hash adalah O(1)

Akan lebih mudah jika kita bisa membuat array data cukup besar untuk menampung semua key yang mungkin muncul. Sebagai contoh, jika kita tahu bahwa key adalah angka dari 0 hingga 99, maka kita bisa membuat array dengan ukuran 100 dan menyimpan entri dengan key 67 dalam data [67], dan seterusnya. Dalam hal ini, fungsi h akan menjadi fungsi identitas h (k) = k. Namun, ide ini tidak terlalu praktis jika kita berurusan dengan sejumlah key yang relatif kecil dari sekumpulan besar kemungkinan key

Beberapa contoh bagaimana hashing metode ini digunakan dalam kehidupan sehari-hari misalnya di universitas, setiap mahasiswa pastiya diberi NIP atau nomor identifikasi yang digunakan sebagai informasi mengenai mereka. Atau contoh paling nyatanya juga pada perpustakaan, setiap buku akan diberi nomor unik sebagai informasi mengenai buku tersebut, seperti letak penyimpanan, sehingga pengunjung yang meminjam buku tersebut bisa mencari lewat database perpustakaan apakah buku dipinjam oleh orang lain atau masih tersedia diperpustakaan. Kelebihan dari hash table antara lain relatif lebih cepat dan memiliki kecepatan dalam insertions, deletions, maupun searching relatif sama.

Maka menggunakan struktur data yang menggunakan fungsi hash ini memungkinkan Anda melakukan pencarian atau penyisipan dalam waktu yang konstan. Disini anda perlu melakukan pencarian dalam waktu linier meskipun dalam list atau satu set, anda perlu memeriksa setiap elemen untuk menemukan yang Anda cari. Atau adanya stack(tumpukan) yang memungkinkan Anda mencari elemen yang paling lama, atau terbaru, dengan segera. Dan queues(antrian) prioritas akan membiarkan Anda menemukan elemen prioritas tertinggi dengan cepat, tetapi jika Anda menginginkan elemen lain, Anda harus melakukan pencarian waktu linier.

Dengan hash function tersebut didapat :

k H
9 9
14 0
25 12
28 2
38 0

Perhatikan range dari h untuk sembarang nilai k.

Maka data 9 akan disimpan pada index 9 atau data 14 tersimpan pada index 0, dst. Sehingga ketika anda mencari kembali suatu data, maka kita hanya perlu menggunakan hash function yang sama sehingga mendapatkan hash index yang sama pula.

Misal : mencari data 25 → h = 25 (mod 13) = 12

Nah sekarang terdapat contoh misalnya perusahaan Amerika menggunakan nomor keamanan sosial 9-digit karyawan mereka sebagai key, meskipun mereka memiliki tempat di dekat 109 karyawan. Ketika terdapat jumlahnya sama panjang dan mengandung campuran huruf dan angka. Jelas itu akan sangat tidak efisien, jika bukan tidak mungkin, untuk mencadangkan ruang untuk semua 109 nomor jaminan sosial yang mungkin terjadi.

Sebagai gantinya, kami menggunakan non-trivial fungsi h, yang disebut fungsi hash, untuk memetakan ruang key yang mungkin ke set indeks dari array kita. Misalnya, jika kita harus menyimpan entri sekitar 500 karyawan, maka mungkin membuat array dengan 1000 entri dan menggunakan tiga digit dari nomor jaminan sosial mereka (mungkin tiga yang pertama atau terakhir) untuk menentukan tempat di array tempat catatan untuk setiap karyawan tertentu harus disimpan.

Pendekatan ini terdengar seperti ide yang bagus, tetapi ada masalah yang cukup jelas dengannya: Apa yang terjadi jika dua karyawan memiliki tiga digit yang sama? Ini disebut collision(tabrakan) antara dua key Supaya lebih paham, sengaja contoh table diatas terdapat angka 14 dan 38 berada pada indeks yang sama, yaitu 0. Collision ini maksudnya terdapat lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat atau satu index array hanya dapat menyimpan satu data saja.

Sebagian besar dari materi ini nantinya akan membicarakan strategi untuk menangani Collision seperti itu. Pertama-tama, tentu saja, kita harus mencoba menghindari Collision. Jika key itu kemungkinan besar sebenarnya terjadi tidak merata di seluruh ruang dari semua kemungkinan key, khususnya perhatian harus diberikan untuk memilih fungsi hash h sedemikian rupa sehingga terjadi Collision antar mereka cenderung tidak terjadi.

Jika, misalnya, tiga digit pertama dari nomor jaminan social memiliki arti geografis, maka karyawan sangat mungkin memiliki tiga digit menandakan wilayah di mana perusahaan berada, dan memilih tiga digit pertama sebagai fungsi hash mungkin menyebabkan banyak tabrakan. Namun, masalah itu mungkin dengan mudah dihindari dengan pilihan yang lebih bijaksana, seperti tiga digit terakhir. Oke sekian dulu pengenalan mengenai table hash, pada materi selanjutnya akan dibahas pengembangan dari metod hasing ini. Terima kasih