HashSet dan HashMap diimplementasikan dengan struktur data yang disebut tabel hash. Kita tidak perlu mengerti tabel hash untuk menggunakan HashSet atau HashMap, akan tetapi programmer harus kenal dengan tabel hash dan cara kerjanya.
Tabel hash merupakan solusi elegan untuk menyelesaikan masalah pencarian. Tabel hash, seperti HashMap, menyimpan pasangan kunci/nilai. Jika kita mengetahui kuncinya, maka kita bisa mencari nilainya di dalam tabel. Jika tabel hash digunakan untuk mengimplementasikan set, maka semua nilainya berisi null. Kita masih harus mencari kuncinya di dalam tabel.
Dalam semua algoritma pencarian, untuk mencari suatu item, kita harus mencari item yang tidak kita inginkan. Untuk mencari suatu item di dalam list tidak terurut, maka kita harus mengecek isinya satu per satu hingga item yang kita cari ditemukan. Dalam pohon pencarian biner, kita harus mulai dari akar dan turun ke bawah hingga item yang dicari ditemukan.
Jika kita mencari pasangan kunci/nilai dalam tabel hash, kita bisa langsung ke tempat di mana item tersebut berada. Kita tidak perlu mencari item lainnya (Sebenarnya tidak sepenuhnya benar, tapi kira-kira seperti ini). Lokasi di mana pasangan kunci/nilai ini berada dihitung dari kuncinya: Kita hanya melihat kuncinya, dan kita bisa pergi ke lokasi di mana nilai tersebut disimpan secara langsung.
Bagaimana caranya? Jika kuncinya adalah integer antara 0 hingga 99, kita bisa menyimpan pasangan kunci/nilai dalam array A yang berisi 100 elemen. Pasangan kunci/nilai dengan kunci N bisa disimpan dalam A[N]. Kunci ini akan membawa kita langsung ke pasangan kunci/nilai.
Masalahnya, ada banyak kemungkinan untuk suatu jenis kunci. Misalnya, jika kuncinya bertipe int, maka kita perlu 4 milyar lokasi untuk menyimpan semua kuncinya dalam array -- tentunya pemborosan memori yang sia-sia jika kita hanya ingin menyimpan katakan ribuan item saja. Jika kuncinya berupa string dengan panjang yang tidak tentu, maka jumlah kemungkinan kuncinya tidak terbatas, sehingga kita tidak mungkin menggunakan array untuk menyimpan semua kemungkinan kuncinya.
Walau bagaimanapun, tabel hash menyimpan datanya dalam array. Indeks tidak sama dengan kunci, akan tetapi indeks dihitung dari kunci. Indeks array dari hasil perhitungan kunci disebut kode hash untuk kunci tersebut. Fungsi tertentu akan menghitung kode hash, yang disebut fungsi hash. Untuk mencari kunci di dalam tabel hash, kita hanya pelu menghitung kode hash kunci tersebut, kemudian langsung pergi ke lokasi array di ditunjuk oleh kode hash tersebut. Jika kode hashnya 17, lihat langsung pada array nomor 17.
Sekarang, karena hanya ada lebih sedikit lokasi array dibandingkan kemungkinan kuncinya, maka sangat mungkin kita memiliki situasi di mana satu lokasi array digunakan dua atau lebih kunci. Hal ini disebut tabrakan (collision). Tabrakan bukan kesalahan. Kita tidak bisa menolak suatu kunci karena memiliki kode hash yang sama dengan kunci lain. Tabel hash harus bisa menangani tabrakan dengan cara yang baik.
Dalam tabel hash yang digunakan pada Java, setiap lokasi array sebetulnya adalah suatu list berantai yang berisi pasangan kunci/nilai (atau mungkin juga list kosong). Jika dua item memiliki kode hash yang sama, maka kedua item tersebut akan ada pada list yang sama. Strukturnya bisa digambarkan sebagai berikut.
Pada gambar di atas, hanya ada satu item dengan kode hash 0, tidak ada item dengan kode hash 1, dua item dengan kode hash 2, dan seterusnya. Pada tabel hash yang dirancang dengan benar, hampir semua list berantai berisi nol atau satu elemen saja, dengan rata-rata panjang list kurang dari 1. Meskipun kode hash dari suatu kunci mungkin tidak membawa kita langsung pada kunci yang kita mau, akan tetapi tidak akan lebih dari satu atau dua item yang harus kita cari sebelum kita sampai pada item yang kita inginkan.
Agar bekerja dengan benar, jumlah item dalam tabel hash harus kurang dari besarnya array. Pada Java, katika jumlah item melebihi 75% ukuran array, maka array tersebut akan diganti dengan array yang lebih besar dan semua item pada array yang lama dipindahkan ke array baru.
Kelas Object memiliki metode bernama hashCode() yang mengembalikan nilai bertipe int. Ketika objek obj disimpan dalam tabel yang berukuran N, maka kode hash antara 0 hingga N-1 diperlukan. Kode hash ini bisa dihitung dengan menggunakanMath.abs(obj.hashCode()) % N, yaitu sisa pembagian dari nilai mutlak obj.hashCode() dengan N. (Nilai mutlak diperlukan karena obj.hashCode() bisa bernilai negatif, dan kita tidak ingin nilai negatif sebagai indeks array kita).
Supaya hash bisa bekerja dengan benar, dua objek yang sama menurut metode equals() seharusnya memiliki kode hash yang sama. Dalam kelas Object metode equals() dan hashCode() dihitung berdasarkan lokasi memori di mana objek tersebut disimpan. Akan tetapi seperti disebutkan sebelumnya, banyak kelas yang memiliki metode equals() sendiri.
Jika suatu kelas memiliki metode equals() sendiri, dan jika objek tersebut akan digunakan sebagai kunci pada tabel hash, maka kelas tersebut juga harus mendefinisikan metode hashCode().
Misalnya dalam kelas String, metode equals() didefinisi ulang sehingga dua objek String dianggap sama jika urutan karakter dalam String tersebut sama. Metode hashCOde() pada kelas String itu juga didefinisi ulang sehingga kode hash dari string dihitung berdasarkan karakter di dalam String, bukan lokasi memorinya.
Untuk kelas standar Java, kita bisa berharap bahwa metode equals() dan hashCode sudah dibuat dengan benar, akan tetapi untuk kelas yang kita buat sendiri kita mungkin harus membuat fungsi hash sendiri.
Tidak ada komentar:
Posting Komentar