хеширования составные объекты

Question

EDIT: Этот вопрос не об операторах поразрядными и не может быть решен с 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, этот вопрос больше связан с математикой и вероятностями.

Answer 1

SUM гарантирует, что вы используете все биты хэш-кода для распространения вашего хеширования (в этом, 32 бита int), и не делает предположений о реализации sub hashcode() для этого.

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

Answer 2

Это потому, что sum обеспечивает лучшее распределение, чем xor.

Например, если inta и b имеют значение от 0 до 7 (000 и 111 бинарного), то результат xor этих двух аргументов всегда будет находиться в диапазоне от 0 до 7 (в xor изменится только 3 бита). Теперь, когда вы делаете умножение и sum, у вас будет намного лучшее распределение, так как значения не будут находиться в пределах диапазона 0 и 7.