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

Для ассоциативного массива я использую хэширование с 72 до 26 бит, и мне нужна чрезвычайно низкая частота конфликтов. Скорость также является важным фактором. Я начал с https://en.wikipedia.org/wiki/Hash_function#Hashing_By_Nonlinear_Table_Lookup Это достаточно быстро, но при тестировании я получил коллизии в пределах первых 100 входов!

    for(=0; k<9; k++)
            hash ^= randombits[byteptr[k]];
    hash &= (1<<HASHBITS)-1

Проблема в том, что все мои входные данные являются производными друг от друга - есть начальные 72 бита, а последующие входные данные получены из предыдущего путем обмена 2-мя битовыми парами (выровненными по четным границам битов) друг с другом. Приведенный выше простой цикл XOR с треском провалился. Очевидным подходом было бы использование байтового индекса «k» для того, чтобы каким-либо образом изменять хеш на каждой итерации. В дополнение к предложениям по коду я ищу теоретическую основу - я хочу иметь хорошее представление о том, какой будет частота столкновений. Читая статьи, я ничего не нахожу относительно эффективности хеширования при перестановках. Я уверен, что с крипто-хэшами все будет хорошо, но они выглядят медленными. Предложения и указатели для моих исследований приветствуются, и спасибо. FWIW Я использую ARC4 для генерации "случайных битов", массива 256 u_int32_t.

ИЗМЕНИТЬ для ясности: битовые транспозиции на входе выглядят следующим образом: для четных N и X меньше 72 биты (N: N + 1) меняются местами на биты (X: X + 1) для случайных X и N. Все такие свопы фактически меняют состояние - идентичные биты никогда не меняются местами.


algorithm hash associative-array hashtable hash-collision
person Conrad    schedule 18.04.2015    source источник
comment
Сколько возможных перестановок разрешено? Не могли бы вы просто сохранить индекс перестановки вместо хеширования результата?   -  person Nick Johnson    schedule 18.04.2015
comment
Ник, поток перестановок бесконечен, и я не знаю начального условия. Конечно, если бы у меня было хранилище порядка 2 * 72 подмигнуть ... Я надеюсь, эксперименты покажут мне, что я случайно выбрал худший вид функции для перестановок (прямой XOR). Я буду очень рад, если я уменьшу количество столкновений примерно до 1/8000.   -  person Conrad    schedule 18.04.2015
comment
(1) Меняются только четные биты: если нечетные биты не переставляются, они одинаковы для всех перестановок. Таким образом, ваш ввод содержит не 72, а всего 36 значащих битов. (2) ваша хеш-функция симметрична: ABCDEFGHI хеширует то же значение, что и BACDEFGHI. Это коэффициент 9! (: = 362880) около 18 бит, которые вы теряете из-за симметрии. (3) Также: замена двух одинаковых битов не меняет значения. Таким образом, ваша хеш-функция может иметь только 36 - 18 -1: = 17 бит информации. (4) может быть, мне не хватает еще одной симметрии   -  person wildplasser    schedule 18.04.2015
comment
Мне нужно уточнить: битовые транспозиции на входе выглядят так: BIT (n): BIT (n + 1) заменяется на BIT (x): BIT (x + 1) для случайных x и n, оба из которые являются целыми числами в диапазоне от 0 до 70. Извините, я не понял! Более того, вся перестановка фактически меняет состояние - идентичные биты никогда не меняются местами.   -  person Conrad    schedule 18.04.2015
comment
@Conrad Поток перестановок может быть бесконечным, но есть только конечное число возможных перестановок. В принципе, их можно проиндексировать. Поскольку вы всегда меняете местами пары битов, вы можете думать о своем числе как о базовом 4. Количество перестановок зависит от количества каждого символа; очевидно, что тривиальный случай, когда все символы совпадают, имеет 0 перестановок.   -  person Nick Johnson    schedule 18.04.2015
comment
36 базовых 4 пунктов, да. Триллионы перестановок :)   -  person Conrad    schedule 19.04.2015

Ответы (2)


arrow_upward
1
arrow_downward

Вот решение, которое разрешило мою проблему: в опубликованном мною цикле между каждым XOR я вращаю хэш на k бит, где k - индекс цикла. В моем тестировании коллизии теперь столь же редки как при перестановках входных данных, так и при единичных битовых перестановках. Кажется, "парадокс дня рождения" удерживает меня от дальнейшего снижения частоты конфликтов, но 26 бит - это все, что я могу себе позволить - хеш-таблица уже огромна.

person Conrad    schedule 20.04.2015

arrow_upward
0
arrow_downward

Применяя парадокс дня рождения, вы можете увидеть, что статистически вы получите вероятность столкновения более 0,5 после хеширования (2 * * 13 = 8000) входов.

Лучшая попытка - использовать крипто-хеширование или некоторую хеш-функцию, основанную на хорошем и быстром ГПСЧ (на ум приходит Xorshift). Вы можете попробовать MurmurHash3 (автор утверждает, что он проходит некоторые статистические тесты и работает довольно быстро)

https://code.google.com/p/smhasher/source/browse/branches/chandlerc_dev/MurmurHash3.cpp

person Luka Rahne    schedule 18.04.2015