Попадание в серую область "вкл / выкл темы", но необходимо, чтобы устранить путаницу в отношении предположения Оскара Рейеса о том, что большее число коллизий хешей - хорошая вещь, потому что это уменьшает количество элементов в HashMap. Я могу неправильно понять, что говорит Оскар, но я, кажется, не единственный: kdgregory, delfuego, Nash0, и я, кажется, все разделяю то же (неправильное) понимание.
Если я понимаю, что Оскар говорит об одном и том же классе с тем же хеш-кодом, он предлагает добавить в HashMap только один экземпляр класса с заданным хеш-кодом. Например, если у меня есть экземпляр SomeClass с хэш-кодом 1 и второй экземпляр SomeClass с хэш-кодом 1, вставляется только один экземпляр SomeClass.
Пример Java pastebin на http://pastebin.com/f20af40b9, кажется, указывает на то, что вышеизложенное правильно суммирует то, что предлагает Оскар.
Независимо от какого-либо понимания или недопонимания, что происходит, если различные экземпляры одного и того же класса не вставляются только один раз в HashMap, если они имеют один и тот же хэш-код - только до тех пор, пока не будет установлено, равны ли ключи или нет. Контракт хеш-кода требует, чтобы равные объекты имели одинаковый хеш-код; однако не требуется, чтобы неравные объекты имели разные хеш-коды (хотя это может быть желательно по другим причинам) [1].
Ниже приведен пример pastebin.com/f20af40b9 (на который Оскар ссылается как минимум дважды), но слегка измененный для использования утверждений JUnit, а не линий печати. Этот пример используется для поддержки предложения о том, что одни и те же хеш-коды вызывают коллизии, и когда классы одинаковы, создается только одна запись (например, только одна строка в данном конкретном случае):
@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
String s = new String("ese");
String ese = new String("ese");
// same hash right?
assertEquals(s.hashCode(), ese.hashCode());
// same class
assertEquals(s.getClass(), ese.getClass());
// AND equal
assertTrue(s.equals(ese));
Map map = new HashMap();
map.put(s, 1);
map.put(ese, 2);
SomeClass some = new SomeClass();
// still same hash right?
assertEquals(s.hashCode(), ese.hashCode());
assertEquals(s.hashCode(), some.hashCode());
map.put(some, 3);
// what would we get?
assertEquals(2, map.size());
assertEquals(2, map.get("ese"));
assertEquals(3, map.get(some));
assertTrue(s.equals(ese) && s.equals("ese"));
}
class SomeClass {
public int hashCode() {
return 100727;
}
}
Однако, хэш-код не полная история. То, что игнорирует пример pastebin, это то, что оба s и ese равны: они оба являются строкой "ese". Таким образом, вставка или получение содержимого карты с использованием s или ese или "ese" в качестве ключа эквивалентны, поскольку s.equals(ese) && s.equals("ese").
Второй тест показывает, что ошибочно заключать, что идентичные хэш-коды в одном и том же классе являются причиной того, что ключ -> значение s -> 1 перезаписывается на ese -> 2, когда map.put(ese, 2) вызывается в первом тесте. Во втором тесте s и ese по-прежнему имеют один и тот же хэш-код (что подтверждено assertEquals(s.hashCode(), ese.hashCode());) И они того же класса. Однако s и ese являются экземплярами MyString в этом тесте, а не экземплярами Java String - единственная разница, относящаяся к этому тесту, равна: String s equals String ese в тесте выше, тогда как MyStrings s does not equal MyString ese в Тест два:
@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
MyString s = new MyString("ese");
MyString ese = new MyString("ese");
// same hash right?
assertEquals(s.hashCode(), ese.hashCode());
// same class
assertEquals(s.getClass(), ese.getClass());
// BUT not equal
assertFalse(s.equals(ese));
Map map = new HashMap();
map.put(s, 1);
map.put(ese, 2);
SomeClass some = new SomeClass();
// still same hash right?
assertEquals(s.hashCode(), ese.hashCode());
assertEquals(s.hashCode(), some.hashCode());
map.put(some, 3);
// what would we get?
assertEquals(3, map.size());
assertEquals(1, map.get(s));
assertEquals(2, map.get(ese));
assertEquals(3, map.get(some));
}
/**
* NOTE: equals is not overridden so the default implementation is used
* which means objects are only equal if they're the same instance, whereas
* the actual Java String class compares the value of its contents.
*/
class MyString {
String i;
MyString(String i) {
this.i = i;
}
@Override
public int hashCode() {
return 100727;
}
}
Основываясь на последующем комментарии, Оскар, похоже, полностью меняет сказанное ранее и признает важность равенства. Тем не менее, все еще кажется, что понятие «равно» - это то, что важно, а не «тот же класс», неясно (выделено мной):
"Не совсем. Список создается только в том случае, если хеш такой же, но ключ другой. Например, если строка дает хеш-код 2345, а Integer дает тот же хэш-код 2345, то вставляется целое число в список, потому что String.equals (Integer) имеет значение false. Но если у вас тот же класс (или хотя бы .equals возвращает true) , тогда используется та же запись. Например, new String ("one") ) и `new String (" one "), используемые в качестве ключей, будут использовать одну и ту же запись. На самом деле это ВСЕ точка HashMap на первом месте! Смотрите сами: pastebin.com/f20af40b9 - Оскар Рейес"
по сравнению с предыдущими комментариями, которые явно указывают на важность идентичного класса и того же хеш-кода, без упоминания равных:
"@ delfuego: убедитесь сами: pastebin.com/f20af40b9 Итак, в этом вопросе используется один и тот же класс (подождите минуту, тот же класс используется правильно?) Что означает, что когда тот же самый используется хэш, используется та же самая запись, и нет «списка» записей. - Оскар Рейес "
или
"На самом деле это увеличит производительность. Чем больше коллизий, тем меньше записей в хеш-таблице, тем меньше работы. Это не хеш (который выглядит хорошо), ни хеш-таблица (который работает отлично), я бы поспорил это на создании объекта, где производительность ухудшается. - Оскар Рейес "
или
"@ kdgregory: Да, но только если столкновение происходит с разными классами, для одного и того же класса (что имеет место) используется одна и та же запись. - Оскар Рейес"
Опять же, я могу неправильно понять, что на самом деле пытался сказать Оскар. Тем не менее, его первоначальные комментарии вызвали достаточно путаницы, так что кажется разумным разобраться во всем с помощью некоторых явных тестов, чтобы не было никаких сомнений.
[1] - Из Effective Java, Второе издание , Джошуа Блох:
Всякий раз, когда он вызывается для одного и того же объекта более одного раза во время выполнения приложения, метод hashCode должен последовательно возвращать
то же самое целое, при условии, что информация не используется в равных с сравнениях на
объект изменен Это целое число не обязательно должно быть согласованным при выполнении одного приложения другим исполнением того же приложения.
Если два объекта равны в соответствии с методом равным s (Obj ect), то вызов метода hashCode для каждого из двух объектов должен привести к одинаковому результату.
целочисленный результат.
Не требуется, чтобы, если два объекта были неравны в соответствии с методом равным s (Object), то вызывался метод hashCode для каждого из двух объектов.
должен давать разные целочисленные результаты. Тем не менее, программист должен быть
осознавая, что получение различных целочисленных результатов для неравных объектов может улучшить
производительность хеш-таблиц.