Выкарыстоўваючы HashTable без пераазначэнне хэш-код ()

Сёння я задаў гэтае пытанне ў інтэрв'ю:

<�Р> Што адбудзецца, калі мы не перавызначыць хэш-код метад для нашага   клас, а затым дадаць яго ў HashTable , а затым паспрабаваць атрымаць аб'екты?

Што можа пайсці не так?

6
@ MartinSchröder У мяне ёсць праца ўжо)
дададзена аўтар Jeremy Brown, крыніца
Прачытайце гэтую кнігу калі вы хочаце атрымаць працу праграмавання Java.
дададзена аўтар Flávio Filho, крыніца

8 адказы

Ідэя з HashTable пры спробе здабывання аб'екта з'яўляецца тое, што структура дадзеных вылічае хэш-код аб'екта, выкарыстоўваючы GetHashCode() метад і затым праходзіць праз спіс з дапамогай клавішы Роўна) <�код /> (метад.

З змаўчанні GetHashCode() рэалізацыя, дзве цалкам аналагічныя аб'екты могуць у канчатковым выніку атрымліваюць розныя хэш-коды, што азначае, што калі вы не выкарыстоўваеце адзін і той жа экземпляр, вы ніколі не знайсці ваш аб'ект у HashTable .

Увогуле, вы хочаце, каб пераканацца, што з двух рэчаў пры рэалізацыі хэш-коды:

  • If A.Equals(B) then A.GetHashCode()==B.GetHashCode()
  • Try to get a distribution of hash codes properly spread to get the maximum efficiency from the hash table (if too few hash codes are possible, you'll end up searching a list).
18
дададзена
Метад з'яўляецца хэш-код (), ня GetHashCode ().
дададзена аўтар Paul, крыніца
@SpencerK: так, як DevSolo сказаў, што я спрабаваў растлумачыць паняцце не патрапіць у мове канкрэтных дэталяў, якія, я спадзяюся, што інтэрв'юер шукае.
дададзена аўтар Jon Mitchell, крыніца
Я лічу, што @SRKX выкарыстаў C# у яго прыкладзе, дзе хэш-код з'яўляецца эквівалентам Java. Адказ сапраўдны на абодвух мовах.
дададзена аўтар Mauro ALLEGRANZA, крыніца
<�Р> Што адбудзецца, калі мы не перавызначыць метад Hashcode для нашага класа, а затым дадаць яго ў HashTable, а затым паспрабаваць атрымаць аб'екты?

Гэта залежыць ад таго, што «даданне да HashTable» азначае. Java- Hashtable не мае <�код > дадаць метад /. Інтэрв'юер, верагодна, меў на ўвазе паставіць метад, які прымае ў ключ і значэнне . Значэнне можа быць што-небудзь (можа быць нават нулявым у HashMap, што цяперашняя версія Hashtable). Нічога асаблівага не адбываецца, незалежна ад таго, ці сапраўды вы перавызначыць хэш-код аб'екта-значэння, або любы іншы метад.

Інтэрв'юер, верагодна, меў на ўвазе, што хэш-код ключавога аб'екта не будзе адменены. Толькі ў гэтым выпадку праблема ідэнтычнасці аб'екта, як паказана ў іншых адказах, ўступаюць у гульню. Нават тады, вы не абавязкова павінны перавызначыць хэш-код гэтага ключа. Напрыклад, калі вы выкарыстоўваеце Радок s як ключы, яны ўжо маюць адпаведную рэалізацыю Hashcode ў іх. Акрамя таго, яны не могуць быць падкласы. Акрамя таго, калі вы зрабіць перавызначыць хэш-код, але не пераазначэнне роўна, вы можаце атрымаць некаторыя дзіўныя мадэлі паводзін ...

Калі пытанне сапраўды быў менавіта тое, што вы напісалі, я б дражніў інтэрв'юер з гэтымі пытаннямі. Добры праграміст не <�ет> Выкажам здагадку, , што інтэрв'юер, верагодна, меў на ўвазе тую ці іншую. Ён просіць наўзамен.

6
дададзена
Hashtable не падтрымлівае нуль.
дададзена аўтар Paul, крыніца
@Spencer K: Дзякуй, выпраўлена.
дададзена аўтар Zoom_v, крыніца

Адказ няма «нічога дрэннага, калі вы не перавызначаны роўны() ».

Агульная кропка з'яўляецца тое, што, калі параўнаць два аб'екта роўныя, г.зн. калі

 a.equals(b)

то яны павінны мець такі ж хэш-код, г.зн.

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

Акрамя таго, калі два аб'екта маюць розныя хэш-коды, яны не павінны параўноўваць роўныя.

Гэта асабліва актуальна, калі вы змяшчаеце аб'екты ў хэш-табліцы. Гэта таму, што хэш-табліца ўяўляе сабой масіў з спісаў (так званыя каўшы звычайна). Хэш вядро індэксуецца з выкарыстаннем хэш-код, як правіла, выкарыстоўваецца Hashcode% ARRAYSIZE .

Таму, калі вы змесціце аб'ект у хэш-табліцы, вы бераце хэш-код ключа і выкарыстоўваць яго, каб вызначыць вядро. Затым пакласці пару ключ-значэнне ў вядры. Калі вы хочаце, каб атрымаць аб'ект з хэш-табліцы, вы бераце хэш-код ключа, каб знайсці вядро і праверыць ключ усіх пар ключ-значэнне ў вядры з .equals() каб вызначыць, які аб'ект з'яўляецца той, які вы хочаце.

Так што калі ў вас ёсць два ключавых аб'ектаў, якія лічацца роўнымі, але маюць розныя Хэш-коды і вы карыстаецеся адзін у якасці ключа ў хэш-табліцу, вы не зможаце знайсці яго з дапамогай іншага ключа аб'екта, таму што вы будзеце шукаць у няправільнае вядро.

Рэалізацыя роўны() у Object толькі вяртае ісціну, калі два аб'екта фактычна той жа аб'ект і хэш-код() вяртае спасылку на аб'ект. Тым не менш, калі вы перавызначыць роўны() (напрыклад, радок робіць так, што розныя радкі, якія ўтрымліваюць тую ж паслядоўнасць сімвалаў параўнання роўныя), то вы павінны перавызначыць хэш-код()

6
дададзена
@scarfridge: Я збольшага згодны, што толькі з дапамогай ідэнтычнасці аб'екта для ідэнтыфікацыі ключоў даволі шмат бескарыснай. Я не меў на ўвазе нічога дрэннага ў плане (напрыклад), якія маюць значэнне хэш-код() змены ў той час як аб'ект выкарыстоўваецца ў якасці ключа ў карце.
дададзена аўтар Christian Læirbag, крыніца
Добры адказ, але я думаю, што першы сказ уводзіць у зман. Калі вы выкарыстоўваеце HashMap або Hashtable, вы павінны перавызначыць хэш-код() і роўны() . Першы сказ толькі справядліва, калі вы сапраўды маюць намер выкарыстоўваць ідэнтыфікатар аб'екта, як роўнасць, напрыклад, Вы сапраўды хочаце, каб параўнаць аб'екты з == замест роўны() .
дададзена аўтар scarfridge, крыніца

вы не знойдзеце аб'ект, калі вы атрымліваеце з іншым аб'ектам, які роўна </кодам> на аб'ект вы паклалі

або прывесці прыклад:

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

the reason for this is that HashTable (and HashMap) will use the hashcode to limit the space it has to search through to find the object and that relies on the assumption that if obj1.equals(obj2) then obj1.hashcode == obj2.hashcode()

4
дададзена

Я хацеў бы толькі дадаць, што ўсе гэтыя паняцці павінны з ідэнтычнасць і Параўнанне .

Існуе кантракт з хэш-код:

1.) Кожны раз, калі ён выклікаецца на той жа аб'екце больш, чым адзін раз на працягу выканання прыкладання Java, метад хэша-код павінен паслядоўна вяртаць той жа цэлы лік, пры ўмове, ніякай інфармацыі выкарыстоўваецца ў не зраўняецца параўнання на аб'екце змяняюцца. Гэты лік не павінна заставацца паслядоўным ад аднаго выканання прыкладання іншаму выканання аднаго і таго жа прыкладання.

2.) Калі два аб'екта роўныя па метадзе Equals (Object), то выклік метаду HashCode на кожным з двух аб'ектаў павінен вырабляць адзін і той жа цэлалікавых вынік.

3.) Тут трэба, што калі два аб'екта няроўныя паводле метаду, роўна (java.lang.Object), то выклік метаду HashCode на кожным з двух аб'ектаў павінен вырабляць розныя вынікі цэлалікавых. Тым не менш, праграміст павінен ведаць, што вырабляць розныя вынікі для цэлалікавых няроўных аб'ектаў можа палепшыць прадукцыйнасць хэш-табліц.

Вынікам з'яўляецца тое, што калі хэш-коды аднолькавыя запісу ў табліцы накласціся адзін на аднаго, і гэта можа быць дзіўным для некаторых ...

Спадзяюся, што гэта дапамагае.

3
дададзена

Адказ: аналагічныя аб'екты (усе палі, якія маюць аднолькавыя значэння) не будзе ствараць той жа хэш-код, так што вам трэба будзе дакладна такі ж (ідэнтычны) аб'ект, які быў выкарыстаны для змясціць , каб атрымаць з хэш-табліцы, якія не ўяўляецца магчымым у большасці выпадкаў.

2
дададзена

Выкажам здагадку, што ваш клас распаўсюджваецца толькі Object , то хэш-код() рэалізацыя вашага класа будзе залежаць ад аб'ект ідэнтычнасці . гэта значыць што хэш-код з двух розных асобнікаў будзе (амаль напэўна) будзе адрознівацца, нават калі яны маюць дакладна такое ж значэнне.

Гэта азначае, што вы, хутчэй за ўсё, не знайсці аб'ект зноў у карце (вы можа знайсці яго выпадкова, аднак).

2
дададзена

Калі метад хэш-код ня перавызначаны, то адказ на гэтае пытанне сапраўды залежыць ад таго, калі той жа аб'ект ключ, які быў выкарыстаны для «паставіць» будзе выкарыстоўвацца для «атрымаць» а таксама:

а) Калі выкарыстоўваецца той жа аб'ект ключ - «атрымаць» будзе знайсці значэнне. Таму што гэта будзе знайсці вядро, выкарыстоўваючы адзін і той жа «ключ» і, такім чынам, будзе знайсці значэнне аб'екта.

б) Калі выкарыстоўваецца якой-небудзь іншай «equivelent» ключавой аб'ект - Дык як, магчыма, хэш-код будзе адрознівацца з-за рэалізацыі па змаўчанні метаду Hashcode ў Object і, такім чынам, ён можа патрапіць у іншае вядро і, магчыма, ня быць у стане атрымаць значэнне аб'екта.

1
дададзена