哈希無序集？

我正試圖解決一個單向的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

哈希無序集？

回答

相關問題