Вот, решил что хватит по верхушкам бродить. Не стыжусь спросить.
Копнул, и выяснилось что я до конца не понимаю смысла хеш-кода у Object и правила его формирования.
Хелп:
The general contract of hashCode is:

-Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

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


-If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

т.е. 2 одинаковых объекта имеют один хеш-код. тут понятно. но не до конца понятно - что есть 2 именно одинаковых объекта.

т.е.
TTst a,b;
a=new TTst;
b=new TTst;
a.equals(b) - true или false?

а после
a.prop1=1;
b.prop1=2;
a.equals(b) - true или false?

т.к. про equals написано:
==========
The equals() method compares two objects of the same type for equality

by comparing the properties of both objects.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

It simply returns a boolean value depending on the results of the object that calls it and the object that is passed to it. For instance, if equals() is called by an object that passes it an object that is identical, the equals() method returns a true value
=============

-It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables

тут говорят что если a.euals(b)==false - то хешкод у a и b - разный. так?

что-то я запутался.
поставте обратно меня на рельсы, а?
Спасибо!

Цитата(Sleepy_PIP @ 13.5.2005, 01:48)

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

Да.

Цитата(Sleepy_PIP @ 13.5.2005, 01:48)

т.е. 2 одинаковых объекта имеют один хеш-код. тут понятно. но не до конца понятно - что есть 2 именно одинаковых объекта.

Это два объекта, для которых equals возвращает true.

Цитата(Sleepy_PIP @ 13.5.2005, 01:48)

тут говорят что если a.euals(b)==false - то хешкод у a и b - разный. так?

Да.

Если вкратце: equals ДОЛЖЕН ПО ИДЕЕ возвращать true если оба объекта одинаковы по свойствам. Но по умолчанию, если его не переопределить, он возвратит то же, что и ==.
А == сравнивает ссылки, и возвращает тру если обе ссылки ссылаются на один объект. equals ты можешь определять как угодно, по равенству всех полей, или некоторых полей.

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

Большое СПАСИБО!

Если hashCode не переопределить, то нельзя будет класс использовать в HashMap, HashSet и т.п. в качестве ключей. Потому что они сначала ищут по hashCode, а только потом по equals.

Не будет ничего страшного если реализовать hashCode() как return 13; Конечно в HashMap, HashSet все сведется к полному перебору.
Отсюда следствие: hashCode должен просто обеспечивать какой-то разброс значений для разных объектов, поэтому лучше использовать какое-то сравнительно уникальное поле и возвращать его hashCode

Цитата(hatsumeika @ 14.5.2005, 09:28)

Если hashCode не переопределить, то нельзя будет класс использовать в HashMap, HashSet и т.п. в качестве ключей. Потому что они сначала ищут по hashCode, а только потом по equals.

Неверно, использовать можно будет, а метод hashCode() будет вызываться унаследованный от Object.

формально использовать можно, только работать будет мягко говоря специфически:
вот этот код напечатает null, а не "ASD"

Код

public class NoHashCode {   int _value;      public NoHashCode(int value) {     _value = value;   }      public static void main(String[] args) {     HashMap<NoHashCode, String> hm = new HashMap<NoHashCode, String>();     hm.put(new NoHashCode(21), "ASD");     System.out.println(hm.get(new NoHashCode(21)));   } }

Цитата(hatsumeika @ 14.5.2005, 12:42)

формально использовать можно, только работать будет мягко говоря специфически: вот этот код напечатает null, а не "ASD"

Ну тогда и equals нужен.

да, Блох рекомендует equals and hashCode переопределять вместе

Цитата(hatsumeika @ 14.5.2005, 13:21)

да, Блох рекомендует equals and hashCode переопределять вместе

Да нет, без него тоже будет нул давать.

согласен. надо обоих переопределять.

Цитата(hatsumeika @ 14.5.2005, 18:28)

Если hashCode не переопределить, то нельзя будет класс использовать в HashMap, HashSet и т.п. в качестве ключей. Потому что они сначала ищут по hashCode, а только потом по equals.

как это, как это! - как я где-то читал (сорри, не помню где) - родной Object.hashCode пользует для построения хеш-кода в т.ч. и "адрес" объекта (ссылки) - так что довольно уникален ... а?

Цитата(Sleepy_PIP @ 15.5.2005, 03:17)

родной Object.hashCode пользует для построения хеш-кода

Он для разных объектов даст разные значения, независимо от того, equals они или нет. Например new Integer(2) и new Integer(2) будут иметь различный хешкод.

Цитата(Domestic @ 15.5.2005, 17:53)

Цитата(Sleepy_PIP @ 15.5.2005, 03:17) родной Object.hashCode пользует для построения хеш-кода Он для разных объектов даст разные значения, независимо от того, equals они или нет. Например new Integer(2) и new Integer(2) будут иметь различный хешкод.

хм ... опять .. оптяь не понисмаю.
MyClass a,b;
a=new MyClass();
b=new MyClass();

что тут даст hashCode и
a.equal(b)

а теперь
a.Prop1=2;
b.Prop1=3;

что тут даст hashCode и
a.equal(b)

???
и на чем это основано?
по докам - equal - во втором случае дас false т.к. поля класса изменены ... не так?

если в MyClass не переопределены equals() и hashCode(), то исп. соотв. методы у Object, поэтому a.equals(b) всегда будет false.
Если переопределены, то зависит проверяется ли поле Prop1.

Короче создатель класса определяет, что такое для этого класса equals.

Например извращение: класс, объекты которого никогда ничему не равны, даже сами себе:

Код

public boolean equals(Object obj){   return false; }

Это сообщение отредактировал(а) hatsumeika - 16.5.2005, 18:45

Цитата(Domestic @ 15.5.2005, 17:53)

Например new Integer(2) и new Integer(2) будут иметь различный хешкод.

Эти будут иметь один.

"To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method."

Вообще надо поискать информацию по хэш-функциям - для чего они. Там более подробно можно почитать. Идея в том, чтобы ускорить выборку для очень сложных объектов, которые просто сравнивать между собой очень неудобно. А хэш-функция вычисляется обычно очень быстро и для каких-то данных она уникальна для набора каких-то ключевых полей.
Например для тех же String, Integer, Double и прочая.
Если я имею класс, который хочу использовать в качестве ключа в Hashtable, то если я хочу, чтобы при равенстве какого-то набора полей я думал, что это один и тот же ключ, то я должне написать hashCode() который такое и сделает.

Если брать практический пример, то в той же Hashtable ключ используется имеено в разрезе hashCode. Т.е. если я знаю, что в моей Hastable есть ключ Integer(1) и ему соответствует "Старая строка", то операция put(Integer(1), "Новая строка") заменит строку в таблице. А не прибавит новую.

Цитата(AntonSaburov @ 16.5.2005, 10:17)

Эти будут иметь один.

Точно. Я имел в виду - для объектов, у которых хешкод() не переопределен.

Цитата(Domestic @ 16.5.2005, 19:23)

Я имел в виду - для объектов, у которых хешкод() не переопределен.

Убедил

вообще в теории БД - хеш ключ однозначно определяет местоположение записи. посему она (запись) может быть очень быстро получена.
Мне не понятно - зачем иметь повторяющиеся хеш-коды, и тем более такие по которым нельзя восстановить положение объекта для доступа к оному.

Дык определять хешкод должен ты сам если намереваешься использовать объект в качестве ключа. Для стандартных классов типа Стринг, Интегер, итп они определены. Просто делать такой хеш который бы давал 100% гарантию не всегда нужно - достаточно чтобы хеши как можно реже совпадали. Например, для стринга используется полином. Иначе ты конечно выиграешь на времени поиска немного, но проиграешь на вычислении самого хеша.

Цитата(Domestic @ 16.5.2005, 21:10)

Дык определять хешкод должен ты сам если намереваешься использовать объект в качестве ключа. Для стандартных классов типа Стринг, Интегер, итп они определены. Просто делать такой хеш который бы давал 100% гарантию не всегда нужно - достаточно чтобы хеши как можно реже совпадали. Например, для стринга используется полином. Иначе ты конечно выиграешь на времени поиска немного, но проиграешь на вычислении самого хеша.

таки. для моего понимания - у кого хеш-коды определены? ... String. а еще. - где можно получить однозначную информацию? Для оболочек?
таки не понятно - полином, не полином - но в хеш таблице если я кладу String и хочу максимально эффекта от поиска - переопределять самому?. а для кого еще переопределять самому? ... плаваю я тут
т.е. грубо - для любых хеш-таблиц достаточно иметь хеш-код равный индексу? но это-ж не верно! - 2 одинаковых объекта тогда будут имет разный хеш код ... а вообще как посмотрерть - их-же щзанесли в таблицу намерянно! - значить они должны хоть чем-то отличаться ... а?

Это сообщение отредактировал(а) Sleepy_PIP - 16.5.2005, 21:46

Цитата(Sleepy_PIP @ 16.5.2005, 12:42)

но в хеш таблице если я кладу String и хочу максимально эффекта от поиска - переопределять самому?. а для кого еще переопределять самому?

Зачем же? Посмотри доки для Стринга, там формула есть как хеш его вычисляется.
http://java.sun.com/j2se/1.4.2/docs/api/ja...html#hashCode()
По-моему этого достаточно для 99% случаев. Ну и остальные классы - смотришь в доки, есть ли хешкод.

Цитата(Domestic @ 16.5.2005, 21:49)

Цитата(Sleepy_PIP @ 16.5.2005, ) но в хеш таблице если я кладу String и хочу максимально эффекта от поиска - переопределять самому?. а для кого еще переопределять самому? Зачем же? Посмотри доки для Стринга, там формула есть как хеш его вычисляется. http://java.sun.com/j2se/1.4.2/docs/api/ja...html#hashCode() По-моему этого достаточно для 99% случаев. Ну и остальные классы - смотришь в доки, есть ли хешкод.

угу. что-то проясняется. но для собственных классов - всегда писать свое? ... или есть что-то универсальное?
int для хеш-кода- очень мало

Это сообщение отредактировал(а) Sleepy_PIP - 16.5.2005, 21:56

Да, писать свое. Но ничего сложного особо не должно быть. Например, если каждый объект имеет уникальное поле типа Стринг, можно просто возвращать хеш этого стринга.
Хотя часто ли ты пользуешь объекты своего класса как ключи?

Цитата(Domestic @ 16.5.2005, 22:00)

Да, писать свое. Но ничего сложного особо не должно быть. Например, если каждый объект имеет уникальное поле типа Стринг, можно просто возвращать хеш этого стринга. Хотя часто ли ты пользуешь объекты своего класса как ключи?

да вообщем-то нет конечно. в объекте всегда держу именно уникальный ключ - проперти ...

Цитата(Sleepy_PIP @ 16.5.2005, 21:51)

int для хеш-кода- очень мало

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

Цитата(Sleepy_PIP @ 16.5.2005, 21:03)

вообще в теории БД - хеш ключ однозначно определяет местоположение записи. посему она (запись) может быть очень быстро получена. Мне не понятно - зачем иметь повторяющиеся хеш-коды, и тем более такие по которым нельзя восстановить положение объекта для доступа к оному.

Скорее не так... для этого у нас есть уникальные индексы(чтобы уникально определить запись)
А хэш ключ служит для ускорения поиска. И он по определению не уникален!!!
Но он даёт возможность быстро сузить круг поисков.
Например - у нас есть числа от 0 до 99(выступают в роли значений уникального ключа для каких-то данных). Хэш код - это результат деления этих чисел без остатка на 10. Имеем 1,2,3 .....
Когда нам надо найти позицию числа 56 мы берём его хеш код - 5.
и ищем там где хеш код 5: (50,51,52,53,54,55,56,57,58,59)
а вот среди них уже ищем нужное число последовательным перебором и сравнением с "56".
применительно к Хэштейблам и проч. он тоже не может быть уникален по определению: как вы представляете впихнуть множество возможных состояний объекта и множество возможных классов в int?
тогда бы все объекты можно было бы хранить как int.
А потом хитроумно декодировать при использовании.
Можно только использовать этот int как первичный ключ в БД. Но тогда этот механизм должен поддерживать контейнер: хэшмэп и т.д.
на самом деле механизм формирования кода реализован-то в самих объектах, ага?
Суть в том, что когда у нас есть 1000 объектов - мы по хэшкоду находим 12 которые с ним совпадают а их уже "ПЕРЕТРАХИВАЕМ" ( ) сравнивая полностью объекты. Но ведь 12 - это вам 1000
Тут сразу хэшкод зауважаешь

Как говорил многоуважаемый Винни-Пух: "Это Ж-Ж-Ж неспроста!!!"

Вот так звучит первоначальный вопрос:
[quote=Sleepy_PIP, 13.5.2005, 10:48]Вот, решил что хватит по верхушкам бродить. Не стыжусь спросить.
Копнул, и выяснилось что я до конца не понимаю смысла хеш-кода у Object и правила его формиро%
Добавлено @ 21:11
[quote=Sleepy_PIP, 16.5.2005, 21:03]вообще в теории БД - хеш ключ однозначно определяет местоположение записи. посему она (запись) может быть очень быстро получена.
Мне не понятно - зачем иметь повторяющиеся хеш-коды, и тем более %F

пардон за предыдущий пост, глюк однако (у меня)
Вот так звучит первоначальный вопрос:

Цитата

Копнул, и выяснилось что я до конца не понимаю смысла хеш-кода у Object и правила его формирования.

по поводу формирования - есть свойство hash у объектов которое я так понимаю инициализируется с учётом пресловутого адреса в памяти
и метод hashcode() который формирует хэшкод объекта с учётом hash
Например у стринга:

Код

public int hashCode() {     int h = hash;     if (h == 0) {         int off = offset;         char val[] = value;         int len = count;             for (int i = 0; i < len; i++) {                 h = 31*h + val[off++];             }             hash = h;         }         return h;     }

А зачем? А чтоб быстрее искало в хэшмапе и т.п.
у хешмапы есть:

Код

public V get(Object key) {         Object k = maskNull(key);           int hash = hash(k);         // вычисляет хэш используя значение, которое // вернул hashCode()  объекта k - то есть у мапы уже свой хэшкод для объекта // кстати в примере hatsumeika вылетало напрочь из человеческой логики  // вот тут. hashcode() нет - хэшкода нет - нет и диапазона - позже получим null         int i = indexFor(hash, table.length); // а тут как бы берём диапазон объектов // что-то вроде сортировки с использования хэшкода - то есть все объекты с таким  // хешкодом в любом случае в него попадут         Entry<K,V> e = table[i]; // получаем осязаемый диапазон на руки  :)          while (true) { // и понеслась             if (e == null)    // вот тут в примере и вылетело                 return null;%

Это сообщение отредактировал(а) Domestic Cat - 26.5.2005, 09:26

Код

(прямое продолжение предыдущего поста - не влезло чёт  :(  )             if (e.hash == hash && eq(k, e.key)) // а вот ради этого хэшкод и ввели // оно проверяет хэшкоды - если не подходит - то объект не сравнивает // кстати, я в своём примере сбрехал (12 из 1000) - оно не будет все двенадцать //  объектов выбирать - просто только у 12 объектов есть шанс что их полностью  // сверят - поскольку они по коду подходят - остальные отвалятся на первом  // условии.                 return e.value;   //              e = e.next;         }     }

а совпасть хэшкоды могут

так же как значения random()
просто случайно совпасть...
ну да не беда
они своё дело сделают и так

прошу развить тему

Это сообщение отредактировал(а) Domestic Cat - 26.5.2005, 09:26