Функция хеширования для поплавков

Ответ 1

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

ИЗМЕНИТЬ:

Обычно из-за ошибок округления и присущих ограничений арифметики с плавающей запятой, если вы ожидаете, что числа с плавающей запятой a и b должны быть равны друг другу, потому что математика говорит так, вам нужно выбрать некоторые относительно небольшие 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.

Ответ 2

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

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

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

Ответ 3

unsigned hash(float x)
{
    union
    {
        float f;
        unsigned u;
    };
    f = x;
    return u;
}

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

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

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

Ответ 4

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

 std::size_t myHash = std::cout << std::hash<float>{}(myFloat);

Ответ 5

Конечно, вы можете представить 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).

Ответ 6

Если вам интересно, я просто создал хеш-функцию, которая использует плавающие точки и может хешировать поплавки. Он также передает 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

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