Panduan untuk hashCode () di Java

1. Ikhtisar

Hashing adalah konsep dasar ilmu komputer.

Di Java, algoritme hashing yang efisien berdiri di belakang beberapa koleksi paling populer yang kami miliki - seperti HashMap (untuk melihat lebih dalam di HashMap , silakan periksa artikel ini) dan HashSet.

Dalam artikel ini, kita akan fokus pada cara kerja hashCode () , cara memainkannya ke dalam koleksi, dan cara menerapkannya dengan benar.

2. Penggunaan hashCode () dalam Struktur Data

Operasi paling sederhana pada koleksi bisa jadi tidak efisien dalam situasi tertentu.

Misalnya, ini memicu penelusuran linier yang sangat tidak efektif untuk daftar ukuran besar:

List words = Arrays.asList("Welcome", "to", "Baeldung"); if (words.contains("Baeldung")) { System.out.println("Baeldung is in the list"); }

Java menyediakan sejumlah struktur data untuk menangani masalah ini secara khusus - misalnya, beberapa implementasi antarmuka Peta adalah tabel hash.

Bila menggunakan tabel hash, koleksi ini menghitung nilai hash untuk kunci tertentu menggunakan kode hash () metode dan menggunakan nilai ini secara internal untuk menyimpan data - sehingga operasi akses yang jauh lebih efisien.

3. Memahami Cara Kerja hashCode ()

Sederhananya, hashCode () mengembalikan nilai integer, yang dihasilkan oleh algoritme hashing.

Objek yang sama (menurut sama dengan () ) harus mengembalikan kode hash yang sama. Objek yang berbeda tidak perlu mengembalikan kode hash yang berbeda.

Kontrak umum hashCode () menyatakan:

  • Kapan pun itu dipanggil pada objek yang sama lebih dari sekali selama eksekusi aplikasi Java, hashCode () harus secara konsisten mengembalikan nilai yang sama, asalkan tidak ada informasi yang digunakan dalam perbandingan yang sama pada objek yang diubah. Nilai ini tidak perlu tetap konsisten dari satu eksekusi aplikasi ke eksekusi lain dari aplikasi yang sama
  • Jika dua objek sama menurut metode equals (Object) , maka pemanggilan metode hashCode () pada masing-masing objek harus menghasilkan nilai yang sama.
  • Tidak diperlukan bahwa jika dua objek tidak sama menurut metode equals (java.lang.Object) , maka memanggil metode hashCode pada masing-masing objek harus menghasilkan hasil integer yang berbeda. Namun, pengembang harus menyadari bahwa menghasilkan hasil integer yang berbeda untuk objek yang tidak sama meningkatkan kinerja tabel hash

“Sebanyak yang cukup praktis, metode hashCode () yang didefinisikan oleh class Object tidak mengembalikan integer yang berbeda untuk objek yang berbeda. (Ini biasanya diterapkan dengan mengonversi alamat internal objek menjadi bilangan bulat, tetapi teknik implementasi ini tidak diperlukan oleh bahasa pemrograman JavaTM.) ”

4. Implementasi hashCode () naif

Sebenarnya cukup mudah untuk memiliki implementasi hashCode () naif yang sepenuhnya mematuhi kontrak di atas.

Untuk mendemonstrasikan ini, kita akan menentukan contoh kelas Pengguna yang menggantikan implementasi default metode:

public class User { private long id; private String name; private String email; // standard getters/setters/constructors @Override public int hashCode() { return 1; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null) return false; if (this.getClass() != o.getClass()) return false; User user = (User) o; return id == user.id && (name.equals(user.name) && email.equals(user.email)); } // getters and setters here }

Kelas Pengguna menyediakan implementasi khusus untuk equals () dan hashCode () yang sepenuhnya mematuhi kontrak masing-masing. Terlebih lagi, tidak ada yang tidak sah dengan hashCode () mengembalikan nilai tetap apa pun.

Namun, implementasi ini menurunkan fungsionalitas tabel hash menjadi nol, karena setiap objek akan disimpan dalam satu keranjang yang sama.

Dalam konteks ini, pencarian tabel hash dilakukan secara linier dan tidak memberi kita keuntungan nyata - lebih lanjut tentang ini di bagian 7.

5. Meningkatkan Implementasi hashCode ()

Mari kita tingkatkan sedikit implementasi hashCode () saat ini dengan menyertakan semua bidang kelas Pengguna sehingga dapat menghasilkan hasil yang berbeda untuk objek yang tidak sama:

@Override public int hashCode() { return (int) id * name.hashCode() * email.hashCode(); }

Algoritme hashing dasar ini secara definitif jauh lebih baik daripada yang sebelumnya, karena ini menghitung kode hash objek hanya dengan mengalikan kode hash dari field nama dan email dan id .

Secara umum, kita dapat mengatakan bahwa ini adalah implementasi hashCode () yang wajar , selama kita menjaga implementasi equals () konsisten dengannya.

6. Implementasi standar hashCode ()

Semakin baik algoritma hashing yang kita gunakan untuk menghitung kode hash, semakin baik pula kinerja tabel hash.

Mari kita lihat implementasi "standar" yang menggunakan dua bilangan prima untuk menambahkan lebih banyak keunikan ke kode hash yang dihitung:

@Override public int hashCode() { int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null ? 0 : name.hashCode()); hash = 31 * hash + (email == null ? 0 : email.hashCode()); return hash; }

Meskipun penting untuk memahami peran yang dimainkan oleh metode hashCode () dan equals () , kita tidak harus mengimplementasikannya dari awal setiap saat, karena sebagian besar IDE dapat menghasilkan implementasi hashCode () dan equals () khusus dan sejak Java 7, kami mendapat metode utilitas Objects.hash () untuk hashing yang nyaman:

Objects.hash(name, email)

IntelliJ IDEA menghasilkan implementasi berikut:

@Override public int hashCode() { int result = (int) (id ^ (id >>> 32)); result = 31 * result + name.hashCode(); result = 31 * result + email.hashCode(); return result; }

Dan Eclipse menghasilkan yang ini:

@Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((email == null) ? 0 : email.hashCode()); result = prime * result + (int) (id ^ (id >>> 32)); result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; }

Selain implementasi hashCode () berbasis IDE di atas , implementasi yang efisien juga dapat dibuat secara otomatis, misalnya menggunakan Lombok. Dalam kasus ini, ketergantungan lombok-maven harus ditambahkan ke pom.xml :

 org.projectlombok lombok-maven 1.16.18.0 pom 

It's now enough to annotate the User class with @EqualsAndHashCode:

@EqualsAndHashCode public class User { // fields and methods here }

Similarly, if we want Apache Commons Lang's HashCodeBuilder class to generate a hashCode() implementation for us, the commons-lang Maven dependency must be included in the pom file:

 commons-lang commons-lang 2.6 

And hashCode() can be implemented like this:

public class User { public int hashCode() { return new HashCodeBuilder(17, 37). append(id). append(name). append(email). toHashCode(); } }

In general, there's no universal recipe to stick to when it comes to implementing hashCode(). We highly recommend reading Joshua Bloch's Effective Java, which provides a list of thorough guidelines for implementing efficient hashing algorithms.

What can be noticed here is that all those implementations utilize number 31 in some form – this is because 31 has a nice property – its multiplication can be replaced by a bitwise shift which is faster than the standard multiplication:

31 * i == (i << 5) - i

7. Handling Hash Collisions

The intrinsic behavior of hash tables raises up a relevant aspect of these data structures: even with an efficient hashing algorithm, two or more objects might have the same hash code, even if they're unequal. So, their hash codes would point to the same bucket, even though they would have different hash table keys.

This situation is commonly known as a hash collision, and various methodologies exist for handling it, with each one having their pros and cons. Java's HashMap uses the separate chaining method for handling collisions:

“When two or more objects point to the same bucket, they're simply stored in a linked list. In such a case, the hash table is an array of linked lists, and each object with the same hash is appended to the linked list at the bucket index in the array.

In the worst case, several buckets would have a linked list bound to it, and the retrieval of an object in the list would be performed linearly.”

Hash collision methodologies show in a nutshell why it's so important to implement hashCode() efficiently.

Java 8 brought an interesting enhancement to HashMap implementation – if a bucket size goes beyond the certain threshold, the linked list gets replaced with a tree map. This allows achieving O(logn) look up instead of pessimistic O(n).

8. Creating a Trivial Application

To test the functionality of a standard hashCode() implementation, let's create a simple Java application that adds some User objects to a HashMap and uses SLF4J for logging a message to the console each time the method is called.

Here's the sample application's entry point:

public class Application { public static void main(String[] args) { Map users = new HashMap(); User user1 = new User(1L, "John", "[email protected]"); User user2 = new User(2L, "Jennifer", "[email protected]"); User user3 = new User(3L, "Mary", "[email protected]"); users.put(user1, user1); users.put(user2, user2); users.put(user3, user3); if (users.containsKey(user1)) { System.out.print("User found in the collection"); } } } 

And this is the hashCode() implementation:

public class User { // ... public int hashCode() { int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null ? 0 : name.hashCode()); hash = 31 * hash + (email == null ? 0 : email.hashCode()); logger.info("hashCode() called - Computed hash: " + hash); return hash; } }

The only detail worth stressing here is that each time an object is stored in the hash map and checked with the containsKey() method, hashCode() is invoked and the computed hash code is printed out to the console:

[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -282948472 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -1540702691 [main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819 User found in the collection

9. Conclusion

It's clear that producing efficient hashCode() implementations often requires a mixture of a few mathematical concepts, (i.e. prime and arbitrary numbers), logical and basic mathematical operations.

Regardless, it's entirely possible to implement hashCode() effectively without resorting to these techniques at all, as long as we make sure the hashing algorithm produces different hash codes for unequal objects and is consistent with the implementation of equals().

Seperti biasa, semua contoh kode yang ditampilkan di artikel ini tersedia di GitHub.