Хеширование и хеш-коды
В предыдущем примере класс стандартной библиотеки (Integer) использовался в качестве ключа для HashMap. Он великолепно работает в качестве ключа, потому что он имеет все необходимые записи, чтобы корректно работать в качестве ключа. Но основные ловушки, случающиеся с HashMap, возникают тогда, когда вы создаете свой собственный класс для использования в качестве ключа. Например, рассмотрим систему прогнозирования погоды, которая ставит в соответствие объекты Groundhog с объектами Prediction. Это кажется достаточно просто: вы создаете два класса и используете Groundhog в качестве ключа, а Prediction в качестве значения:
//: c09:SpringDetector.java
// выглядит правдоподобно, но не работает.
import java.util.*;
class Groundhog { int ghNumber; Groundhog(int n) { ghNumber = n; } }
class Prediction { boolean shadow = Math.random() > 0.5; public String toString() { if(shadow) return "Six more weeks of Winter!"; else
return "Early Spring!"; } }
public class SpringDetector { public static void main(String[] args) { HashMap hm = new HashMap(); for(int i = 0; i < 10; i++) hm.put(new Groundhog(i), new Prediction()); System.out.println("hm = " + hm + "\n"); System.out.println( "Looking up prediction for Groundhog #3:"); Groundhog gh = new Groundhog(3); if(hm.containsKey(gh)) System.out.println((Prediction)hm.get(gh)); else
System.out.println("Key not found: " + gh); } } ///:~
Каждому Groundhog дан идентификационный номер, так что вы можете искать Prediction в HashMap, говоря: “Дайте мне Prediction, ассоциированный с Groundhog под номером 3”. Класс Prediction содержит boolean, который инициализируется с использованием Math.random( ), и toString( ), который интерпретирует результат для вас. В main( ) заполняется HashMap с помощью Groundhog и ассоциированными Prediction. HashMap печатается, так что вы можете видеть, как он заполнен. Затем Groundhog с идентификационным номером 3 используется в качестве ключа для поиска прогноза для Groundhog №3 (который, как вы видите, должен быть в Map).
Это выглядит достаточным, но это не работает. Проблема в том, что Groundhog наследуется от общего корневого класса Object (что происходит в том случае, когда вы не указываете базовый класс, так как все классы наследуются от Object). Этот метод hashCode( ) класса Object используется для генерации хеш кода для каждого объекта, а по умолчанию он просто использует адрес этого объекта. Таким образом, первый экземпляр Groundhog(3) не производит хеш код, равный хеш коду для второго экземпляра Groundhog(3) который мы пробуем использовать для поиска.
Вы можете подумать, что все, что вам нужно сделать, это написать соответствующую перегрузку для hashCode( ). Но это все равно не будет работать, пока вы не сделаете еще одну вещь: перегрузка метода equals( ), который тоже является частью Object. Этот метод используется HashMap когда происходит попытка определить, что ваш ключ равен ключу из таблицы. Опять таки, по умолчанию Object.equals( ) просто сравнивает адреса объектов, так что один Groundhog(3) не равен другому Groundhog(3).
Таким образом, для использования вашего собственного класса в качестве ключа в HashMap, вы должны перегрузить и hashCode( ), и equals( ), как показано в следующем решении возникшей выше проблемы:
//: c09:SpringDetector2.java
// Класс, который используется в качестве ключа в HashMap,
// должен перегружать hashCode() и equals().
import java.util.*;
class Groundhog2 { int ghNumber; Groundhog2(int n) { ghNumber = n; } public int hashCode() { return ghNumber; } public boolean equals(Object o) { return (o instanceof Groundhog2) && (ghNumber == ((Groundhog2)o).ghNumber); } }
public class SpringDetector2 { public static void main(String[] args) { HashMap hm = new HashMap(); for(int i = 0; i < 10; i++) hm.put(new Groundhog2(i),new Prediction()); System.out.println("hm = " + hm + "\n"); System.out.println( "Looking up prediction for groundhog #3:"); Groundhog2 gh = new Groundhog2(3); if(hm.containsKey(gh)) System.out.println((Prediction)hm.get(gh)); } } ///:~
Обратите внимание, что здесь используется класс Prediction из предыдущего примера, так что SpringDetector.java должен быть откомпилирован первым или вы получите ошибку времени компиляции, когда попробуете откомпилировать SpringDetector2.java.
Groundhog2.hashCode( ) возвращает номер groundhog в качестве идентификатора. В этом примере программист отвечает за то, что не будет существовать два одинаковых groundhog с одним и тем же идентификационным номером. hashCode( ) не требует возврата уникального идентификатора (кое-что вы поймете лучше позднее в этой главе), но метод equals( ) должен быть способен точно определить равны два объекта или нет.
Даже притом, что метод equals( ) только проверяет, является ли аргумент экземпляром Groundhog2 (использование ключевого слова instanceof будет полностью объяснено в Главе 12), instanceof на самом деле спокойно выполняет вторую необходимую проверку, проверяет, что объект - это не null, так как instanceof производит false, если левый аргумент - это null. Принимая это во внимание, получаем, что необходимо соответствие типов и не null, сравнение основывается на реальных ghNumber. Когда вы запустите программу, вы увидите что получаете на выходе правильный результат.
Когда создаете ваши собственные класса для использования в HashSet, вы должны уделять внимание тем же проблемам, что и при использовании в качестве ключей в HashMap.
