Блог

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

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

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

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

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

Если это так, то фильтр Блума идеально подойдет.

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

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

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

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

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

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

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

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