Идеальное хеширование для OpenCL
У меня есть набор (статический, известный во время компиляции) около 2 миллионов значений по 20 байтов каждое. Мне нужен быстрый O(1) способ проверить, находится ли заданное значение в этом наборе. Кажется, что идеальная хеш-функция с битовым массивом идеально подходит для этого, но я не могу найти простой способ ее создания. Есть некоторые утилиты, такие как gperf, но они слишком сложные. Кроме того, в моем случае нет необходимости иметь коэффициент нагрузки, близкий к 100%, даже 10% достаточно, но с гарантией отсутствия столкновений. Еще одно требование для этой функции - простота, без многих условий: она будет работать на GPU. Что бы вы посоветовали для этого случая?
2 ответа
Прочитав больше информации об идеальном хешировании, я решил не пытаться реализовать это, и вместо этого использовал хэш-таблицу кукушки. Это намного проще и требует не более 2-х обращений к таблице (или любого другого числа>1, чаще всего используется 2..5) вместо 1 для идеального хеширования.
Смотрите мой ответ здесь. Проблема немного другая, но решение может быть адаптировано к вашим потребностям. Оригинал использует коэффициент загрузки 100%, но это можно легко изменить. Он работает путем перетасовки массива на месте во время запуска (это может быть сделано во время компиляции, но это будет подразумевать компиляцию сгенерированного кода).
WRT хеш-функция: если вы ничего не знаете о содержимом 20-байтовых объектов, любая разумная хеш-функция (FNV, Jenkins или моя) будет достаточно хороша.