随机1对1哈希函数

3
今天我遇到了一个有趣的问题,搜索了互联网寻找解决方案,但没有找到。这个问题是:
用户创建一个账户,他会得到一个唯一的ID号,比如123,来代表他的账户。当另一个用户创建一个账户时,我可以将最近创建的ID号加1并分配给他,124。然而,这并不能完全匿名化所有人,因为他现在知道用户123在他之前注册。这是一个非常小的问题,但在某些情况下可能会导致更大的问题。
更好的解决方案是使ID号随机但唯一,以便没有人能够知道谁先来。
为了解决这个问题,可以使用标准哈希函数或随机数生成器为每个人创建一个唯一的ID号,但这样可能会出现碰撞。可以通过检查碰撞并再次运行来避免这种情况,但假设对于这个例子来说,这将使系统变得太慢。或者生成器正在运行不完整的信息,无法检查是否存在碰撞。
我想到的另一个想法是基本上有一副洗好的牌,你存储它并在需要新ID号时从顶部拿走一张。当你用完牌堆中的所有牌时,你从上一个牌堆中的最高牌继续,并洗牌那一副牌。这样做的缺点是你必须存储这副牌,如果你不小心丢失了它,你将遇到很多问题,试图重新创建它或在没有它的情况下继续。
一个非常类似的解决方案是每次基于固定种子重新创建这个洗好的牌,并取代替顶部的第n张牌。这种方法的问题是每次需要新卡片时重新洗牌可能会很昂贵。
我尝试想出的其他数学模型都有一个问题,即序列中的下一个数字是可预测的(每个数字与上一个数字相差一个固定的数量)。很多模型也存在碰撞的问题。
所以我的问题是:是否有一些数学模型可以插入数字来获得唯一的ID号,而不需要使用存储在内存中的“牌堆”(读:数组)或在每个函数调用上重新计算。
例如
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位。


4
恭喜!你刚刚得到了GUID:https://dev59.com/questions/lnRC5IYBdhLWcg3wOeSB - trailmax
不确定为什么trailmax的回答是一条评论,但这是一个很好的答案。大多数编程语言都有一个库来生成GUID。该值不能保证唯一,但碰撞的可能性非常小,对于所有实际目的而言,它们可以作为唯一的、非顺序的ID使用。 - Yevgeniy Brikman
4个回答

2
您可以使用块密码来实现此目的。当您加密一个块(一定数量的比特)时,密码将其映射到具有相同比特数的不同块。解密步骤会撤消这个映射。没有两个不同的块会被映射到同一个块。
因此,将您的用户 ID(假设为 64 位)使用 64 位块密码和秘密密钥进行加密,就可以得到随机化的用户 ID。要恢复原始用户 ID,只需使用相同的密钥进行解密。
如果您使用像BlowfishAES这样的知名算法,结果将是加密安全性最高的。

1
不确定如何存储这些数据,但您可以创建一个足够大的数组来处理所有使用您网站的用户。然后,您可以创建一个从随机的第n个索引开始并迭代随机次数的随机数字。当您落在一个空索引上时,将在该索引中放置一个值(例如1或其他),用户将获得该索引的ID。如果该索引已经具有值,则重复此过程,直到随机数落在索引上。这样做的好处是您甚至不需要迭代,因为您可以将随机数添加到当前索引。唯一需要逻辑的是某种模函数,以处理到达数组末尾的情况。希望这有所帮助。

这就是我所说的卡牌堆栈,我只是用了一个类比。我会在我的帖子中进行澄清 :) - Glen Takahashi

1
您可以选择一个周期大于您将需要支持的最大用户数的伪随机数生成器,然后只需使用上次使用的值对PRNG进行种子处理以生成下一个值。如果您不知道上次使用的值,可以使用初始种子,然后根据已注册用户的数量生成更多的值。您可能希望避免使用过大的PRNG值(例如,如果您将有少于65536个用户,则可能会找到一个16位2^16周期),以便这些数字易于记忆。

1

以下是一种灵活高效的方法:

  1. 维护一个哈希表。
  2. 选择一个与所需使用的哈希表大小成比例的数字M。
  3. 为前M个ID生成M个随机数,并通过哈希表查找避免冲突。
  4. 在M次生成的末尾,如果它们没有被使用,则将所有先前M个ID的ID + 1值添加到大小为M + 1的数组中。
  5. 如果之前未使用,则添加ID 0。
  6. 对于每个后续ID生成,随机从该数组中选择一个ID。
  7. 如果ID + 1不在哈希表中,则将其添加。

优点:

  1. 您可以使用M调节随机性和存储量。 M越高,您的ID就越随机。 您可能会在使用空间和随机性之间找到平衡。
  2. 您可以轻松使用内存数据库(如Redis)用作哈希表和数组。
  3. 生成唯一ID的时间复杂度为O(1)。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接