最高效的方法是什么来生成唯一随机字符串?

4
我需要高效地将一个5个字符的随机字符串插入到数据库中,同时确保它是唯一的。生成随机字符串不是问题,但目前我所做的是生成字符串,然后检查数据库是否已经存在……如果存在,我就重新开始。
有没有更有效的方法来完成这个过程?
请注意,我不想使用GUID或任何其他超过5个字符的东西……我必须坚持5个字符。
PS:我认为这没有什么区别,但我的字符串都是区分大小写的。
以下是“随机字符串”部分。
    Public Function GetRandomNumbers(ByVal numChars As Integer) As String
    Dim chars As String() = { _
     "A", "B", "C", "D", "E", "F", _
     "G", "H", "I", "J", "K", "L", _
     "M", "N", "O", "P", "Q", "R", _
     "S", "T", "U", "V", "W", "X", _
     "Y", "Z", "0", "1", "2", "3", _
     "4", "5", "6", "7", "8", "9", _
     "a", "b", "c", "d", "e", "f", _
     "g", "h", "i", "j", "k", "l", _
     "m", "n", "o", "p", "q", "r", _
     "s", "t", "u", "v", "w", "x", _
     "y", "z"}
    Dim rnd As New Random()
    Dim random As String = String.Empty
    Dim i As Integer = 0
    While i < numChars
        random += chars(rnd.[Next](0, 62))
        System.Math.Max(System.Threading.Interlocked.Increment(i), i - 1)
    End While
    Return random
End Function

不需要有人帮我写代码,只是想要了解一个效率概念。 - Chase Florell
7个回答

9
创建一个包含一大批5个字符字符串的表,这些字符串是按顺序添加的(因此它们是唯一的),并且具有GUID作为它们的主键。添加一列来指示它们是否已使用。
当您需要一个新的数字时,您从池中选择前1个,按guid排序(使其成为随机的),并将结果设置为“已用”。

1
这将创建一个额外的表,但是它会是独特的、随机的,并使用最可能的值,而无需不断搜索当前的值。原始解决方案会随着行数的增加而变得越来越慢。 - Edward Leno
所以我假设在生成初始随机字符串方面会有相当大的工作量。 - Chase Florell
1
为什么不在使用的时候直接删除列,而不是添加一个指示它们是否被使用的列?这样可以使查询更快且更容易编写。 - JohnFx
2
对于一个54进制的随机字符串,表格大小为4.59亿,除非使用可预测的序列(这时就不再是“随机”的了),否则你所做的只是把同样的问题从一个表格移到另一个表格。 - Einstein
“这就是随机性的问题。你永远无法确定。” [随机数生成器] (http://search.dilbert.com/comic/Random%20Number%20Generator) - mwolfe02
显示剩余3条评论

1

有一种方法可以随机选择未使用的唯一单词,但这可能不会比您现在所做的任何更好。

原则是确定未使用的单词的排列方式,根据未使用的排列数量生成随机数,并选择其中一个。

例如,如果您使用了一个具有三个字符的单词,只有字符0和1,则有八种可能的排列方式。 如果您已经使用了组合“010”和“100”,则会得到类似以下的结果:

PI = 排列索引
UI = 未使用的排列索引

No. PI UI
----------
000 0  0
001 1  1
010 2  -
011 3  2
100 4  -
101 5  3
110 6  4
111 7  5

要选择一个未使用的排列,您只需从0到5生成一个随机数,并选择相应的排列。

当然,保留所有可能的排列列表是不切实际的,因此您需要一个函数来确定字符串的排列索引,以及一个函数来确定排列索引的字符串。

此外,要确定哪些排列未使用,您必须检查哪些已使用,因此您仍然必须在某个时候查询表格。


1
你可以生成一个 GUID 并仅使用前5个字符吗?

3
这只是生成随机字符串的另一种方法,你仍然需要检查是否有重复。 - Guffa
我的第一反应也是如此,尽管他必须为区分大小写的字符串生成5个额外的位。 - schnaader

1

随机性更重要还是唯一性更重要?请注意我说的是“更”重要;我知道你需要两者。

如果随机性更重要,那么你需要一种跟踪历史值的方法。数据库本身(带有适当的索引)将是这样做的最佳方式。

如果唯一性更重要,则只需使用计数器并将其补零到五位数字。当然,这将限制您最多只能有100,000行,因此您可以选择使用计数器和字符空间转换(例如,1="A",2="B",27="AA"等)。


这个想法很简单,就是为了我正在开发的应用程序中的一个URL缩短器。我想要5个随机字符,就像bit.ly一样。 - Chase Florell

0

如果您要将字符串插入到现有的、已填充的表中,则始终需要检查该字符串是否不存在(它不必是显式的SELECT)。您可以手动执行此操作,也可以在列上具有唯一约束,并让数据库执行此操作。因此,如果数据库返回错误,因为该字符串已经存在,请生成另一个字符串。

请注意,如果您有一个空表并希望用多个随机字符串填充它,则这是一个不同的问题。


0

我认为你应该坚持你的原始想法。在索引上放置唯一约束并让数据库检查/报告重复项是一种相当有效的重复项检查方法,但这个假设取决于未提供的一些信息,例如行数和随机选择数据时遇到重复项的可能性。

完全预先填充具有您参数的唯一序列池需要一个4.59亿行的表。

您可以使用布隆过滤器将可管理的统计信息加载到数据库或主内存中,并避免重复项,但是根据行数和过滤器配置,当行数占459百万限制的相当比例时,这可能会导致过滤器饱和。由于过滤器可能报告错误的阳性结果,因此您应该努力确保不会陷入系统试图通过接近永远的排列来通过过滤器的情况。


0

既然你知道单词的长度,为什么不采用基于树的方法呢?(我们称之为随机树漫步)

假设你的单词有n个字符。生成S中所有符号s的列表,并为每个符号和可能的字符串位置关联一个计数器,本质上是一个维度为s乘以n的矩阵M。现在掷骰子并选择第一个字母,查找M(s,1)。如果M(s,1)大于或等于以s开头的可能单词数,请重新掷骰子。否则,将M(s,1)递增。

对于每个字母1到n,重复此过程。

直到使用太多单词为止,应该非常快速。


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