Hashtables / Словари, которые используют поплавки / удваивается

Question

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

Кто-нибудь знает, кто они?

Answer 1

Если вы имеете в виду использование float / double в качестве ключей в вашем хэше, это легко. Например, в .NET он просто использует Dictionary<double,MyValueType>.

Если вы говорите о том, что хеш должен основываться на двойном, а не на целом ....

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

Однако хеш - это просто BitArray, поэтому все будет работать. На самом деле нет особого преимущества в создании чего-то другого, кроме int или long, кроме возможного разрешения большего набора значений хеша (т. Е. Если вы используете 8-байтовый или больший тип для вашего хэша).

Answer 2

Вы имеете в виду как ключи? Это кажется мне хитрым.

Если вы используете их как произвольные ключи, они не лучше целых чисел.

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

Итак, что бы вы сделали с хешами с плавающей точкой?

Answer 3

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

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

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

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

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

Answer 4

История ваших вопросов показывает, что вы используете .Net, поэтому я отвечу в этом контексте.

Если вы хотите, чтобы словарь знал тип, чтобы вы могли указать, что он должен использовать плавающие или двойные для ключей или значений, используйте System.Collections.Generic.Dictionary<T, U> http://msdn.microsoft.com/en-us/library/xfhwa508.aspx

Если вы хотите, чтобы словарь был слепым, чтобы вы могли использовать числа с плавающей запятой и двойные для ключей и значений, используйте System.Collections.HashTable http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx