Как хэшировать вещественные числа?

Question

[Artyom_Kopan]

Простое приведение к int или memcpy(&doubleValue, &intValue, sizeof(double)) не подходит, потому что получается адское количество коллизий, особенно когда на вход поступают близкие значения double.
Какая хэш-функция окажется более эффективной?

Comments

[uvelichitel]

Зависит от распределения входящих данных. Если эти вещественные числа распределены равномерно по всему полю double, то хеширование не имеет кажется никакого смысла. А вот если, тривиальный пример, входные данные все >14 и <15 то можно просто брать дробную часть...

Answer 1

[Wataru]

Проблема вашего кода в том, что вы берете лишь первые 4 байта из 8 в double.

Копируете в uint64_t. Если надо меньше бит, то можно домножить на большое простое число и потом взять xor младших и старших бит.

Comments

[Artyom_Kopan]

Согласно условию задачи, хэш должен быть uint32_t. А как это - xor младших и старших бит? То есть нужно в uint64_t выделить 32 младших бита, 32 старших и сделать их xor?

[Wataru]

Artyom_Kopan, Почитайте про битовые операции.

[Artyom_Kopan]

Получилось что-то вроде этого:

uint32_t hashDouble(double x)
{
    uint_fast64_t temp = 0;
    x *= HASH_POLYNOMIAL_PARAMETER;
    memcpy(&x, &temp, sizeof(double));
    int32_t older = temp >> 32;
    int32_t younger = (temp << 32) >> 32;
    return (older ^ younger) % MOD;
}

[Wataru]

Artyom_Kopan, Почти. Домножать надо ужe uint. Тогда домножение на большое простое (или хотя бы нечетное) число в 64 бита и арифметика uint64_t по модулю 2^64 вносит элемент случайности.

И еще у вас у memcpy перепутан порядок аргументов.

Вместо сдвигов туда и обратно для младших битов можно использовать операцию побитового и с 0xFFFFFFFF или просто привести к int32_t - что отбросит лишние биты.
Или, можно вообще сразу написать return static_cast<uint32_t>((temp >> 32)^temp);. В младших битах как раз что вам надо получится и старшие выкинутся.

И старший/младший не переводится так на прямо на английский. Для этого там есть термины high/low.

Answer 2

[Армянское Радио]

Вещественные числа сами себе прекрасный 64-битный хэш.