Хеширование значений с плавающей точкой

Question

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

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

Как:

std::size_t hash_value(float f)
{
  return hash_value(*(reinterpret_cast<int*>(&f)));
}

Я понимаю, что float не обязательно будет иметь такой же размер, как int во всех системах, но такого рода вещи могут быть обработаны с помощью нескольких шаблонных метапрограмм для вывода целочисленного типа того же размера как float. Так в чем же преимущество введения совершенно другой хеш-функции, которая специально работает с типами с плавающей запятой?

Answer 1

Взгляните на https://svn.boost.org/trac/boost/ticket/4038

По сути, это сводится к двум вещам:

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

• второй вопрос - это то, что вы предложили, возможно, sizeof(float) не равно sizeof(int).

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

Answer 2

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

• положительный и отрицательный ноль
• возможно денормализованные числа (я не думаю, что это может произойти с IEEE 754, но C допускает другие представления с плавающей точкой).
• возможно, NAN (их много, по крайней мере, в IEEE 754. Фактически требуется, чтобы шаблоны NAN считались неравными для себя, что, вероятно, означает, что их нельзя использовать в хеш-таблице)

Answer 3

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

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

Это, вероятно, не возникнет при хешировании, если не произойдет иначе в вашемАлгоритм, но вам все равно нужно позаботиться о сигнализации значений NaN.

Кроме того, что будет означать хэширование +/- бесконечности и / или NaN?В частности, NaN может иметь много представлений, все ли они должны приводить к одному и тому же хешу?У бесконечности, кажется, есть только два представления, поэтому кажется, что все будет хорошо.

Answer 4

Я предполагаю, что две машины с несовместимыми форматами с плавающей запятой хэшируют одно и то же значение.