哈希无序集？

我正试图解决一个单向的indentity问题，一组作者想发布一些东西而不透露自己的真实username，那么有没有算法/库散列无序的一套username s？哈希无序集？

有些人会建议，首先按字母顺序排序，然后加入，最后散列，但这不是动态增长阵列的理想解决方案。

Additionaly问题（不是强制的主要问题）：

如果存在这样的算法，我们可以验证一个username是哈希作者之一？
如果我们已经知道一组username的散列，那么有一位新作者补充说，如果我们不知道以前的作者username是否可以得到一个新的散列？

来源

2011-05-03 est

你能澄清你实际想要达到的目标吗？如果你想发布一些东西而不泄露你自己的用户名，为什么不把它的签名保留下来呢？你想要这个数据结构启用什么？ – 2011-05-03 16:26:25

您是否愿意接受误报的可能性较小，即不是作者的姓名，如果有人检查，这些姓名会被错误地识别为作者？（概率可以任意小）

如果你是，那么bloom filter将完全符合法案。

来源

2011-05-03 06:28:00 btilly

哇，很酷。我会研究这:)顺便说一句，布隆过滤器消化固定长度？我真的想保留作者的数量作为秘密。 – est 2011-05-03 06:42:21

布隆过滤器的问题在于用户名的基数很重要。经典布隆过滤器仅适用于预期的基数（允许误报率）。 – 2011-05-03 06:50:07

@est：布隆过滤器是固定长度。假阳性率取决于作者的数量和长度。 @ thomas-jung：很高兴知道失败模式，但我认为在这种情况下可能会好。 – btilly 2011-05-03 06:56:09

无论您是否知道其他作者的用户名，您都可以生成散列。不过，你不能保证它是一个独特的散列。

如果您事先知道所有的用户名，可以生成最小的完美哈希值，但是无论何时添加用户名，您都必须生成一个全新的哈希表 - 带有不同的哈希值。这显然不是一个好的解决方案。

这取决于你想要你的最终键看起来像什么。

一种可能性是将唯一顺序ID分配给用户名，然后对这些ID进行模糊处理，以使它们看起来不像顺序ID。这与YouTube用户的ID相似 - 他们将64位数字转换为11个字符的base64字符串。我用C＃中的代码写了一篇关于该文章的文章。退房http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=839。

而且，是的，这个过程是可逆的。

来源

2011-05-03 06:19:44

这听起来像一个单一的哈希对你没有任何好处。 1.您无法验证单个用户名在散列中;你需要知道所有的用户名。 2.如果不知道有关非加密用户名的信息（您将用户添加到哈希中的顺序对所有好的哈希算法都很重要），则无法将新用户添加到哈希中。

对于＃2，部分解决方案是您不会保留所有用户名，只是保持类似所有现有用户的异或。当你想添加一个新用户时，将它与现有用户进行异或并重新对结果进行散列。那么，你添加用户的顺序并不重要。

但我认为真正的解决方案只是拥有一组哈希，而不是一组哈希。有没有理由不能这样做？然后，您可以根据需要轻松地保留该集合的有序或无序，您可以轻松地将用户添加到集合中，并轻松检查给定的作者是否已经在该集合中。

来源

2011-05-03 06:21:39 mgiuca

感谢您的想法，我不想要一个“散列”的原因是保持作者的数量秘密。 – est 2011-05-03 06:25:08

哈希无序集？

回答

相关问题