随机的1对1散列函数

今天我遇到了一个有趣的问题，并在互联网上搜索寻找解决方案，但没有找到任何。问题是这样的：随机的1对1散列函数

用户创建一个帐户，并给他一个唯一的ID号码，如123，来表示他的帐户。当另一个用户创建一个帐户时，我可以给最近创建的ID号码加1，并将其分配给他（124）。但是，这并不完全匿名每个人，因为他现在知道用户123在他之前注册。一个非常小的问题，但在一些可能的情况下，这可能会导致更大的问题。

更好的解决方案是让ID随机但唯一，这样就不会有人知道谁先来了。

为了解决这个问题，可以使用标准的散列函数或随机数发生器为每个人创建一个唯一的ID，但是然后碰到碰撞的可能性。这可以通过检查碰撞并再次运行来避免，但是对于这个例子来说，这会使系统太慢。或者可能是发电机运行的信息不完整，无法检查是否有碰撞。

我想出了一个不同的想法，就是基本上有一个洗牌的卡片组，你可以随时储存，并在任何时候需要一个新的ID。当你在套牌中用尽卡牌时，你会在最后一张牌组中的最高卡牌上继续一个新套牌，然后洗牌。缺点是你必须储存这副牌，如果你不小心失去了套牌，你会遇到许多问题，试图重新创建它，或者没有它就继续下去。

这一个非常类似的解决方案是每次重新创建基于固定种子的洗牌甲板，并取代甲板上的第n张牌而不是顶部。这样做的问题是，每当你需要一张新卡时，洗这个卡组可能会很昂贵。

我试图提出的其他数学模型都存在序列中的下一个数字是可预测的问题（每个数字与前一个数字相距一定数量）。他们中的很多人也有碰撞的问题。

所以我的问题是：是否有一些数学模型，我可以插入数字来获得独特的ID，不需要使用存储在内存中的“deck”（读取：数组），或在每次函数调用时重新计算。

例如

randomID(number, seed, range) 
randomID(1,123,1000) = 284 
randomID(2,123,1000) = 739 
randomId(3,123,1000) = 088 
randomId(3,888,1000) = 912

我已经看过了https://code.google.com/p/smhasher/wiki/MurmurHash3这似乎是有前途的，但我不认为它适用于对数字的任意范围，只有在32位或64位。

来源

2014-07-21 Glen Takahashi

恭喜！你刚刚想出了GUID：http://stackoverflow.com/questions/371762/what-exactly-is-guid-why-and-where-i-should-use-it – trailmax

不知道为什么trailmax的答案是一个评论，但这是一个很好的答案。大多数语言都有一个库来生成一个GUID。价值并不保证是独一无二的，但碰撞的可能性是天文数字小，对于所有的实际目的，它们都是独特的，无序的ID。 –

您可以选择一个伪随机数生成器，其周期大于您需要支持的最大用户数，然后您只需将PRNG与最后使用的值一起生成以生成下一个。如果以某种方式失去了最后使用的值，可以使用初始种子，然后根据已注册用户的数量生成更多值。您可能希望避免PRNG的值过大（例如，如果您的用户数少于65536，可能会找到16位一个2^16的周期），所以这些数字是切合实际的。

来源

2014-07-22 02:57:35

不确定如何存储此信息，但您可以创建一个足够大的大型阵列，以处理将使用您的网站的所有用户。然后，您可以创建一个随机数，该随机数始于随机的第n个索引并迭代随机数量。当你落在一个空的索引上时，你在该索引中放置一个值（例如1或其他），并且用户将得到该索引的ID。如果该索引已经有一个值，则重复该过程直到随机数落在索引上。关于这一点的好处是你甚至不需要迭代，因为你可以将随机数添加到当前索引。唯一的逻辑是某种mod函数来处理你到达数组尾部的情况。希望这可以帮助。

来源

2014-07-21 22:54:13 Maxqueue

这就是我的意思，我只是用一个比喻。我会在我的文章中澄清:) –

这里是办法，灵活，高效： -

维护一个哈希表。

选择一个与您需要使用的散列表大小成正比的数字M.

为第一个M ID生成M个随机数并通过散列表查找防止冲突。

在M代的末尾添加M个先前id的所有id + 1值（如果它们未用于大小为M + 1的数组）。

如果先前未使用，请添加ID 0。

对于每一个下一代id代从随机数组中选择一个id。

如果不在散列表中，则添加id + 1。

优点： -

可以调节使用M.更高的多M随机您的ID用于随机性和存储。您可能会发现在空间使用和随机性之间存在权衡。

你可以很容易地使用像redis这样的内存数据库作为散列表和数组。

的时间生成唯一ID的复杂度为O（1）

来源

2014-07-22 05:20:00

可以使用block cipher实现这一目标。当你加密一个块（固定数量的比特）时，密码器将它映射到具有相同比特数的不同块。解密步骤解除了这一点。没有两个不同的块被映射到相同的块。

因此，请将您的用户ID设为64位，并使用64位块密码和密钥对其进行加密，并且您有随机用户标识。要获得原始用户标识，只需使用相同的密钥进行解密。

如果您使用像Blowfish或AES这样的着名算法，则结果将按照您的密码安全。

来源

2014-07-22 20:03:50 HugoRune

随机的1对1散列函数

回答

相关问题