Как я должен сопоставить long с int в hashCode ()?

Question

У меня есть ряд объектов с полем long, значение которого однозначно идентифицирует конкретный объект во всей моей системе, во многом как GUID. Я переопределил Object.equals(), чтобы использовать этот идентификатор для сравнения, потому что я хочу, чтобы он работал с копиями объекта. Теперь я тоже хочу переопределить Object.hashCode(), что в основном означает отображение моего long на некоторое int возвращаемое значение.

Если я правильно понял назначение hashCode, оно в основном используется в хеш-таблицах, поэтому было бы желательно равномерное распределение. Это будет означать, что достаточно просто вернуть id % 2^32. Это все, или я должен знать что-то еще?

Answer 1

Начиная с Java 8 вы можете использовать

Long.hashCode(guid);

Для более старых версий Java вы можете использовать следующее:

Long.valueOf(guid).hashCode();

Обратите внимание, что это решение создает новый объект для стека, в то время как первый не создает (хотя вполне вероятно, что Java оптимизирует создание объекта вне ...)

Глядя на документы, оба способа просто используют следующий алгоритм:

(int)(this.longValue()^(this.longValue()>>>32))

Это достойные решения, поскольку они используют библиотеку Java - всегда лучше использовать что-то, что уже было протестировано.

Answer 2

Немного мелочи, если вы не используете Гуава , но Гуава может сделать это за вас приятно:

public int hashCode() {
  return Longs.hashCode(id);
}

Это дает вам эквивалент Long.valueOf(id).hashCode():

return (int) (value ^ (value >>> 32));

Кроме того, если бы у вас были другие значения или объекты, которые были частью хеш-кода, вы могли бы просто написать

return Objects.hashCode(longValue, somethingElse, ...);

long будет автоматически помещен в Long, так что вы получите правильный хеш-код для него как часть общего хеш-кода.

Answer 3

Вы правильно поняли цель hashCode.Да, желательно равномерное распределение (хотя это и не фактическое требование).

Я бы предложил ((id >> 32) ^ id).

Вышеприведенное выражение:

• Использует все битыпервоначальной стоимости, не исключает никакой информации заранее.Например, в зависимости от того, как вы генерируете идентификаторы, старшие биты могут меняться чаще (или наоборот).
• Не вносит никакого смещения в сторону значений с большим количеством единиц (нулей), так как это будетслучай, если две половины были объединены операцией ИЛИ (И).

Answer 4

Java 8 добавляет Long.hashCode (long) в JDK.

Следующий код может повысить производительность.Этот код сокращает вычисление до 32-разрядного int вместо вычисления с 64-разрядным long.Это может иметь значение для 32-разрядных и небольших архитектур.32-разрядные процессы на машинах x86 могут оптимизировать это в одну инструкцию, которая просто регистрируется в XOR 2.

return (int)(value ^ (value >>> 32));

Как отмечалось в других ответах, это не иметь хороший лавинный эффект и, следовательно, может привести к столкновениям.Можно использовать криптографические хеш-функции для обеспечения высокого лавинного эффекта.Однако есть и другие алгоритмы, такие как Murmur Hash (дополнительная информация ), которые имеют очень хороший лавинный эффект, но не занимают так много процессорного времени.

Answer 5

(l >> 32) ^ l - хороший хеш-код в большинстве случаев;особенно когда long имеет равномерное распределение.

Поскольку это был принятый ответ, я публикую его, чтобы уточнить некоторые из моих комментариев о том, когда это НЕ хороший хеш-код для long.

Пример, который я привел, был классом Point следующим образом:

public class Point {
    private final long coords; //x in high-bits, y in low
    public int getX() {
        return (int)(coords >> 32);
    }
    public int getY() {
        return (int)coords;
    }
    public int hashCode() {
        return (int)((coords >> 32) ^ (coords));
    }
}

Может показаться надуманным, но иногда у вас есть несколько "полей", упакованных в long.

Итак, поле coordsпредставляет 32 бита х и 32 бита у.Так почему же это проблема?Ну, это не так, если каждый из x и y равномерно распределен по своим соответствующим 32 битам.Но на практике это маловероятно.Что более вероятно, так это то, что X и Y ограничены некоторым числом.Скажем, 1024, так как это 2 ^ 10.Это означает, что самое большее 10 младших битов каждого X и Y установлены:

00000000 00000000 000000XX XXXXXXXX 00000000 00000000 000000YY YYYYYYYY

Есть 2 ^ 20 (1024 * 1024) возможных комбинаций.Но что делает операция hashCode?

  00000000 00000000 000000XX XXXXXXXX 
^ 00000000 00000000 000000YY YYYYYYYY
-------------------------------------
= 00000000 00000000 000000?? ????????

Существует не более 2 ^ 10 (1024) возможных значений hashCode, поскольку только младшие 10 бит могут быть чем-либо, кроме нуля.Отношение хеш-значений к реальным значениям составляет 1024:(1024*1024) или 1:1024.Таким образом, сразу же существует вероятность 1/1024, что два числа имеют одинаковый хэш.

Теперь давайте вычислим вероятность столкновения, применяя математические вычисления из задачи дня рождения .Пусть p (n) - вероятность того, что при n значениях произойдет хотя бы одно столкновение.Мы знаем, что p (1025+) = 1, поскольку существует только 1024 значения.

p(n) = 1 - (n! * (1024 choose n))/1024^n

Это работает следующим образом:

n: p(n)
1: 0.00000
2: 0.00098
3: 0.00293
4: 0.00585
5: 0.00973
6: 0.01457
...
38: 0.50096
...
79: 0.95444
...
148: 0.99999

Всего 38 элементов, вероятно, естьстолкновениеС 148 предметами вероятность столкновения составляет не менее 99,999%.Каждый предмет из 148 предметов с вероятностью 7% может столкнуться с другим предметом.При правильной функции хеширования, принимая знания о домене, эти числа могут легко опуститься до 0.

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

Answer 6

int result = (int)((longVal >> 32) ^ longVal);

будет распределяться лучше, потому что по модулю не будет возвращено другое значение, если изменились только старшие биты вашего длинного значения.