Хешування композитних об'єктів

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
додано Змінено
Перегляди: 4
джерело
ro nl ja ru fr es pt de zh hi bn ar kk uz be tr
stackoverflow.com/questions/2334218/…
додано Автор assylias, джерело
stackoverflow.com/questions/2334218/…
додано Автор assylias, джерело
Джош Блох обговорює хорошу реалізацію хеш-коду в Ефективному Java .
додано Автор Edward Thomson, джерело
Джош Блох обговорює хорошу реалізацію хеш-коду в Ефективному Java .
додано Автор Edward Thomson, джерело
Зазвичай, просто використовуйте функції lib. Якщо ви не збираєтеся виконати аналіз розподілу ймовірностей, щоб визначити, як краще розподіляти ваші точки даних. Ви знаходите багато зіткнень із набором даних?
додано Автор CodeMonkeyForHire, джерело
Зазвичай, просто використовуйте функції lib. Якщо ви не збираєтеся виконати аналіз розподілу ймовірностей, щоб визначити, як краще розподіляти ваші точки даних. Ви знаходите багато зіткнень із набором даних?
додано Автор CodeMonkeyForHire, джерело

12 Відповіді

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

XOR має тільки те ж властивість, якщо хеш-код B і C має його, інакше він буде використовувати тільки мінімум числа "корисних" бітів в хеш-кодах B і C, що може призвести до погіршення розподілу і більш частого зіткнення . Дуже легко побачити проблему, якщо B і C є цілими числами, які мають тенденцію бути дуже малими, ви будете лише колись використовувати перші кілька бітів (як int.hashcode() є функцією ідентичності).

5
додано
джерело

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

XOR має тільки те ж властивість, якщо хеш-код B і C має його, інакше він буде використовувати тільки мінімум числа "корисних" бітів в хеш-кодах B і C, що може призвести до погіршення розподілу і більш частого зіткнення . Дуже легко побачити проблему, якщо B і C є цілими числами, які мають тенденцію бути дуже малими, ви будете лише колись використовувати перші кілька бітів (як int.hashcode() є функцією ідентичності).

5
додано
джерело

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

XOR має тільки те ж властивість, якщо хеш-код B і C має його, інакше він буде використовувати тільки мінімум числа "корисних" бітів в хеш-кодах B і C, що може призвести до погіршення розподілу і більш частого зіткнення . Дуже легко побачити проблему, якщо B і C є цілими числами, які мають тенденцію бути дуже малими, ви будете лише колись використовувати перші кілька бітів (як int.hashcode() є функцією ідентичності).

5
додано
джерело

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

XOR має тільки те ж властивість, якщо хеш-код B і C має його, інакше він буде використовувати тільки мінімум числа "корисних" бітів в хеш-кодах 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. зловживання терміном «складний тип» (який не має формального визначення в CS і може посилатися, наприклад, на комплексне число) 2. мається на увазі порушення контракту hashCode() + equals() Де моє розуміння відсутнє?
додано Автор Basilevs, джерело
Що таке складний тип? Чому рівний об'єкт виробляє інший хеш-код?
додано Автор Basilevs, джерело
Чи буде "Композитний тип" працювати тут краще?
додано Автор Basilevs, джерело
3. Objects.hash() лише хеші для масивів, якщо у вашому прикладі немає масивів, цей аргумент не застосовується.
додано Автор Basilevs, джерело
Найбільше: " Якщо T є складним типом, третє рішення (Objects.hash ()) також може бути поганим, тому що розглядаються лише посилання (рівні об'єкти можуть повертати різні хеш-коди). "все це говорить: Рівні об'єкти можуть мати різні посилання, які Objects.hash (...) враховує. Таким чином, при передачі рівних об'єктів з різними посиланнями, можуть виникати різні хеш-коди. Ось що я написав, і я думаю, що це правильно.
додано Автор U. Windl, джерело
Для мене, особливо при обговоренні непослідовної мови на зразок Java, це подібно до розщеплення волосся: будь то Атомна або intrinsic_ або примітивний , це одна частина, а комплекс , композитний є іншим. У Eiffel є тільки розширені типи і посилання типи. І є дуже чіткі контракти, що стосуються рівності і хеш-коду, які відсутні в Java (і я вважаю, що це є причиною більшості безладів у Java).
додано Автор U. Windl, джерело
@Basilevs: складний тип, очевидно, є непримітивним типом, тобто. Я не знаю, чому ви проголосували за це, коли ви не розумієте, що я написав.
додано Автор 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. Objects.hash() лише хеші для масивів, якщо у вашому прикладі немає масивів, цей аргумент не застосовується.
додано Автор Basilevs, джерело
1. зловживання терміном «складний тип» (який не має формального визначення в CS і може посилатися, наприклад, на комплексне число) 2. мається на увазі порушення контракту hashCode() + equals() Де моє розуміння відсутнє?
додано Автор Basilevs, джерело
Чи буде "Композитний тип" працювати тут краще?
додано Автор Basilevs, джерело
Більш загально тільки об'єкти, які використовують реалізацію hashCode за замовчуванням, підлягають хешування ідентифікаторів. Такі об'єкти виходять за рамки цього питання.
додано Автор Basilevs, джерело
Найбільше: " Якщо T є складним типом, третє рішення (Objects.hash ()) також може бути поганим, тому що розглядаються лише посилання (рівні об'єкти можуть повертати різні хеш-коди). "все це говорить: Рівні об'єкти можуть мати різні посилання, які Objects.hash (...) враховує. Таким чином, при передачі рівних об'єктів з різними посиланнями, можуть виникати різні хеш-коди. Ось що я написав, і я думаю, що це правильно.
додано Автор U. Windl, джерело
Для мене, особливо при обговоренні непослідовної мови на зразок Java, це подібно до розщеплення волосся: будь то Атомна або intrinsic_ або примітивний , це одна частина, а комплекс , композитний є іншим. У Eiffel є тільки розширені типи і посилання типи. І є дуже чіткі контракти, що стосуються рівності і хеш-коду, які відсутні в Java (і я вважаю, що це є причиною більшості безладів у Java).
додано Автор U. Windl, джерело
@Basilevs: складний тип, очевидно, є непримітивним типом, тобто. Я не знаю, чому ви проголосували за це, коли ви не розумієте, що я написав.
додано Автор 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. зловживання терміном «складний тип» (який не має формального визначення в CS і може посилатися, наприклад, на комплексне число) 2. мається на увазі порушення контракту hashCode() + equals() Де моє розуміння відсутнє?
додано Автор Basilevs, джерело
Чи буде "Композитний тип" працювати тут краще?
додано Автор Basilevs, джерело
3. Objects.hash() лише хеші для масивів, якщо у вашому прикладі немає масивів, цей аргумент не застосовується.
додано Автор Basilevs, джерело
Для мене, особливо при обговоренні непослідовної мови на зразок Java, це подібно до розщеплення волосся: будь то Атомна або intrinsic_ або примітивний , це одна частина, а комплекс , композитний є іншим. У Eiffel є тільки розширені типи і посилання типи. І є дуже чіткі контракти, що стосуються рівності і хеш-коду, які відсутні в Java (і я вважаю, що це є причиною більшості безладів у Java).
додано Автор U. Windl, джерело
Найбільше: " Якщо T є складним типом, третє рішення (Objects.hash ()) також може бути поганим, тому що розглядаються лише посилання (рівні об'єкти можуть повертати різні хеш-коди). "все це говорить: Рівні об'єкти можуть мати різні посилання, які Objects.hash (...) враховує. Таким чином, при передачі рівних об'єктів з різними посиланнями, можуть виникати різні хеш-коди. Ось що я написав, і я думаю, що це правильно.
додано Автор U. Windl, джерело
@Basilevs: складний тип, очевидно, є непримітивним типом, тобто. Я не знаю, чому ви проголосували за це, коли ви не розумієте, що я написав.
додано Автор 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. зловживання терміном «складний тип» (який не має формального визначення в CS і може посилатися, наприклад, на комплексне число) 2. мається на увазі порушення контракту hashCode() + equals() Де моє розуміння відсутнє?
додано Автор Basilevs, джерело
Що таке складний тип? Чому рівний об'єкт виробляє інший хеш-код?
додано Автор Basilevs, джерело
Більш загально тільки об'єкти, які використовують реалізацію hashCode за замовчуванням, підлягають хешування ідентифікаторів. Такі об'єкти виходять за рамки цього питання.
додано Автор Basilevs, джерело
Чи буде "Композитний тип" працювати тут краще?
додано Автор Basilevs, джерело
3. Objects.hash() лише хеші для масивів, якщо у вашому прикладі немає масивів, цей аргумент не застосовується.
додано Автор Basilevs, джерело
Найбільше: " Якщо T є складним типом, третє рішення (Objects.hash ()) також може бути поганим, тому що розглядаються лише посилання (рівні об'єкти можуть повертати різні хеш-коди). "все це говорить: Рівні об'єкти можуть мати різні посилання, які Objects.hash (...) враховує. Таким чином, при передачі рівних об'єктів з різними посиланнями, можуть виникати різні хеш-коди. Ось що я написав, і я думаю, що це правильно.
додано Автор U. Windl, джерело
Для мене, особливо при обговоренні непослідовної мови на зразок Java, це подібно до розщеплення волосся: будь то Атомна або intrinsic_ або примітивний , це одна частина, а комплекс , композитний є іншим. У Eiffel є тільки розширені типи і посилання типи. І є дуже чіткі контракти, що стосуються рівності і хеш-коду, які відсутні в Java (і я вважаю, що це є причиною більшості безладів у Java).
додано Автор U. Windl, джерело
@Basilevs: складний тип, очевидно, є непримітивним типом, тобто. Я не знаю, чому ви проголосували за це, коли ви не розумієте, що я написав.
додано Автор U. Windl, джерело

Це пояснюється тим, що сума надає кращий розподіл, ніж xor .

Наприклад, якщо int a і b мають значення від 0 до 7 ( 000 та 111 binary), то результат xor цих двох аргументів завжди буде між 0 і 7 (оскільки xor змінить лише 3 біти). Тепер, коли ви виконуєте множення та суму , ви матимете набагато кращий розподіл, оскільки значення не будуть знаходитися в діапазоні 0 і 7. \ t

0
додано
джерело
До речі це int hashCode його значення? Було б дуже погано для нерівномірних розподілів для більшості випадків використання, що погано для HashMap та інших алгоритмів на основі хешу.
додано Автор Basilevs, джерело
Залежить від реалізації ^ ^ але відповідь, на жаль, часто так.
додано Автор C4stor, джерело
@Basilevs Так, я мав на увазі ширше, краще, фіксував відповідь, дякую.
додано Автор Adam Siemion, джерело

Це пояснюється тим, що сума надає кращий розподіл, ніж xor .

Наприклад, якщо int a і b мають значення від 0 до 7 ( 000 та 111 binary), то результат xor цих двох аргументів завжди буде між 0 і 7 (оскільки xor змінить лише 3 біти). Тепер, коли ви виконуєте множення та суму , ви матимете набагато кращий розподіл, оскільки значення не будуть знаходитися в діапазоні 0 і 7. \ t

0
додано
джерело
До речі це int hashCode його значення? Було б дуже погано для нерівномірних розподілів для більшості випадків використання, що погано для HashMap та інших алгоритмів на основі хешу.
додано Автор Basilevs, джерело
Залежить від реалізації ^ ^ але відповідь, на жаль, часто так.
додано Автор C4stor, джерело
@Basilevs Так, я мав на увазі ширше, краще, фіксував відповідь, дякую.
додано Автор Adam Siemion, джерело

Це пояснюється тим, що сума надає кращий розподіл, ніж xor .

Наприклад, якщо int a і b мають значення від 0 до 7 ( 000 та 111 binary), то результат xor цих двох аргументів завжди буде між 0 і 7 (оскільки xor змінить лише 3 біти). Тепер, коли ви виконуєте множення та суму , ви матимете набагато кращий розподіл, оскільки значення не будуть знаходитися в діапазоні 0 і 7. \ t

0
додано
джерело
До речі це int hashCode його значення? Було б дуже погано для нерівномірних розподілів для більшості випадків використання, що погано для HashMap та інших алгоритмів на основі хешу.
додано Автор Basilevs, джерело
Залежить від реалізації ^ ^ але відповідь, на жаль, часто так.
додано Автор C4stor, джерело
@Basilevs Так, я мав на увазі ширше, краще, фіксував відповідь, дякую.
додано Автор Adam Siemion, джерело

Це пояснюється тим, що сума надає кращий розподіл, ніж xor .

Наприклад, якщо int a і b мають значення від 0 до 7 ( 000 та 111 binary), то результат xor цих двох аргументів завжди буде між 0 і 7 (оскільки xor змінить лише 3 біти). Тепер, коли ви виконуєте множення та суму , ви матимете набагато кращий розподіл, оскільки значення не будуть знаходитися в діапазоні 0 і 7. \ t

0
додано
джерело
До речі це int hashCode його значення? Було б дуже погано для нерівномірних розподілів для більшості випадків використання, що погано для HashMap та інших алгоритмів на основі хешу.
додано Автор Basilevs, джерело
Залежить від реалізації ^ ^ але відповідь, на жаль, часто так.
додано Автор C4stor, джерело
@Basilevs Так, я мав на увазі ширше, краще, фіксував відповідь, дякую.
додано Автор Adam Siemion, джерело
ІТ КПІ - Java
ІТ КПІ - Java
436 учасників

відкрити Telegram