Хэш для неупорядоченного набора?
Я пытаюсь решить одностороннюю проблему индентичности, группа авторов хочет опубликовать что-то, не раскрывая свои собственные реальные username, так есть ли алгоритм/библиотека для хеширования неупорядоченного набора usernames?
Некоторые люди предложили бы сначала отсортировать набор по алфавиту,затем объединить, наконец хэшировать, но это не идеальное решение для динамического растущего массива.
Дополнительные вопросы (не обязательные для основного вопроса):
- Если такой алгоритм существует, можем ли мы проверить если a
usernameявляется одним из авторов по хэшу? - Если мы уже знаем хэш группы
usernames, то есть добавлен новый автор, можем ли мы получить новый хэш, не зная предыдущего автораusernames?
3 ответов:
Согласны ли вы принять малую вероятность ложных срабатываний, то есть имен, которые не являются авторами, которые будут неверно идентифицированы как авторы, если кто-нибудь проверит? (Вероятность можно сделать сколь угодно малой.)
Если это так, тофильтр Блума идеально подойдет.
Вы всегда можете создать хэш, независимо от того, знаете ли вы имена пользователей других авторов. Однако вы не можете гарантировать, что этоУникальный хэш.
Если вы заранее знаете все имена пользователей, вы можете создать минимальный идеальный хэш, но каждый раз, когда вы добавляете имя пользователя, вам придется создавать совершенно новую хэш-таблицу-с разными хэшами. Это явно не самое лучшее решение.
Это зависит от того, как вы хотите, чтобы ваши последние ключи выглядели.
Один возможность состоит в том, чтобы назначить уникальные последовательные идентификаторы именам пользователей, а затем запутать эти идентификаторы, чтобы они не выглядели как последовательные идентификаторы. Это похоже на то, что YouTube делает с их идентификаторами-они превращают 64-битное число в 11-символьную строку base64. Я написал небольшую статью об этом, с кодом в C#. Проверить http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=839 .
И, да, процесс обратимый.
Похоже, что один хэш не принесет вам никакой пользы. 1. Вы не можете проверить, что одно имя пользователя находится в хэше; вам нужно знать все имена пользователей. 2. Вы не можете добавить нового пользователя в хэш, не зная ничего о незашифрованных именах пользователей (порядок, в котором вы добавляете пользователей в хэш, будет иметь значение для всех хороших алгоритмов хэширования).
Для #2 частичное решение состоит в том, что вы не будете сохранять все имена пользователей, просто сохраните что-то вроде XOR всех существующих пользователей. Когда вы хотите добавить нового пользователя, XOR его с существующим и повторно хэшировать результат. Тогда не будет иметь значения, в каком порядке вы добавили пользователей.
Но реальное решение, я думаю, состоит в том, чтобы просто иметь набор хэшей, а не хэш множества. Есть ли причина, по которой ты не можешь этого сделать? Тогда вы можете легко сохранить набор упорядоченным или неупорядоченным, как вы хотите, вы можете легко добавить пользователей в набор, и легко проверить, если данный автор уже находится в наборе.
Comments