Intro

Dalam paradigma bahasa pemrograman berorientasi objek atau OOP (Object-Oriented Programming) setiap kelas yang dibuat pasti memiliki method HashCode() atau sejenisnya. Method ini akan selalu ada meskipun kita tidak pernah menuliskannya didalam kelas yang dibuat.

Kenapa bisa ada? Karena sejatinya method tersebut diimplementasikan pada kelas Object. Dan seluruh kelas yang dibuat, akan otomatis inherit dari kelas tersebut.

Implementasi Default HashCode

Dalam bahasa pemrograman Java, tidak diketahui implementasi default dari HashCode. Apabila kita menelusuri kode sumber, Maka hanya akan didapatkan method native

public class Object {
	...
	public native int hashCode();
	...
}

Apa itu native? Secara singkat method native berarti suatu method, yang dimana tidak di-implementasikan pada bahasa pemrograman tersebut. Artinya, implementasi dari method tersebut dan bagaimana method tersebut bekerja, semua dibuat dalam bahasa pemrograman lain. Meskipun begitu, Kita bisa mengetahui gambaran cara kerja dan penggunaannya dengan membaca dokumentasi.

Kontrak:

  • Setiap kali method dipanggil pada object yang sama, harus konsisten menghasilkan nilai yang sama
  • Jika dua object merupakan equal, nilai dari HashCode juga harus sama
  • Tidak dipersyaratkan untuk object yang berbeda harus memiliki HashCode yang berbeda. Tetapi jika dapat dicapai, maka akan dapat memberikan performa lebih pada HashTable.

Dokumentasi

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

Jika membaca penjelasan tersebut, sepertinya secara default HashCode akan mengembalikan nilai berupa alamat memori dari object tersebut. Tetapi terdapat sanggahan bahwa cara tersebut tidak diharuskan.

Kegunaan HashCode

Bayangkan kita memiliki ratusan ribu data. Anggaplah sebagai contoh pendataan buku.

public class Book {
	private int      id;
	private String   judul;
	private int      jumlah;
	private Category kategory;

	public void setId(int id) { 
		this.id = id;
	}

	public void setJudul(String judul) {
		this.judul = judul;
	}
	public void setJumlah(int jumlah) {
		this.jumlah = jumlah;
	}

	public void setKategori(Category cat) {
		this.kategory = cat;
	}

	public int getId() {
		return this.id;
	}

	public String getJudul() {
		return this.judul;
	}
	public int getJumlah() {
		return this.jumlah;
	}
	public Category getKategori() {
		return this.kategori;
	}
}

Lalu, untuk keperluan memanipulasi data, kita menampung keseluruhan object tersebut ke dalam array atau ke sebuah List.

List<Book> daftarBuku = new ArrayList<Book>();

1. HashMap

Kemudian, program kita terdapat kebutuhan untuk melakukan update terhadap jumlah buku. Bagaimana cara mendapatkan object yang sesuai? Sebagai contoh, buku “Sejarah” mendapatkan penambahan 5 buah dan buku “Novel” mendapatkan penambahan 18 buah. Dengan langsung menuliskan index?

Book sejarah = daftarBuku.get(8);
sejarah.setJumlah(sejarah.getJumlah() + 5);

Ya cara tersebut bisa dilakukan dengan sangat cepat. Tapi apakah buku sejarah sudah dipastikan berada pada index ke -8? Apa yang terjadi jika index ke -8 ternyata merupakan buku komik?

Tentu saja semua sepakat menjawab “Dengan search algorithm“. Ya.. benar.. dengan Binary Search? Sequential Search? atau jenis algoritma pencarian lain?

Penggunaan Sequential Search, apabila ternyata object tersebut berada pada index 1000, apakah harus melakukan loop 1000x tidak bisa dipercepat? Atau kita menggunakan Binary Search untuk mereduksi jumlah iterasi? Ya memungkinkan, tetapi sebelum itu, jangan lupa untuk melakukan sorting terlebih dahulu. Pada akhirnya akan sama saja. Operasi yang dilakukan untuk menemukan object tersebut akan sangat mahal dan cukup memakan waktu.

Untuk menyiasati hal tersebut, diciptakanlah suatu metode HashTable, dimana data disimpan dalam bentuk kode hash yang dihasilkan dari hashCode().

Program hanya perlu menghitung index dari HashCode yang sudah didapatkan dan index data tersebut sudah ditemukan dengan sangat cepat. Pada bahasa pemrograman Java, kita dapat menggunakan HashMap untuk mengakomodasi kebutuhan ini.

Map<String, Book> daftarBuku = new HashMap<String, Book>();

HashMap memiliki sebuah key yang dijadikan acuan dalam menemukan suatu object. Sehingga kebutuhan pencarian buku sejarah seperti kasus diatas dapat dicapai dengan

Book sejarah = daftarBuku.get("Sejarah");
sejarah.setJumlah(sejarah.getJumlah() + 5);

Selain HashMap, kita bisa menggunakan LinkedHashMap yang menawarkan kelebihan urutan data berdasarkan data yang dimasukkan layaknya LinkedList.

2. HashSet

HashCode juga bermanfaat untuk mencegah adanya duplikasi pada data. Kita bisa menggunakan HashSet untuk mencapai kebutuhan tersebut.

Set<Book> daftarBuku = new HashSet<Book>();
Book sejarah = new Book();

...

daftarBuku.add(sejarah);

Sebenarnya cara kerja antara kedua struktur data tersebut sama saja. Yaitu menggunakan HashTable untuk menemukan data yang dimaksud. Perbedaannya adalah HashSet untuk menyimpan data tanpa adanya duplikasi data dan HashMap untuk kebutuhan menyimpan dan memanipulasi data dengan cepat dengan melakukan pencarian terhadap kunci (dan tanpa duplikasi kunci).

Permasalahan Pada HashCode

Kontrak

– Setiap kali method dipanggil pada object yang sama, harus konsisten menghasilkan nilai yang sama
– Jika dua object merupakan equal, nilai dari HashCode juga harus sama
– Tidak dipersyaratkan untuk object yang berbeda harus memiliki HashCode yang berbeda. Tetapi jika dapat dicapai, maka akan dapat memberikan performa lebih pada hashTable.

1. Hash Collision (Tabrakan Hash)

Sebelum membahas apa itu Hash Collision, ada baiknya memahami kontrak dari HashCode diatas. Misalnya, kita ada kebutuhan apabila judul buku sama, maka object adalah equals.

public class Book {

        ...
        
        @override
        public int hashCode(){
            return getJudul().length();
        }
        
        @Override
	    public boolean equals(Object obj) {
            return ((Book)obj).getJudul().equals(this.getJudul());
        }
}

Apa yang salah dari kode tersebut? Katakanlah judulnya adalah “Sejarah”. Karena hashCode() mengembalikan nilai berupa panjangnya String pada judul, maka object Book untuk sejarah akan memiliki HashCode bernilai 7. Object Book apapun, apabila memiliki judul “Sejarah” maka akan selalu equal dan selalu menghasilkan HashCode yang bernilai 7. Berdasarkan hasil tersebut, kontrak 1 dan 2 sudah terpenuhi. Bagaimana dengan kontrak ke -3?

Kontrak

– Tidak dipersyaratkan untuk object yang berbeda harus memiliki HashCode yang berbeda. Tetapi jika dapat dicapai, maka akan dapat memberikan performa lebih pada hashTable.

Anggap saja kita memiliki judul buku lain, “Biologi”. Diingat kembali pada implementasi HashCode diatas, yaitu akan mengembalikan nilai berupa panjang dari String judul. karena “Biologi” memiliki panjang 7 maka HashCode yang dihasilkan juga akan bernilai 7.

object untuk “Sejarah” dan “Biologi” akan menghasilkan HashCode yang sama. Apakah hal ini menyalahi kontrak? Tidak.. tidak sama sekali, tetapi coba diperhatikan kembali pada kalimat kedua

… Tetapi jika dapat dicapai, maka akan dapat memberikan performa lebih pada hashTable.

Meskipun tidak diwajibkan, tetapi hal ini dapat dianggap tidak memenuhi kriteria tambahan tersebut. Apa dampaknya?

Dalam implementasi HashTable, seperti yang digunakan pada HashMap dan HashSet, masalah ini disebut dengan Hash Collision. Yaitu kondisi dimana object yang berbeda tetapi menghasilkan nilai HashCode yang sama.

Jika begitu, maka apakah object berbeda itu dianggap menjadi data yang sama (Baik secara kunci HashMap, atau data HashCode)? Jawabannya adalah tidak. Dalam hal ini, implementasi HashTable sudah sangat baik di Java. Apabila HashCode ditemukan kesamaan, maka selanjutnya method equals() akan dipanggil. Hal ini dibuat guna untuk mencegah adanya data yang rusak / hilang akibat kesamaan HashCode.

Dampak negatifnya, Hash Collision akan memperlambat waktu pemrosesan saat table lookup atau pencarian data. Hal ini akan sangat diperparah apabila terlalu banyak object berbeda yang memiliki HashCode yang sama. Istilah umum yang digunakan untuk hal ini adalah good hash dan bad hash.

Hampir mustahil untuk menjamin HashCode selalu unik untuk tiap value. Tetapi sangat amat mungkin untuk membuat implementasi HashCode sebaik mungkin untuk mereduksi kemungkinan Hash Collision. Bisa saja hal itu masih terjadi, tapi diharapkan dalam kemungkinan sekecil mungkin atau ketika data sudah sangat amat banyak.

2. Mutable Key (Perubahan Data)

Terkait object “Sejarah” dimana nilai dari HashCode itu sangat bergantung kepada field judul. Lalu misalnya kita mengganti judul object tersebut menjadi “Sejarah Indonesia” maka otomatis HashCode akan mengalami perubahan nilai

Book sejarah = new Book();
sejarah.setJudul("Sejarah");
System.out.println(sejarah.hashCode());

sejarah.setJudul("Sejarah Indonesia");
System.out.println(sejarah.hashCode());
7
17

Apa dampak buruk yang terjadi? Hash Lookup akan menjadi gagal dan akan menghasilkan output yang sulit diprediksi Umumnya null, tetapi tidak menutup kemungkinan untuk mengbalikan data yang salah. Sebagai contoh, kita membuat HashMap dengan key berupa Book dan value berupa jumlah buku.

Map<Book, Integer> buku = new HashMap<Book, Integer>();

Lalu kita melakukan insertion dengan key sejarah yang berjudul “Sejarah”.

Kemudian apabila object sejarah tersebut kita ganti judulnya menjadi “Sejarah Indonesia” maka data tersebut sudah tidak akan bisa diakses kembali karena HashCode yang menjadi acuan sudah berubah. Hal ini tentu saja akan mengakibatkan memory leak, yaitu kondisi dimana object tidak terpakai yang menjadi residu karena tidak terhapus.

Map<Book, Integer> buku = new HashMap<Book, Integer>();
Book sejarah = new Book();
sejarah.setJudul("Sejarah");
buku.put(sejarah, 10);

System.out.println(buku.get(sejarah));

sejarah.setJudul("Sejarah Indonesia");
System.out.println(buku.get(sejarah));
10
null

Praktek Terbaik

Praktek terbaik adalah untuk tidak melakukan override sama sekali jika memang tidak ada kebutuhan. Biarkan dengan implementasi default. Jika memang akan diubah, pastikan untuk merancangnya dengan baik agar kecil kemungkinan terjadinya Hash Collision.

Selain itu, pastikan juga data yang menjadi rujukan bersifat immutable atau tidak dapat diubah. Dalam hal ini, menggunakan HashCode dari ID suatu entitas database masih memungkinkan karena ID tidak mungkin bertabrakan untuk row dari table yang sama. Selain itu ID juga tidak mungkin berubah untuk data yang sama.

Hindari menggunakan object sebagai key pada HashMap. Selalu gunakan primitive(baik boxed atau non boxed) dan String. Kecuali memang kelas pada object tersebut sudah menjamin mengimplementasikan HashCode berdasarkan field immutable.