คำแนะนำเกี่ยวกับ hashCode () ใน Java

1. ภาพรวม

การแฮชเป็นแนวคิดพื้นฐานของวิทยาศาสตร์คอมพิวเตอร์

ใน Java อัลกอริธึมการแฮชที่มีประสิทธิภาพอยู่เบื้องหลังคอลเล็กชันยอดนิยมบางส่วนที่เรามีให้เช่นHashMap (สำหรับข้อมูลเชิงลึกเกี่ยวกับHashMapโปรดตรวจสอบบทความนี้) และHashSet

ในบทความนี้เราจะเน้นไปที่วิธีการทำงานของhashCode ()วิธีการเล่นในคอลเล็กชันและวิธีการนำไปใช้อย่างถูกต้อง

**2. การใช้hashCode ()ในโครงสร้างข้อมูล**

การดำเนินการที่ง่ายที่สุดในคอลเลกชันอาจไม่มีประสิทธิภาพในบางสถานการณ์

ตัวอย่างเช่นสิ่งนี้ทริกเกอร์การค้นหาเชิงเส้นซึ่งไม่ได้ผลอย่างมากสำหรับรายการขนาดใหญ่:

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

Java มีโครงสร้างข้อมูลจำนวนมากสำหรับจัดการกับปัญหานี้โดยเฉพาะตัวอย่างเช่นการใช้งานอินเทอร์เฟซMapหลายรายการเป็นตารางแฮช

เมื่อใช้ตารางแฮชคอลเลคชันเหล่านี้จะคำนวณค่าแฮชสำหรับคีย์ที่กำหนดโดยใช้เมธอดhashCode ()และใช้ค่านี้ภายในเพื่อจัดเก็บข้อมูลเพื่อให้การดำเนินการเข้าถึงมีประสิทธิภาพมากขึ้น

**3. ทำความเข้าใจว่าhashCode ()ทำงานอย่างไร**

พูดง่ายๆคือhashCode ()ส่งกลับค่าจำนวนเต็มซึ่งสร้างโดยอัลกอริทึมการแฮช

ออบเจ็กต์ที่มีค่าเท่ากัน (ตามค่าเท่ากับ () ) จะต้องส่งคืนรหัสแฮชเดียวกัน ไม่จำเป็นสำหรับวัตถุที่แตกต่างกันในการส่งคืนรหัสแฮชที่แตกต่างกัน

สัญญาทั่วไปของhashCode ()ระบุ:

เมื่อใดก็ตามที่เรียกใช้บนอ็อบเจ็กต์เดียวกันมากกว่าหนึ่งครั้งในระหว่างการเรียกใช้แอ็พพลิเคชัน Java hashCode ()จะต้องส่งคืนค่าเดียวกันอย่างสม่ำเสมอโดยไม่มีการแก้ไขข้อมูลที่ใช้ในการเปรียบเทียบเท่ากับอ็อบเจ็กต์ ค่านี้ไม่จำเป็นต้องคงที่ตั้งแต่การเรียกใช้งานแอปพลิเคชันหนึ่งไปจนถึงการเรียกใช้งานแอปพลิเคชันอื่น

ถ้าวัตถุสองชิ้นมีค่าเท่ากันตามวิธีการเท่ากับ (Object)ดังนั้นการเรียกใช้เมธอดhashCode ()บนแต่ละวัตถุทั้งสองจะต้องสร้างค่าเดียวกัน

ไม่จำเป็นว่าถ้าสองอ็อบเจ็กต์ไม่เท่ากันตามเมธอดequals (java.lang.Object)การเรียกเมธอดhashCodeบนอ็อบเจ็กต์ทั้งสองแต่ละอ็อบเจ็กต์จะต้องให้ผลลัพธ์จำนวนเต็มที่แตกต่างกัน อย่างไรก็ตามนักพัฒนาควรทราบว่าการสร้างผลลัพธ์จำนวนเต็มที่แตกต่างกันสำหรับอ็อบเจ็กต์ที่ไม่เท่ากันจะช่วยเพิ่มประสิทธิภาพของตารางแฮช

“ เท่าที่ใช้งานได้จริงวิธีhashCode () ที่กำหนดโดยคลาสObjectจะส่งคืนจำนวนเต็มที่แตกต่างกันสำหรับอ็อบเจ็กต์ที่แตกต่างกัน (โดยทั่วไปจะดำเนินการโดยการแปลงที่อยู่ภายในของวัตถุเป็นจำนวนเต็ม แต่ภาษาโปรแกรม Java ™ไม่จำเป็นต้องใช้เทคนิคการใช้งานนี้)”

**4. การใช้งานhashCode ที่ไร้เดียงสา()**

จริงๆแล้วมันค่อนข้างตรงไปตรงมาที่จะมีการใช้งานhashCode () ที่ไร้เดียงสาซึ่งปฏิบัติตามสัญญาข้างต้นอย่างสมบูรณ์

เพื่อแสดงให้เห็นถึงสิ่งนี้เราจะกำหนดคลาสผู้ใช้ตัวอย่างที่แทนที่การใช้งานเริ่มต้นของวิธีการ:

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 }

ผู้ใช้ระดับให้การใช้งานที่กำหนดเองสำหรับทั้งสองเท่ากับ ()และhashCode ()อย่างเต็มที่กับการทำสัญญาที่เกี่ยวข้องปฏิบัติตาม ยิ่งไปกว่านั้นไม่มีอะไรผิดกฎหมายด้วยการมีhashCode ()ส่งคืนค่าคงที่ใด ๆ

อย่างไรก็ตามการนำไปใช้งานนี้ทำให้ฟังก์ชันการทำงานของตารางแฮชลดลงเป็นศูนย์เนื่องจากทุกออบเจ็กต์จะถูกเก็บไว้ในที่เก็บข้อมูลเดียว

ในบริบทนี้การค้นหาตารางแฮชจะดำเนินการแบบเชิงเส้นและไม่ได้ให้ข้อได้เปรียบที่แท้จริงแก่เรา - เพิ่มเติมเกี่ยวกับเรื่องนี้ในส่วนที่ 7

**5. การปรับปรุงhashCode ()การดำเนินงาน**

มาปรับปรุงการใช้งานhashCode ()ปัจจุบันเล็กน้อยโดยรวมฟิลด์ทั้งหมดของคลาสUserเพื่อให้สามารถสร้างผลลัพธ์ที่แตกต่างกันสำหรับอ็อบเจ็กต์ที่ไม่เท่ากัน:

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

อัลกอริทึมนี้คร่ำเครียดพื้นฐานคือการแตกหักมากดีกว่าก่อนหน้านี้หนึ่งขณะที่มันคำนวณรหัสแฮชของวัตถุโดยเพียงแค่คูณรหัสกัญชาของชื่อและอีเมลสาขาและรหัส

โดยทั่วไปแล้วเราสามารถพูดได้ว่านี่เป็นการใช้งานhashCode () ที่สมเหตุสมผลตราบเท่าที่เรายังคงการใช้งานequals () ให้สอดคล้องกับมัน

**6. การใช้งานhashCodeมาตรฐาน()**

ยิ่งอัลกอริทึมการแฮชที่เราใช้ในการคำนวณรหัสแฮชดีเท่าใดประสิทธิภาพของตารางแฮชก็จะดีขึ้นเท่านั้น

มาดูการใช้งาน "มาตรฐาน" ที่ใช้ตัวเลขสองค่าเพื่อเพิ่มความเป็นเอกลักษณ์ให้กับรหัสแฮชที่คำนวณได้มากขึ้น:

@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; }

ในขณะที่จำเป็นต้องเข้าใจบทบาทที่hashCode ()และequals ()วิธีการเล่น แต่เราไม่จำเป็นต้องใช้งานตั้งแต่เริ่มต้นทุกครั้งเนื่องจาก IDE ส่วนใหญ่สามารถสร้างการใช้งานhashCode ()และequals () ที่กำหนดเองได้และตั้งแต่ Java 7 เป็นต้นไป เรามีวิธียูทิลิตี้Objects.hash ()สำหรับการแฮชที่สะดวกสบาย:

Objects.hash(name, email)

IntelliJ IDEA สร้างการใช้งานต่อไปนี้:

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

และ Eclipse สร้างสิ่งนี้:

@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; }

นอกเหนือจากการใช้งานhashCode ()ตาม IDE ข้างต้นแล้วยังสามารถสร้างการใช้งานที่มีประสิทธิภาพโดยอัตโนมัติตัวอย่างเช่นการใช้ Lombok ในกรณีนี้ต้องเพิ่มการพึ่งพา lombok-maven ใน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().

เช่นเคยตัวอย่างโค้ดทั้งหมดที่แสดงในบทความนี้มีอยู่ใน GitHub