#c #algorithm #hash
#c #алгоритм #хэш
Вопрос:
Я получаю на входе моей функции список строк. Но порядок этих строк может отличаться для каждого вызова функции. Я хочу сгенерировать хэш из этих строк, но он должен быть равен для двух строк, исключая порядок. Итак, хэш hello и world должен быть равен хэшу world и hello . Хэш должен быть безопасным и устойчивым к столкновениям. Как я могу это сделать?
PS: Я могу получить хэш из массива байтов, но не исключая порядок.
Комментарии:
1. каковы ваши требования к этому хэшу? Должен ли он быть безопасным? Насколько вас беспокоят коллизии?
2. как насчет сортировки списка строк в алфавитном порядке перед генерацией хэша?
3. @AlanBirtles, да, хэш должен быть безопасным, меня беспокоят коллизии
4. вы должны отредактировать эти требования в своем вопросе, тем более что это делает недействительными 2 опубликованных в настоящее время ответа
5. Вопрос безопасности / коллизии на самом деле не актуален. Выберите любой хорошо известный криптографический хэш, который работает с одной строкой. Затем, чтобы использовать этот хэш в вашем списке строк: сначала отсортируйте строки (простой способ, вставьте каждый элемент в мультимножество). Затем определите внедрение из отсортированного списка строк (или мультимножества) в одну строку. Одна из таких инъекций: объединить отсортированный список с разделителем между каждым элементом, который не будет отображаться ни в одной строке (например, символ ` 0′, который по определению не отображается в строке).
Ответ №1:
Вам нужно использовать любой независимый от позиции хэш либо для байтов, либо использовать любой хэш для слов, а затем использовать независимый от позиции хэш для хэшей word.
Хэш, не зависящий от позиции, может быть любой функцией, которая имеет тот же результат при замене аргументов: , *, xor и т.д.
Комментарии:
1. Безопасно ли это? А как насчет столкновений?
2. Нет, конечно, это небезопасно. Коллизии происходят в любых типах хэшей, но, конечно, этот тип хэша может иметь больше коллизий в строках, чем хэши, зависящие от позиции.
Ответ №2:
Вы можете использовать сумму каждого символа для хэша:
'h' 'e' 'l' 'l' 'o' 'w' 'o' 'r' 'l' 'd' == 'w' 'o' 'r' 'l' 'd' 'h' 'e' 'l' 'l' 'o'