Хэш-функция для поплавков - PullRequest
Новая
       43

Хэш-функция для поплавков

16 голосов
/ 21 ноября 2010

В настоящее время я реализую хеш-таблицу в C ++ и пытаюсь создать хеш-функцию для чисел с плавающей запятой ...

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

Есть ли хороший способ хеширования?

Вам не нужно давать мне функцию напрямую, но я бы хотел увидеть / понять различные концепции ...

Примечания:

  1. Мне не нужно, чтобы он был действительно быстрым, просто равномерно распределенным, если это возможно.

  2. Я читал, что числа с плавающей запятой не должны хэшироваться из-за скорости вычислений, может ли кто-нибудь подтвердить / объяснить это и дать мне другие причины, почему не следует хэшировать числа с плавающей запятой? Я не очень понимаю, почему (помимо скорости)

Ответы [ 6 ]

17 голосов
/ 21 ноября 2010

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

РЕДАКТИРОВАТЬ :

Как правило, из-за ошибок округления и врожденных ограничений арифметики с плавающей запятой, если вы ожидаете, что числа с плавающей запятой a и b должны быть равны друг другу, потому что математика говорит, что вам нужно выбрать относительно small delta > 0, и затем вы объявляете a и b равными, если abs(a-b) < delta, где abs - функция абсолютного значения. Подробнее см. в этой статье .

Вот небольшой пример, демонстрирующий проблему: 

float x = 1.0f;
x = x / 41;
x = x * 41;
if (x != 1.0f)
{
    std::cout << "ooops...\n";
}

В зависимости от вашей платформы, компилятора и уровней оптимизации, это может вывести на ваш экран ooops..., что означает, что математическое уравнение x / y * y = x не обязательно сохраняется на вашем компьютере.

В некоторых случаях арифметика с плавающей запятой дает точные результаты, например, разумные целые числа и рациональные числа со знаменателями степени 2.

11 голосов
/ 21 ноября 2010

Если ваша хеш-функция выполняет следующие действия, вы получите некоторую степень размытости при поиске хеша 

unsigned int Hash( float f )
{
    unsigned int ui;
    memcpy( &ui, &f, sizeof( float ) );
    return ui & 0xfffff000;
}

Таким образом, вы замаскируете 12 младших битов, учитывая степень неопределенности ... Однако это действительно зависит от вашего приложения.

6 голосов
/ 30 сентября 2016

Вы можете использовать хеш std, это неплохо: 

 std::size_t myHash = std::cout << std::hash<float>{}(myFloat);
5 голосов
/ 21 ноября 2010 
unsigned hash(float x)
{
    union
    {
        float f;
        unsigned u;
    };
    f = x;
    return u;
}

Технически неопределенное поведение, но большинство компиляторов поддерживают это.Альтернативное решение: 

unsigned hash(float x)
{
    return (unsigned&)x;
}

Оба решения зависят от порядкового номера вашей машины, поэтому, например, для x86 и SPARC они будут давать разные результаты.Если вас это не беспокоит, просто воспользуйтесь одним из этих решений.

3 голосов
/ 17 февраля 2015

Вы, конечно, можете представить float как тип int того же размера, чтобы хэшировать его, однако этот наивный подход имеет некоторые подводные камни, с которыми вам нужно быть осторожными ...

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

Очевидный случай: -0.0 не будет соответствовать 0.0, например. *

Кроме того, простое преобразование в int того же размера не даст очень равномерного распределения, что часто важно (например, реализация хеша / набора, использующего сегменты).

Предлагаемые шаги для реализации:

  • отфильтровывает неконечные случаи (nan, inf) и (0.0, -0.0 , нужно ли вам сделать это явно или нет, зависит от используемого метода ).
  • преобразовать в int того же размера
    (то есть - использовать объединение, например, для представления float как int, а не просто приведение к int) .
  • перераспределить биты, (намеренно расплывчато здесь!) , это в основном соотношение скорости и качества. Но если у вас много значений в небольшом диапазоне, вы, вероятно, не хотите, чтобы они находились и в аналогичном диапазоне.

*: Вы можете не проверять (nan и -nan) тоже. Как именно их обрабатывать, зависит от вашего варианта использования (вы можете игнорировать знак для всех nan, как делает CPython).

Python _Py_HashDouble - хороший пример того, как вы можете хэшировать float в рабочем коде (игнорируйте проверку -1 в конце, так как это специальное значение для Python) .

1 голос
/ 12 июня 2017

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

Я не уверен, что tifuhash станет полезным для всех приложений, но интересно, что простая функция с плавающей запятой проходит как PractRand, так и SMHasher.

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

function q( state, val, numerator, denominator ) {
  // Continued Fraction mixed with Egyptian fraction "Continued Egyptian Fraction"
  // with denominator = val + pos / state[1]
  state[0] += numerator / denominator;
  state[0] = 1.0 / state[0];

  // Standard Continued Fraction with a_i = val, b_i = (a_i-1) + i + 1
  state[1] += val;
  state[1] = numerator / state[1];
}

В любом случае, вы можете получить его по npm Или вы можете проверить GitHub

Использование просто: 

const tifu = require('tifuhash');

const message = 'The medium is the message.';
const number = 333333333;
const float = Math.PI;

console.log( tifu.hash( message ), 
  tifu.hash( number ),
  tifu.hash( float ),
tifu.hash( ) );

Здесь есть демо-версия некоторых хэшей на runkit https://runkit.com/593a239c56ebfd0012d15fc9/593e4d7014d66100120ecdb9

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

...