В Java написание методов equals и hashcode — постоянные проблемы. Как новички, так и эксперты смущаются, когда дела идут плохо, и проблемы с устранением неполадок могут быть чрезвычайно сложными. Обычная вещь, которую может вызвать плохая реализация хэш-кода / равнозначная, — это периодические проблемы и / или таинственные ошибки нехватки памяти. Чтобы прояснить ситуацию, я дам 10 000 кратких обзоров того, как основные библиотеки Java используют методы hashcode / equals.
По сути, методы хэш-кода / равно используются для хранения вещей в хэшах (HashMap, Hashtable, HashSet). Все часто идет не так, когда люди начинают использовать пользовательские объекты в качестве ключей для этих классов. Например, допустим, у нас есть класс person, который выглядит примерно так:
public class Person {
public Person(String orgName) {
this.name = orgName
}
private String name;
public String getName() {
return name;
}
public void setName(String newName) {
this.name = newName;
}
}
Это кажется довольно простым, без сюрпризов, не может быть проще, не так ли?
Теперь допустим, что мы добавили некоторых людей в хэш-сет, представляющий клуб, к которому люди могут принадлежать:
HashSet<Person> myClub = new HashSet<Person>();
Person jsmith = new Person("Joe Smith");
Person sjones = new Person("Sarah Jones");
myClub.add(jsmith);
myClub.add(sjones);
Контракт набора говорит, что он будет гарантировать уникальность … чтобы проверить это, мы можем попытаться добавить дубликат Сары Джонс:
Person sjones2 = new Person("Sarah Jones");
assertTrue(myClub.add(sjones2));
Это говорит нам о том, что мы можем добавить два объекта Person с одинаковыми именами. В нашем странном случае использования мы этого не хотим, мы хотим, чтобы в клубе был только 1 человек «Сара Джонс». Для этого нам нужно написать метод equals, чтобы система знала, что наши люди уникальны по имени. Таким образом, мы переопределяем метод equals в нашем классе, добавляя следующее к Person.
@Override
public equals(Object o) {
if (o == null || o.getClass() != this.getClass()) return false;
Person other = (Person)o;
return other.getName().equals(this.getName());
}
Теперь, если мы попытаемся добавить нашу вторую Сару Джонс, это должно провалиться, верно? Что ж, получается, что это только «может» потерпеть неудачу, но оно также «может» работать (иногда), и это то, где все становится шатким (особенно для новичков). Учтите следующее:
HashSet<Person> myClub = new HashSet<Person>();
Person sjones = new Person("Sarah Jones");
Person sjones2 = new Person("Sarah Jones");
assertEquals(sjones, sjones2);
// Now for the guts
myClub.add(sjones);
assertTrue(myClub.contains(sjones);
//Random failures after here
assertFalse(myClub.add(sjones2));
assertTrue(myClub.contains(sjones2);
Приведенный выше код случайным образом провалит третье и четвертое утверждения без видимой причины. Зачем? Это связано с тем, как реализации Hash * работают в Java. Для действительно хорошей, более глубокой рецензии, иди сюда , но я просто дам краткий обзор.
Реализации Hash * java хранят вещи в контейнерах, обычно со связанными списками (или массивами) в каждом сегменте. Например, тривиальная реализация занимает 10 сегментов, и при сохранении чего-либо она берет хеш-код объекта, выполняет над ним операцию mod-10 и затем добавляет его в связанный список этого сегмента. Проблема с нашей реализацией состоит в том, что мы не переопределяли функцию hashCode, и реализация по умолчанию в java просто использует расположение памяти для результата функции hashCode. Так, например, наш приведенный выше пример будет работать, если произойдет следующее:
- новый hashSet создан
- Sjones создается и хранится в ячейке памяти 4
- sjones2 создается и хранится в ячейке памяти 14
- java сравнивает sjones и sjones2, видит, что они равны, и возвращает true
- java добавляет sjones в myClub, взяв mod-10 sjones (который будет равен 4) и поместив его в список в корзину 4 myClub
- java проверяет, что sjones находится в myClub, захватывая hashCode, видя, что sjones должен быть в сегменте 4, а затем спускаясь по списку, вызывая метод equals для каждого объекта. Там только один и sjones.getName () на самом деле равен sjones.getName (), поэтому его можно найти
- Затем java пытается добавить sjones2, выполнив mod-10 хеш-кода sjones2, посмотрев, что он также должен войти в сегмент 4, а затем пройдясь по списку, чтобы увидеть, существует ли уже sjones. Он видит, что sjones уже существует (потому что sjones.getName () равен sjones2.getName (). Из-за характера контракта HashSet java вернет false, чтобы указать, что sjones2 НЕ было добавлено, потому что оно уже было там.
- Затем java снова будет искать хеш-код sjones2, mod-10, заглядывать в корзину и проверять, что sjones2 фактически находится в наборе … хотя ранее было сказано, что он не был добавлен (что совершенно правильно) и имеет смысл, если вы понимаете, как все должно работать)
Если приведенные выше результаты являются удивительными, вы захотите сделать перерыв, но для тех из вас, кто следит за вами, теперь это становится более интересным. Давайте пройдемся по вышеописанному сценарию, но вместо того, чтобы создать sjones2 в ячейке памяти 14, скажем, она создается в ячейке памяти 17. Это будет означать, что СЕЙЧАС sjones2 будет добавлен в набор, и вы получите дубликаты. Хуже того, если вы назовете это достаточно, у вас может получиться 10 копий объектов Person, которые все равны в наборе. Как это произойдет?
Что ж, мы видим, что для определения «корзины» для поиска объекта java будет использовать хеш-код. Если два «равных» объекта имеют разные хэш-коды, java будет искать неправильный сегмент и НЕ будет его находить. Поскольку реализация по умолчанию использует ячейки памяти в качестве хэш-кода, часто бывает, что все «иногда возможно» работает, но в других случаях происходит полный сбой.
Короче говоря, если у вас странное поведение со сложными типами в наборах или ключах Maps, тщательно проверьте, что все вещи, которые могут быть «равными», будут «всегда» иметь одинаковый hashCode. Обратите внимание, что вещи с одинаковым хэш-кодом НЕ ДОЛЖНЫ быть равными, но это совершенно другое обсуждение.