Мой вопрос во многом относится к этой теме:
Хеш-функция в списке, не зависящая от порядка элементов в это
По сути, у меня есть набор из N чисел. N является фиксированным и обычно довольно большим, например. 1000 например. Эти числа могут быть целыми числами или числами с плавающей запятой. Они могут быть равны, некоторые или все из них. Никакое число не может быть нулем.
Каждая комбинация K чисел, где K находится в диапазоне от 1 до N, приводит к вычислению хэша.
Возьмем пример с 3 номерами, которые я буду называть A, B и C. Мне нужно вычислить хэш для следующих комбинаций:
A
B
C
A+B
B+C
A+B+C
A+C
Вещи не зависят от порядка, C + A просто равно A + C. «+» может быть реальным дополнением или чем-то другим, например XOR, но это фиксировано. Точно так же каждое значение может сначала пройти через функцию, например.
f(A)
f(B)
f(A)+f(B)+f(C)
...
Теперь мне нужно избегать столкновений, но только определенным образом. Каждая комбинация помечается числом, либо 0, либо 1. Могут возникать коллизии, так что, если возможно, могут столкнуться только те, которые помечены одним и тем же номером (0 или 1). В этом случае многие коллизии даже приветствуются, особенно если это делает хеш-значение компактным. Я имею в виду, что в идеале лучший хэш имеет длину всего 1 бит! (0 или 1). Столкновения между комбинациями, помеченными разными номерами (0 и 1), по возможности должны происходить редко - в этом весь смысл.
Возьмем пример. Комбинация -> тег -> рассчитанное значение хеш-функции:
Combination Tag Hash
A -> 0 -> 0
B -> 1 -> 1
C -> 0 -> 2
A+B -> 0 -> 0
B+C -> 1 -> 1
A+B+C -> 1 -> 3
A+C -> 0 -> 2
Здесь хеш-значения действительны, потому что между комбинациями разных тегов нет коллизии. Например, A сталкивается с A + B, но они оба помечены «0».
Однако в целом хэш не очень хорош, потому что мне нужно 4 бита, что кажется много всего для 4 входных чисел.
Как найти хорошую (достаточно хорошую) хэш-функцию для этой цели?
Спасибо за ваше понимание.
