Идеальная хеш-функция для набора целых чисел без обновлений

Question

В одном из приложений, над которым я работаю, необходимо иметь такую ​​функцию:

bool IsInList(int iTest)
{
   //Return if iTest appears in a set of numbers.
}

Список номеров известен при загрузке приложения (но не всегда одинаков между двумя экземплярами одного и того же приложения) и не будет изменяться (или добавляться) в течение всей программы. Сами целые числа могут быть большими и иметь большой диапазон, поэтому неэффективно иметь vector<bool>. Производительность - проблема, поскольку функция находится в горячей точке. Я слышал о Идеальное хеширование , но не смог найти ни одного хорошего совета. Любые указатели будут полезны. Благодарю.

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

Answer 1

Я бы предложил использовать Bloom Filters в сочетании с простым std::map.

К сожалению, фильтр Bloom не является частью стандартной библиотеки, поэтому вам придется его реализоватьсам.Однако это оказывается довольно простая структура!

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

Небольшая проблема в том, что ответ ... особенный: Является ли этот элемент частью набора?

• Нет
• Возможно (с определенной вероятностью, зависящей от свойств фильтра Блума)

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

Что действительно интересно для вас, так это то, что для всех случаев он отвечает Нет , у вас есть гарантия, что это не так.t часть набора.

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

Answer 2

целые числа, строки, не имеет значения

http://videolectures.net/mit6046jf05_leiserson_lec08/

После вступления в 49:38 вы узнаете, как это сделать. Демонстрируется хеш-функция Dot Product, поскольку она имеет элегантное доказательство. Большинство хэш-функций напоминают черную магию вуду. Не тратьте время здесь, найдите что-то, что БЫСТРО для вашего типа данных, и которое предлагает некоторую регулируемую SEED для хеширования. Хорошая комбинация там лучше, чем альтернатива выращивания хеш-таблицы.

@ 54: 30 Профессор рисует картину стандартного способа создания идеального хэша. Идеальный минимальный хэш выходит за рамки этой лекции. (удачи!)

Все зависит от того, чем вы занимаетесь.

Имейте в виду, анализ, который он показывает, может быть дополнительно оптимизирован, зная оборудование, на котором вы работаете.

Std :: map обеспечивает очень хорошую производительность в 99,9% сценариев. Если в вашей горячей точке одни и те же сообщения iTest несколько раз, объедините результат карты с временным хеш-кэшем.

Int - это один из типов данных, который можно просто сделать:

bool hash[UINT_MAX]; // stackoverflow ;)

И заполните его. Если вас не волнуют отрицательные числа, тогда это вдвое проще.

Answer 3

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

Answer 4

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

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

Answer 5

Три или, возможно, дерево Ван-Эмде Боаса может быть лучшим выбором для создания компактного набора целых чисел с временем поиска, приводящим постоянную к числу объектов в структуре данных, при условии, что даже std :: bitset будет слишком большой.

Answer 6

Оригинальный вопрос

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

Допустим, значения варьируются от L до H в массиве.Это дает диапазон R = H - L + 1. Обычно он был довольно большим.

Затем я применил оператор модуля от H до L + 1, ища отображение, которое сохраняет их уникальность, но имеетменьший диапазон.

В вашем случае вы используете целые числа.Технически они уже хэшированы, но диапазон велик.

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

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

Answer 7

Нет необходимости или практического стремления отображать N различных случайно распределенных целых чисел в N смежных сегментов, т. Е. Идеальный минимальный хэш, важно определить приемлемое соотношение. Чтобы сделать это во время выполнения, вы можете начать с настройки наихудшего приемлемого соотношения (скажем, от 1 до 20) и отношения «без точки лучше, чем это» (скажем, от 1 до 4), а затем случайным образом изменить ( например, изменение используемых простых чисел) быстрый алгоритм вычисления хеша, чтобы увидеть, насколько легко вы можете встретить все более сложные соотношения. Для худшего - вы не используете тайм-аут или прибегаете к чему-то более медленному, но надежному (списки контейнеров или перемещений для разрешения коллизий). Затем, подождите секунду или десять (настраивается) для каждого X% лучше, пока вы не сможете добиться успеха в этом соотношении или не достигнете отношения без пинты-лучше-лучше ....

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

Answer 8

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

В Википедии есть примера реализации , которая должна быть достаточно простой для перевода на C ++.