Хэш для неупорядоченного набора?

Question

Я пытаюсь решить проблему односторонней идентификации, группа авторов хочет опубликовать что-то без раскрытия своего собственного реального username, поэтому есть ли алгоритм / библиотека для хеширования неупорядоченного набора username с?

Некоторые люди предлагают сначала отсортировать набор по алфавиту, а затем соединить, наконец, хэш, но это не идеальное решение для динамически растущего массива.

Дополнительные вопросы (не обязательные для основного вопроса):

1. Если такой алгоритм существует, можем ли мы проверить, является ли username одним из авторов по хешу?
2. Если мы уже знаем хеш группы username s,затем добавлен новый автор, можем ли мы получить новый хеш, не зная предыдущего автора username s?

Answer 1

Готовы ли вы принять небольшую вероятность ложных срабатываний, то есть имен, которые не являются авторами, которые будут неверно идентифицированы как авторы, если кто-нибудь проверит? (Вероятность может быть сделана сколь угодно малой.)

Если да, то фильтр Блума идеально подходит для всех.

Answer 2

Звучит так, будто один хэш не принесет вам пользы1. Вы не можете проверить, что в хэше есть одно имя пользователя;вам нужно знать все имена пользователей.2. Вы не можете добавить нового пользователя в хеш, не зная чего-либо о нехэшированных именах пользователей (порядок, в котором вы добавляете пользователей в хеш, будет иметь значение для всех хороших алгоритмов хеширования).

Для # 2Частичное решение состоит в том, что вы не сохраните все имена пользователей, просто сохраните что-то вроде XOR всех существующих пользователей.Если вы хотите добавить нового пользователя, добавьте его в XOR к существующему и повторно хэшируйте результат.Тогда не имеет значения, в каком порядке вы добавили пользователей.

Но реальное решение, я думаю, это просто иметь набор хешей, а не хэш из набора.Есть ли причина, по которой вы не можете этого сделать?Затем вы можете легко сохранять упорядоченный или неупорядоченный набор, как вы хотите, вы можете легко добавлять пользователей в набор и легко проверять, есть ли данный автор уже в наборе.

Answer 3

Вы всегда можете сгенерировать хеш, независимо от того, знаете ли вы имена пользователей других авторов. Вы не можете гарантировать, что это уникальный хеш.

Если вы заранее знаете все имена пользователей, вы можете сгенерировать минимальный идеальный хеш, но каждый раз, когда вы добавляете имя пользователя, вам нужно будет создать совершенно новую хеш-таблицу - с разными хешами. Это, очевидно, не очень хорошее решение.

Это зависит от того, как вы хотите, чтобы ваши окончательные ключи выглядели.

Одна из возможностей - назначить уникальные последовательные идентификаторы именам пользователей, а затем скрыть эти идентификаторы, чтобы они не выглядели как последовательные идентификаторы. Это похоже на то, что делает YouTube со своими идентификаторами - они превращают 64-разрядное число в строку из 11 символов в формате base64. Я написал небольшую статью об этом, с кодом на C #. Проверить http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=839.

И, да, процесс обратим.