Использование HashTable без переопределения hashcode ()

Сегодня мне задали этот вопрос во время интервью:

  

Что произойдет, если мы не переопределим метод hashcode для нашего   класс, затем добавьте его в HashTable, а затем попытайтесь получить объекты?

Что может пойти не так?

6 голосов | спросил VextoR 16 PMpMon, 16 Apr 2012 12:06:43 +040006Monday 2012, 12:06:43

8 ответов


18

Идея с HashTable при попытке получить объект заключается в том, что структура данных вычисляет хэш-код объекта с помощью ---- +: = 1 =: + ----, а затем просматривается список с помощью GetHashCode().

При реализации по умолчанию Equals() два совершенно похожих объекта могут привести к различным хеш-кодам, что означает, что если вы не используете точные тот же экземпляр, вы никогда не найдете свой объект в GetHashCode().

В общем, вы хотите убедиться в двух вещах при реализации хеш-кодов:

  • Если HashTable, то A.Equals(B)
  • Постарайтесь правильно распределить распределение хеш-кодов, чтобы получить максимальную эффективность из хеш-таблицы (если слишком мало хэш-кодов возможно, вы окажетесь в поиске списка).
ответил SRKX 16 PMpMon, 16 Apr 2012 12:24:30 +040024Monday 2012, 12:24:30
6

Ответ «ничего плохого, если вы не переопределили equals()".

Общая точка состоит в том, что если два объекта сравниваются равными, т.е. если

 a.equals(b)

, то они должны иметь один и тот же хэш-код i.e.

 a.hashCode() == b.hashCode()

также, если два объекта имеют разные хэш-коды, они не должны сравнивать одинаковые.

Это особенно актуально, если вы помещаете объекты в хеш-таблицу. Это связано с тем, что хеш-таблица представляет собой массив списков (обычно называемых ведрами). Ведро hash индексируется с использованием хеш-кода, обычно вы используете hashCode % arraySize.

Поэтому, когда вы помещаете объект в хеш-таблицу, вы берете хэш-код ключа и используете его для определения ведра. Затем вы помещаете пару ключ-значение в ведро. Когда вы хотите получить объект из хеш-таблицы, вы берете хэш-код ключа для поиска ведра и проверяете ключ всех пар ключ-значение в ковше с помощью .equals(), чтобы определить, какой именно объект вам нужен.

Итак, если у вас есть два ключевых объекта, которые сравнивают одинаковые, но имеют разные хеш-коды, и вы используете их как ключ в хеш-таблице, вы не сможете его искать с помощью другого ключевого объекта, потому что вы будете глядя в неправильное ведро.

Реализация equals() в Object возвращает только true, если оба объекта фактически являются одним и тем же объектом и hashCode() возвращает ссылку на объект. Однако, если вы переопределяете equals() (например, String делает так, чтобы разные строки, содержащие одну и ту же последовательность символов, сравнивали одинаковые), вы должны переопределить hashCode()

ответил JeremyP 16 PMpMon, 16 Apr 2012 19:22:47 +040022Monday 2012, 19:22:47
6
  

Что произойдет, если мы не переопределим метод hashcode для нашего класса, а затем добавим его в HashTable, а затем попытаемся получить объекты?

Это зависит от того, что означает «добавление в HashTable». Java Hashtable не имеет add. Вероятно, интервьюер имел в виду метод put, который принимает ключ и значение , Значение может быть любым (может быть даже null в HashMap, который является текущей версией Hashtable). Ничего особенного не происходит независимо от того, переопределяете ли вы хэш-код объекта значения или какой-либо другой метод.

Интервьюер, вероятно, имел в виду, что хэш-код ключевого объекта не будет переопределен. Только тогда проблемы с идентификацией объекта, как указано в других ответах, вступают в игру. Даже тогда вы не обязательно должны переопределять хэш-код ключа. Например, если вы используете String s как ключи, у них уже есть соответствующая реализация хэш-кода. Кроме того, они не могут быть подклассами. Кроме того, если вы do переопределите hashcode, но do not переопределите equals, вы можете получить какое-то потрясающее поведение ...

Если бы вопрос действительно был именно тем, что вы написали, я бы дразнил интервьюера этими вопросами. Хороший программист не полагает , что интервьюер, вероятно, имел в виду то или это. Он спрашивает об этом.

ответил Joonas Pulakka 16 PMpMon, 16 Apr 2012 12:29:14 +040029Monday 2012, 12:29:14
4

вы не найдете свой объект, если у вас есть другой объект, который equal для объекта, который вы положили

или для примера:

MyClass obj1 = new MyClass(1);
MyClass obj2 = new MyClass(1);
assert obj1.equals(obj2);
assert obj1.hashcode()!=obj2.hashcode(); //this is wat happens if you don't inclde hashcode
table.put(obj1,2);
table.get(obj2) // will likely return null but that is a gamble
table.get(obj1) // but this will return the object passed in

причина этого в том, что HashTable (и HashMap) будет использовать хэш-код для ограничения пространства, которое он должен выполнить для поиска, чтобы найти объект, и полагается на предположение, что если obj1.equals(obj2), затем obj1.hashcode == obj2.hashcode()

ответил ratchet freak 16 PMpMon, 16 Apr 2012 12:19:05 +040019Monday 2012, 12:19:05
3

Я бы добавил, что все эти понятия должны соответствовать identity и сравнению .

Существует контракт с хэш-кодом:

1.) Всякий раз, когда он вызывается на одном и том же объекте более одного раза во время выполнения приложения Java, метод hashCode должен последовательно возвращать одно и то же целое число, если информация, используемая при равных сравнениях с объектом, не изменяется. Это целое число не должно оставаться согласованным с одним исполнением приложения на другое выполнение того же приложения.

2.) Если два объекта равны в соответствии с методом equals (Object), то вызов метода hashCode для каждого из двух объектов должен приводить к одному и тому же целочисленному результату.

3.) Не требуется, чтобы, если два объекта не равны по методу equals (java.lang.Object), то вызов метода hashCode для каждого из двух объектов должен производить различные целочисленные результаты. Тем не менее, программист должен знать, что получение отдельных целочисленных результатов для неравных объектов может улучшить производительность хеш-таблиц.

Результат состоит в том, что если хэш-коды совпадают, записи в таблице переписывают друг друга, и это может быть удивительно для некоторых ...

Надеюсь, что это поможет.

ответил rich_markle 17 AMpTue, 17 Apr 2012 01:21:46 +040021Tuesday 2012, 01:21:46
2

Ответ: похожие объекты (все поля с равными значениями) не будут создавать один и тот же хеш-код, поэтому вам понадобится точно такой же (идентичный) объект, который использовался для put, чтобы извлечь из хеш-таблицы, что в большинстве случаев не представляется возможным.

ответил user281377 16 PMpMon, 16 Apr 2012 12:18:31 +040018Monday 2012, 12:18:31
2

Предполагая, что ваш класс расширяет только Object, тогда hashCode() реализация вашего класса будет зависеть от идентификатора объекта . То есть что хэш-код двух разных экземпляров (почти наверняка) будет отличаться, даже если они содержат то же самое значение.

Это означает, что вы скорее всего не найдете объект снова на карте (вы можете найти его случайно).

ответил Joachim Sauer 16 PMpMon, 16 Apr 2012 12:20:23 +040020Monday 2012, 12:20:23
1

Если метод hashcode не переопределен, ответ на этот вопрос действительно зависит от того, был ли тот же ключевой объект, который использовался для "put" будет использоваться для "get":

a) Если используется один и тот же ключевой объект - "get" найдет значение. Поскольку он найдет ведро, используя тот же "key" и, следовательно, найдет объект value.

b) Если используется какой-либо другой «эквивалентный» ключевой объект - поскольку, возможно, хэш-код будет отличаться из-за реализации по умолчанию метода hashcode в Object и, следовательно, он может попасть в другое ведро и, возможно, не сможет получить объект значения.

ответил java_mouse 16 PMpMon, 16 Apr 2012 19:42:57 +040042Monday 2012, 19:42:57

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132