Хэшавання складовых аб'ектаў

EDIT: This question is not about bitwise operators and can't be answered with Why are XOR often used in java hashCode() but another bitwise operators are used rarely?

Я бачыў розныя падыходы да хэш разліку аб'екта:

class A {
  public B b;
  public C c;

  @Override
  public boolean equals();
  @Override
  public int hashCode() {
   return c.hashCode() ^ b.hashCode(); //XOR
   return c.hashCode() + prime * b.hashCode();//SUM
   return Objects.hash(b,c);//LIB
  }
}

Здаецца, LIB метад выкарыстоўвае SUM, але чаму гэта лепш, чым XOR?

Нягледзячы на ​​тое, напрыклад, у Java, гэтае пытанне больш пра матэматыцы і верагоднасцяў.

11
дададзена аўтар assylias, крыніца
дададзена аўтар assylias, крыніца
Джош Блох абмяркоўвае добрую рэалізацыю Хэш-кода ў <�я> Effective Java .
дададзена аўтар Edward Thomson, крыніца
Джош Блох абмяркоўвае добрую рэалізацыю Хэш-кода ў <�я> Effective Java .
дададзена аўтар Edward Thomson, крыніца
Як правіла, проста выкарыстоўваць Lib функцыі. Калі вы не збіраецеся працаваць аналіз размеркавання верагоднасцяў, каб вызначыць, як вашы пункту дадзеных лепш размеркаваны. Супастаўляць вы шмат сутыкненняў з ўсталяваць вашы дадзеныя?
дададзена аўтар CodeMonkeyForHire, крыніца
Як правіла, проста выкарыстоўваць Lib функцыі. Калі вы не збіраецеся працаваць аналіз размеркавання верагоднасцяў, каб вызначыць, як вашы пункту дадзеных лепш размеркаваны. Супастаўляць вы шмат сутыкненняў з ўсталяваць вашы дадзеныя?
дададзена аўтар CodeMonkeyForHire, крыніца

12 адказы

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

XOR мае толькі адзін і той жа уласцівасцю, калі хэш-код У і З мае яго, інакш ён будзе выкарыстоўваць толькі мінімум ліку «карысных» біт у B і C хэш-код, які можа прывесці да горшага размеркаванні, а таксама больш частыя сутыкненні , Гэта вельмі лёгка ўбачыць праблему, калі B і C з'яўляюцца цэлымі лікамі, якія, як правіла, вельмі мала, вы будзеце толькі калі-небудзь выкарыстоўваць першыя некалькі бітаў (як int.hashcode() з'яўляецца функцыяй ідэнтычнасці).

5
дададзена

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

XOR мае толькі адзін і той жа уласцівасцю, калі хэш-код У і З мае яго, інакш ён будзе выкарыстоўваць толькі мінімум ліку «карысных» біт у B і C хэш-код, які можа прывесці да горшага размеркаванні, а таксама больш частыя сутыкненні , Гэта вельмі лёгка ўбачыць праблему, калі B і C з'яўляюцца цэлымі лікамі, якія, як правіла, вельмі мала, вы будзеце толькі калі-небудзь выкарыстоўваць першыя некалькі бітаў (як int.hashcode() з'яўляецца функцыяй ідэнтычнасці).

5
дададзена

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

XOR мае толькі адзін і той жа уласцівасцю, калі хэш-код У і З мае яго, інакш ён будзе выкарыстоўваць толькі мінімум ліку «карысных» біт у B і C хэш-код, які можа прывесці да горшага размеркаванні, а таксама больш частыя сутыкненні , Гэта вельмі лёгка ўбачыць праблему, калі B і C з'яўляюцца цэлымі лікамі, якія, як правіла, вельмі мала, вы будзеце толькі калі-небудзь выкарыстоўваць першыя некалькі бітаў (як int.hashcode() з'яўляецца функцыяй ідэнтычнасці).

5
дададзена

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

XOR мае толькі адзін і той жа уласцівасцю, калі хэш-код У і З мае яго, інакш ён будзе выкарыстоўваць толькі мінімум ліку «карысных» біт у B і C хэш-код, які можа прывесці да горшага размеркаванні, а таксама больш частыя сутыкненні , Гэта вельмі лёгка ўбачыць праблему, калі B і C з'яўляюцца цэлымі лікамі, якія, як правіла, вельмі мала, вы будзеце толькі калі-небудзь выкарыстоўваць першыя некалькі бітаў (як int.hashcode() з'яўляецца функцыяй ідэнтычнасці).

5
дададзена

Адказ (як заўсёды): « Гэта залежыць ад .» Гэта залежыць ад вашага класа.

Напрыклад, калі вы лічыце,

class X {
    T a, b;
    X(T _a, _b) { a = _a; b = _b }
}

вы б не выкарыстоўваць сіметрычны аператар, як + , * , або ^ (Уявіце T з'яўляецца Int , і вы хэшавання X (1,2) і X (2,1) . Відавочна, што хэш-код павінен быць іншым. Такім чынам, першы з тры «рашэнне» (XOR хэш-значэнне) будзе дрэнна).

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

1
дададзена
У цэлым толькі аб'екты, якія выкарыстоўваюць рэалізацыю Hashcode па змаўчанні з'яўляюцца прадметам ідэнтычнасці хэшавання. Такія аб'екты выходзяць за рамкі гэтага пытання.
дададзена аўтар Basilevs, крыніца
1. Злоўжыванне тэрміна «складаны тыпу» (які не мае ніякага фармальнага Definiton ў CS і можа ставіцца, напрыклад, да комплекснага ліку) 2. маецца на ўвазе парушэнне хэша-код() +() ураўноўваецца кантракт Дзе маё разуменне не хапае?
дададзена аўтар Basilevs, крыніца
Што такое складаны тып? Чаму б раўнапраўны аб'ект вырабляць розны хэш-код?
дададзена аўтар Basilevs, крыніца
Ці будзе «Composite тыпу» лепш працаваць тут?
дададзена аўтар Basilevs, крыніца
3.
дададзена аўтар Basilevs, крыніца
Больш за ўсё «<�я> Калі T ўяўляе сабой складаны тып, трэцяе рашэнне (Objects.hash ()) было б, магчыма, таксама дрэнна, таму што толькі спасылкі лічацца (роўныя аб'екты могуць вяртаць розныя хэш-коды) »кажа ўсё гэта :. Роўныя аб'екты могуць мець розныя спасылкі, што Objects.hash (...) ўспрыме. Такім чынам, пры праходжанні аднолькавых аб'ектаў з рознымі спасылкамі, можа прывесці розны хэш-кода. Гэта тое, што я напісаў, і я думаю, што гэта правільна.
дададзена аўтар U. Windl, крыніца
Для мяне, асабліва пры абмеркаванні супярэчлівую мовы як Java, гэта як расшчапленне валасоў: Ці з'яўляецца <�я> Atomic або intrinsic_ або <�я> прымітыў , усё гэта адна частка, а <�я> комплекс , <�я> кампазітны з'яўляецца іншы. У Eiffel ёсць толькі <�я> Пашыраныя Тыпы і спасылка тыпы. І ёсць вельмі выразныя кантракты, якія тычацца роўнасцяў і хэш-коды, якія адсутнічаюць у Java (І я лічу, што гэта прычына для большасці бардака ў Java).
дададзена аўтар U. Windl, крыніца
@Basilevs: А <�я> комплекс тыпу, відавочна, не з'яўляецца прымітыўным тыпам, т.е.: Сапраўдным <�я> спасылачныя тып . Я не ведаю, чаму вы downvote гэта калі ты не разумееш, што я напісаў.
дададзена аўтар U. Windl, крыніца

Адказ (як заўсёды): « Гэта залежыць ад .» Гэта залежыць ад вашага класа.

Напрыклад, калі вы лічыце,

class X {
    T a, b;
    X(T _a, _b) { a = _a; b = _b }
}

вы б не выкарыстоўваць сіметрычны аператар, як + , * , або ^ (Уявіце T з'яўляецца Int , і вы хэшавання X (1,2) і X (2,1) . Відавочна, што хэш-код павінен быць іншым. Такім чынам, першы з тры «рашэнне» (XOR хэш-значэнне) будзе дрэнна).

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

1
дададзена
Што такое складаны тып? Чаму б раўнапраўны аб'ект вырабляць розны хэш-код?
дададзена аўтар Basilevs, крыніца
3.
дададзена аўтар Basilevs, крыніца
1. Злоўжыванне тэрміна «складаны тыпу» (які не мае ніякага фармальнага Definiton ў CS і можа ставіцца, напрыклад, да комплекснага ліку) 2. маецца на ўвазе парушэнне хэша-код() +() ураўноўваецца кантракт Дзе маё разуменне не хапае?
дададзена аўтар Basilevs, крыніца
Ці будзе «Composite тыпу» лепш працаваць тут?
дададзена аўтар Basilevs, крыніца
У цэлым толькі аб'екты, якія выкарыстоўваюць рэалізацыю Hashcode па змаўчанні з'яўляюцца прадметам ідэнтычнасці хэшавання. Такія аб'екты выходзяць за рамкі гэтага пытання.
дададзена аўтар Basilevs, крыніца
Больш за ўсё «<�я> Калі T ўяўляе сабой складаны тып, трэцяе рашэнне (Objects.hash ()) было б, магчыма, таксама дрэнна, таму што толькі спасылкі лічацца (роўныя аб'екты могуць вяртаць розныя хэш-коды) »кажа ўсё гэта :. Роўныя аб'екты могуць мець розныя спасылкі, што Objects.hash (...) ўспрыме. Такім чынам, пры праходжанні аднолькавых аб'ектаў з рознымі спасылкамі, можа прывесці розны хэш-кода. Гэта тое, што я напісаў, і я думаю, што гэта правільна.
дададзена аўтар U. Windl, крыніца
Для мяне, асабліва пры абмеркаванні супярэчлівую мовы як Java, гэта як расшчапленне валасоў: Ці з'яўляецца <�я> Atomic або intrinsic_ або <�я> прымітыў , усё гэта адна частка, а <�я> комплекс , <�я> кампазітны з'яўляецца іншы. У Eiffel ёсць толькі <�я> Пашыраныя Тыпы і спасылка тыпы. І ёсць вельмі выразныя кантракты, якія тычацца роўнасцяў і хэш-коды, якія адсутнічаюць у Java (І я лічу, што гэта прычына для большасці бардака ў Java).
дададзена аўтар U. Windl, крыніца
@Basilevs: А <�я> комплекс тыпу, відавочна, не з'яўляецца прымітыўным тыпам, т.е.: Сапраўдным <�я> спасылачныя тып . Я не ведаю, чаму вы downvote гэта калі ты не разумееш, што я напісаў.
дададзена аўтар U. Windl, крыніца

Адказ (як заўсёды): « Гэта залежыць ад .» Гэта залежыць ад вашага класа.

Напрыклад, калі вы лічыце,

class X {
    T a, b;
    X(T _a, _b) { a = _a; b = _b }
}

вы б не выкарыстоўваць сіметрычны аператар, як + , * , або ^ (Уявіце T з'яўляецца Int , і вы хэшавання X (1,2) і X (2,1) . Відавочна, што хэш-код павінен быць іншым. Такім чынам, першы з тры «рашэнне» (XOR хэш-значэнне) будзе дрэнна).

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

1
дададзена
Што такое складаны тып? Чаму б раўнапраўны аб'ект вырабляць розны хэш-код?
дададзена аўтар Basilevs, крыніца
У цэлым толькі аб'екты, якія выкарыстоўваюць рэалізацыю Hashcode па змаўчанні з'яўляюцца прадметам ідэнтычнасці хэшавання. Такія аб'екты выходзяць за рамкі гэтага пытання.
дададзена аўтар Basilevs, крыніца
1. Злоўжыванне тэрміна «складаны тыпу» (які не мае ніякага фармальнага Definiton ў CS і можа ставіцца, напрыклад, да комплекснага ліку) 2. маецца на ўвазе парушэнне хэша-код() +() ураўноўваецца кантракт Дзе маё разуменне не хапае?
дададзена аўтар Basilevs, крыніца
Ці будзе «Composite тыпу» лепш працаваць тут?
дададзена аўтар Basilevs, крыніца
3.
дададзена аўтар Basilevs, крыніца
Для мяне, асабліва пры абмеркаванні супярэчлівую мовы як Java, гэта як расшчапленне валасоў: Ці з'яўляецца <�я> Atomic або intrinsic_ або <�я> прымітыў , усё гэта адна частка, а <�я> комплекс , <�я> кампазітны з'яўляецца іншы. У Eiffel ёсць толькі <�я> Пашыраныя Тыпы і спасылка тыпы. І ёсць вельмі выразныя кантракты, якія тычацца роўнасцяў і хэш-коды, якія адсутнічаюць у Java (І я лічу, што гэта прычына для большасці бардака ў Java).
дададзена аўтар U. Windl, крыніца
Больш за ўсё «<�я> Калі T ўяўляе сабой складаны тып, трэцяе рашэнне (Objects.hash ()) было б, магчыма, таксама дрэнна, таму што толькі спасылкі лічацца (роўныя аб'екты могуць вяртаць розныя хэш-коды) »кажа ўсё гэта :. Роўныя аб'екты могуць мець розныя спасылкі, што Objects.hash (...) ўспрыме. Такім чынам, пры праходжанні аднолькавых аб'ектаў з рознымі спасылкамі, можа прывесці розны хэш-кода. Гэта тое, што я напісаў, і я думаю, што гэта правільна.
дададзена аўтар U. Windl, крыніца
@Basilevs: А <�я> комплекс тыпу, відавочна, не з'яўляецца прымітыўным тыпам, т.е.: Сапраўдным <�я> спасылачныя тып . Я не ведаю, чаму вы downvote гэта калі ты не разумееш, што я напісаў.
дададзена аўтар U. Windl, крыніца

Адказ (як заўсёды): « Гэта залежыць ад .» Гэта залежыць ад вашага класа.

Напрыклад, калі вы лічыце,

class X {
    T a, b;
    X(T _a, _b) { a = _a; b = _b }
}

вы б не выкарыстоўваць сіметрычны аператар, як + , * , або ^ (Уявіце T з'яўляецца Int , і вы хэшавання X (1,2) і X (2,1) . Відавочна, што хэш-код павінен быць іншым. Такім чынам, першы з тры «рашэнне» (XOR хэш-значэнне) будзе дрэнна).

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

1
дададзена
1. Злоўжыванне тэрміна «складаны тыпу» (які не мае ніякага фармальнага Definiton ў CS і можа ставіцца, напрыклад, да комплекснага ліку) 2. маецца на ўвазе парушэнне хэша-код() +() ураўноўваецца кантракт Дзе маё разуменне не хапае?
дададзена аўтар Basilevs, крыніца
Што такое складаны тып? Чаму б раўнапраўны аб'ект вырабляць розны хэш-код?
дададзена аўтар Basilevs, крыніца
У цэлым толькі аб'екты, якія выкарыстоўваюць рэалізацыю Hashcode па змаўчанні з'яўляюцца прадметам ідэнтычнасці хэшавання. Такія аб'екты выходзяць за рамкі гэтага пытання.
дададзена аўтар Basilevs, крыніца
Ці будзе «Composite тыпу» лепш працаваць тут?
дададзена аўтар Basilevs, крыніца
3.
дададзена аўтар Basilevs, крыніца
Больш за ўсё «<�я> Калі T ўяўляе сабой складаны тып, трэцяе рашэнне (Objects.hash ()) было б, магчыма, таксама дрэнна, таму што толькі спасылкі лічацца (роўныя аб'екты могуць вяртаць розныя хэш-коды) »кажа ўсё гэта :. Роўныя аб'екты могуць мець розныя спасылкі, што Objects.hash (...) ўспрыме. Такім чынам, пры праходжанні аднолькавых аб'ектаў з рознымі спасылкамі, можа прывесці розны хэш-кода. Гэта тое, што я напісаў, і я думаю, што гэта правільна.
дададзена аўтар U. Windl, крыніца
Для мяне, асабліва пры абмеркаванні супярэчлівую мовы як Java, гэта як расшчапленне валасоў: Ці з'яўляецца <�я> Atomic або intrinsic_ або <�я> прымітыў , усё гэта адна частка, а <�я> комплекс , <�я> кампазітны з'яўляецца іншы. У Eiffel ёсць толькі <�я> Пашыраныя Тыпы і спасылка тыпы. І ёсць вельмі выразныя кантракты, якія тычацца роўнасцяў і хэш-коды, якія адсутнічаюць у Java (І я лічу, што гэта прычына для большасці бардака ў Java).
дададзена аўтар U. Windl, крыніца
@Basilevs: А <�я> комплекс тыпу, відавочна, не з'яўляецца прымітыўным тыпам, т.е.: Сапраўдным <�я> спасылачныя тып . Я не ведаю, чаму вы downvote гэта калі ты не разумееш, што я напісаў.
дададзена аўтар U. Windl, крыніца

Гэта адбываецца таму, што сума забяспечвае дае лепшае размеркаванне, чым які выключае .

Напрыклад, калі Int а і б маюць значэння ў дыяпазоне ад 0 да 7 ( 000 і 111 двайковы), то вынік які выключае гэтых двух аргументаў заўсёды будзе знаходзіцца ў дыяпазоне ад 0 да 7 (як XOR будзе змяняцца толькі 3 біта). Зараз, калі вы робіце множанне і суму вы будзеце мець значна лепшае размеркаванне, значэння не будуць знаходзіцца ў межах ад 0 да 7 дыяпазону.

0
дададзена
Дарэчы гэта ИНТ хэш-код яго значэнне? Было б вельмі дрэнна для нераўнамерных размеркаванняў для большасці сцэнарыяў выкарыстання, што дрэнна для HashMap і іншых алгарытмаў на аснове хэша.
дададзена аўтар Basilevs, крыніца
У залежнасці ад рэалізацыі ^^ але адказ, на жаль, часта так.
дададзена аўтар C4stor, крыніца
@Basilevs Так, я меў на ўвазе шырэй, лепш, фіксаваны адказ, дзякуй.
дададзена аўтар Adam Siemion, крыніца

Гэта адбываецца таму, што сума забяспечвае дае лепшае размеркаванне, чым які выключае .

Напрыклад, калі Int а і б маюць значэння ў дыяпазоне ад 0 да 7 ( 000 і 111 двайковы), то вынік які выключае гэтых двух аргументаў заўсёды будзе знаходзіцца ў дыяпазоне ад 0 да 7 (як XOR будзе змяняцца толькі 3 біта). Зараз, калі вы робіце множанне і суму вы будзеце мець значна лепшае размеркаванне, значэння не будуць знаходзіцца ў межах ад 0 да 7 дыяпазону.

0
дададзена
Дарэчы гэта ИНТ хэш-код яго значэнне? Было б вельмі дрэнна для нераўнамерных размеркаванняў для большасці сцэнарыяў выкарыстання, што дрэнна для HashMap і іншых алгарытмаў на аснове хэша.
дададзена аўтар Basilevs, крыніца
У залежнасці ад рэалізацыі ^^ але адказ, на жаль, часта так.
дададзена аўтар C4stor, крыніца
@Basilevs Так, я меў на ўвазе шырэй, лепш, фіксаваны адказ, дзякуй.
дададзена аўтар Adam Siemion, крыніца

Гэта адбываецца таму, што сума забяспечвае дае лепшае размеркаванне, чым які выключае .

Напрыклад, калі Int а і б маюць значэння ў дыяпазоне ад 0 да 7 ( 000 і 111 двайковы), то вынік які выключае гэтых двух аргументаў заўсёды будзе знаходзіцца ў дыяпазоне ад 0 да 7 (як XOR будзе змяняцца толькі 3 біта). Зараз, калі вы робіце множанне і суму вы будзеце мець значна лепшае размеркаванне, значэння не будуць знаходзіцца ў межах ад 0 да 7 дыяпазону.

0
дададзена
Дарэчы гэта ИНТ хэш-код яго значэнне? Было б вельмі дрэнна для нераўнамерных размеркаванняў для большасці сцэнарыяў выкарыстання, што дрэнна для HashMap і іншых алгарытмаў на аснове хэша.
дададзена аўтар Basilevs, крыніца
У залежнасці ад рэалізацыі ^^ але адказ, на жаль, часта так.
дададзена аўтар C4stor, крыніца
@Basilevs Так, я меў на ўвазе шырэй, лепш, фіксаваны адказ, дзякуй.
дададзена аўтар Adam Siemion, крыніца

Гэта адбываецца таму, што сума забяспечвае дае лепшае размеркаванне, чым які выключае .

Напрыклад, калі Int а і б маюць значэння ў дыяпазоне ад 0 да 7 ( 000 і 111 двайковы), то вынік які выключае гэтых двух аргументаў заўсёды будзе знаходзіцца ў дыяпазоне ад 0 да 7 (як XOR будзе змяняцца толькі 3 біта). Зараз, калі вы робіце множанне і суму вы будзеце мець значна лепшае размеркаванне, значэння не будуць знаходзіцца ў межах ад 0 да 7 дыяпазону.

0
дададзена
Дарэчы гэта ИНТ хэш-код яго значэнне? Было б вельмі дрэнна для нераўнамерных размеркаванняў для большасці сцэнарыяў выкарыстання, што дрэнна для HashMap і іншых алгарытмаў на аснове хэша.
дададзена аўтар Basilevs, крыніца
У залежнасці ад рэалізацыі ^^ але адказ, на жаль, часта так.
дададзена аўтар C4stor, крыніца
@Basilevs Так, я меў на ўвазе шырэй, лепш, фіксаваны адказ, дзякуй.
дададзена аўтар Adam Siemion, крыніца