HOWTO: วิธีการ override hashCode() อย่างง่าย
posted on 17 Dec 2008 16:03 by sonicneo in Javaอย่าง ที่พอจะทราบกันแล้วว่า เมื่อไหร่ก็ตามที่เราทำการ override equals() แล้ว เราต้องทำการ override hashCode() ด้วยเสมอ เพื่อรักษาข้อตกลง (contract) ของ hashCode() ที่ว่าทุก object ที่เหมือนหรือเท่ากันจากการทดสอบด้วย equals() จะต้องมีค่า hash code เท่ากันเสมอ
ทั้งนี้ก็เพราะว่า วิธีการทำงาน (implementation) ของ hashCode() ที่ได้รับสืบทอดมาจาก Object จะให้ค่า hash code ที่ไม่ได้ขึ้นอยู่กับค่าข้อมูลของ instance variable ของ object ค่าที่ได้เป็นเพียงค่า integer ตัวหนึ่งสำหรับ object นั้น ทำให้ object สองตัวที่ถึงแม้จะเปรียบเทียบแล้วว่าเท่ากันด้วย equals() แต่ก็มี hash code ต่างกัน เมื่อนำ object นี้ไปใช้ใน HashMap หรือ Hashtable จะทำให้ทำงานผิดพลาดได้
ว่าแต่ hash code คืออะไรกัน ? hash code ก็เป็นเพียงค่า integer ค่าหนึ่งที่ได้จากการทำ hashing กับข้อมูลชุดหนึ่ง (คือการนำค่าของข้อมูลชุดหนึ่ง อย่างเช่น ชื่อ ไปผ่าน hashing function หรือ algorithm ที่ใช้สร้างค่า integer ทำให้ได้ค่า integer ออกมาค่าหนึ่ง ที่จะใช้แทนตัวข้อมูลนั้นได้ โดยมีหลักสำคัญอยู่ว่า ถ้าเป็นข้อมูลชุดเดียวกัน จะต้องมีค่า hash code เท่ากันเสมอ) ค่า hash code นี้จะมีความสำคัญอย่างมาก เมื่อเราต้องใช้งาน data structure ที่มีการทำงานโดยอาศัยเรื่องของ hashing อย่างเช่น HashMap, HashSet และ Hashtable
ขั้นตอนการ override hashCode() อย่างง่าย มีดังนี้
1. ทำการ override hashCode() ที่ได้รับสืบทอดมาจาก Object โดยเพิ่ม method declaration เข้าไปในคลาสที่เราเขียนขึ้น ดังนี้
public int hashCode() {
}
2. ทำการคำนวณหาค่า hash code จากค่าของตัวแปร instance variable ทั้งหมดที่มีในคลาสที่เราเขียน (ตัวแปรเหล่านี้จะต้องเป็นตัวแปรที่เราใช้ใน การเปรียบเทียบของ equals() ด้วย) โดยใช้วิธีการคำนวณหาค่า hash code ที่อธิบายไว้ใน [Bloch2001] ดังนี้
2.1 ให้ค่าเริ่มต้นกับ hash code ผลลัพท์ เป็นค่า integer อะไรก็ได้ อย่างเช่น 17 โดยเก็บไว้ในตัวแปร integer ตัวหนึ่ง อย่างเช่น result
2.2 หาค่า hash code ของแต่ล่ะ instance variable ของคลาสที่เราเขียน เพื่อนำมาคำนวณร่วมกับค่าเริ่มต้นของ hash code ผลลัพท์ ที่เก็บไว้ในตัวแปร result วิธีการหาค่า hash code ของแต่ล่ะ instance variable มีดังนี้
- ถ้าเป็นตัวแปรชนิด boolean ให้หาค่า hash code จาก (f ? 0 :1)
- ถ้าเป็นตัวแปรชนิด bye, char, short, int ให้หาค่า hash code จาก (int) f
- ถ้าเป็นตัวแปรชนิด long ให้หาค่า hash code จาก (int) (f ^ (f >>> 32))
- ถ้าเป็นตัวแปรชนิด float ให้หาค่า hash code จาก Float.floatToIntBits(f)
- ถ้าเป็นตัวแปรชนิด double ให้เริ่มจากหา Double.doubleToLongBits(f) ก่อน แล้วทำการหาค่า hash code โดยใช้วิธีการหาค่า hash code ของตัวแปรชนิด long อีกที
- ถ้าตัวแปรเป็น reference ของ object ให้หาค่า hash code จากการเรียก hashCode() ของ object นั้น ในกรณีที่ reference นั้นเป็น null ให้ ค่า hash code ที่ได้เป็น 0 หรือค่าคงที่อื่น ๆ
- ถ้าตัวแปรนั้นเป็น array ให้มองว่าสมาชิกแต่ล่ะตัวใน array นั้นก็เป็นเหมือนตัวแปรตัวหนึ่ง ให้ใช้หลักการข้างต้นในการหาค่า hash code ของสมาชิกแต่ล่ะตัว
2.3 ให้นำค่า hash code ของ instance variable ที่คำนวณได้จาก (2.2) มาคำนวณร่วมกับตัวแปร result ดังนี้
result = result * 37 + c; // ให้ c เป็นค่า hash code ของตัวแปรที่คำนวณได้จาก (2.2)
2.4 หาค่า hash code ของแต่ล่ะตัวแปรในคลาส แล้วนำมาคำนวณร่วมกับตัวแปร result จนครบทุกตัวแปรในคลาส ค่าที่ได้จะเป็นค่า hash code ผลลัพท์ ให้ค่าผลลัพท์ที่ได้เป็นค่าที่จะใช้ return สำหรับ hashCode()
3. ตรวจสอบว่าค่า hash code ที่ได้จาก hashCode() เป็นไปตามข้อตกลง (contract) ที่กำหนดไว้สำหรับ hashCode() ดังนี้
- เมื่อเรียกใช้ hashCode() ของ object ตัวหนึ่งมากกว่า 1 ครั้ง ค่าที่ได้จะต้องเป็นค่าเดิมเสมอ กำหนดให้ค่า instance variable ภายใน object นั้นไม่มีการเปลี่ยนแปลง
- เมื่อเปรียบเทียบ object สองตัวด้วย equals() แล้วปรากฏว่าเท่ากัน ค่า hash code ที่ได้จากการเรียก hashCode() ของแต่ล่ะ object จะต้องเป็นค่าเดียวกัน
- ถ้าเปรียบเทียบ object สองตัวด้วย equals() แล้วปรากฏว่าไม่เท่ากัน ค่า hash code ที่ได้จากการเรียก hashCode() ของแต่ล่ะ object ไม่จำเป็นต้องเท่ากันก็ได้ แต่การที่ object ที่ไม่เท่ากันมีค่า hash code ที่ต่างกันจะช่วยทำให้ data structure อย่างเช่น HashMap, HashSet, Hashtable ทำงานได้อย่างมีประสิทธิภาพมากขึ้น
Example
จากตัวอย่างของบทความ "วิธีการ override equals() อย่างง่าย" เราสามารถ override hashCode() ของ Employee ได้ดังนี้
import java.util.*;
public class Employee {
private String _name; // ชื่อ
private int _age; // อายุ
private double _salary; // เงินเดือน
public Employee(String name, int age, double salary) {
_name = name;
_age = age;
_salary = salary;
}
public boolean equals(Object o) { // เพิ่ม method declaration เพื่อ override equals()
if (!(o instanceof Employee)) // (2) ตรวจสอบว่าเป็น object ของคลาสที่เราเขียน
return false;
Employee e = (Employee) o; // (3) cast object ที่รับมาให้เป็นชนิดของคลาสที่เราเขียน
// (4) เปรียบเทียบค่าภายใน object แต่ล่ะค่าว่าเท่ากันหรือไม่
return _name.equals(e._name) && _age == e._age && Double.doubleToLongBits(_salary) ==
Double.doubleToLongBits(e._salary); }
public int hashCode() {
int result = 17; // ให้ค่าเริ่มต้นกับค่า hash code ผลลัพท์
// หาค่า hash code ของ _name แล้วนำมาคำนวณร่วมกับ result ตามสมการใน (2.3)
result = 37 * result + _name.hashCode();
result = 37 * result + _age; // หาค่า hash code ของ _age แล้วนำมาคำนวณร่วมกับ result
// หาค่า hash code ของ _salary แล้วนำมาคำนวณร่วมกับ result
long temp = Double.doubleToLongBits(_salary);
result = 37 * result + ((int) (temp ^ (temp >>> 32)));
// ค่าผลลัพท์สุดท้ายที่ได้จะเป็นค่า hash code ของ object return result; }
public static void main(String[] args) {
Employee e1 = new Employee("John", 20, 25000.0);
Employee e2 = new Employee("John", 20, 25000.0);
// ทดลองใช้งาน Employee กับ HashMap
HashMap map = new HashMap();
map.put(e1, "John"); // ใส่ e1 ใน HashMap System.out.println(map.get(e2)); // ทดลองดึง e1 จาก HashMap โดยใช้ e2 ในการหา } }