C# 创建你自己的 Tinyurl 风格的 uid
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/190701/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Creating your own Tinyurl style uid
提问by Chris S
I'm writing a small article on humanly readable alternatives to Guids/UIDs, for example those used on TinyURL for the url hashes (which are often printed in magazines, so need to be short).
我正在写一篇关于 Guids/UIDs 的人类可读替代品的小文章，例如那些在 TinyURL 上用于 url 哈希的文章（通常印在杂志上，因此需要简短）。
The simple uid I'm generating is - 6 characters: either a lowercase letter (a-z) or 0-9.
我生成的简单 uid 是 - 6 个字符：小写字母 (az) 或 0-9。
"According to my calculations captain", that's 6 mutually exclusive events, although calculating the probability of a clash gets a little harder than P(A or B) = P(A) + P(B), as obviously it includes numbers and from the code below, you can see it works out whether to use a number or letter using 50/50.
“根据我的计算队长”，这是 6 个相互排斥的事件，尽管计算冲突的概率比 P(A 或 B) = P(A) + P(B) 更难，因为显然它包括数字和来自下面的代码，你可以看到它使用 50/50 来计算是使用数字还是字母。
I'm interested in the clash rate and if the code below is a realistic simulation of anticipated clash rate you'd get from generating a hash. On average I get 40-50 clashes per million, however bare in mind the uid wouldn't be generated a million times at once, but probably only around 10-1000 times a minute.
我对冲突率感兴趣，如果下面的代码是对预期冲突率的真实模拟，您将通过生成哈希获得。平均每百万我会得到 40-50 次冲突，但是请记住，uid 不会一次生成一百万次，但可能每分钟只生成 10-1000 次左右。
What is the probability of a clash each time, and can anyone suggest a better way of doing it?
每次发生冲突的概率是多少，谁能提出更好的方法？
static Random _random = new Random();
public static void main()
{
// Size of the key, 6
HashSet<string> set = new HashSet<string>();
int clashes = 0;
for (int n=0;n < 1000000;n++)
{
StringBuilder builder = new StringBuilder();
for (int i =0;i < 7;i++)
{
if (_random.NextDouble() > 0.5)
{
builder.Append((char)_random.Next(97,123));
}
else
{
builder.Append(_random.Next(0,9).ToString());
}
}
if (set.Contains(builder.ToString()))
{
clashes++;
Console.WriteLine("clash: (" +n+ ")" +builder.ToString());
}
set.Add(builder.ToString());
_random.Next();
//Console.Write(builder.ToString());
}
Console.WriteLine("Clashes: " +clashes);
Console.ReadLine();
}
UPDATE:Here's the resulting articlefrom this question
I really asked two questions here so I was cheating. The answer I was after was rcar's, however Sklivvz's is also the answer to the 2nd part (an alternative). Is it possible to make a custom unique id generator in a database, or would it be client side (which would be 2 possible reads first)?
我真的在这里问了两个问题，所以我在作弊。我所追求的答案是 rcar 的，但是 Sklivvz 的也是第二部分（替代方案）的答案。是否可以在数据库中创建一个自定义的唯一 id 生成器，或者它是客户端（首先是 2 个可能的读取）？
The general idea I was after was using Ids in databases or other stores that can be used by phone or printed material, not a giant 16 byte guid.
我所追求的一般想法是在数据库或其他商店中使用 Id，可以通过电话或印刷材料使用，而不是一个巨大的 16 字节 guid。
UPDATE 2:I put the formula for two mutually exclusive events above instead of 2 independent ones (as getting an 'a' the first time doesn't mean you can't get an 'a' the second time). Should've been P(A and B) = P(A) x P(B)
更新 2：我在上面列出了两个互斥事件的公式，而不是两个独立事件（因为第一次获得“a”并不意味着您第二次无法获得“a”）。应该是 P(A 和 B) = P(A) x P(B)
采纳答案by Randy
The probability of a collision against one specific ID is:
与一个特定 ID 发生冲突的概率为：
p = ( 0.5 * ( (0.5*1/10) + (0.5*1/26) ) )^6
which is around 1.7×10^-9.
大约是 1.7×10^-9。
The probability of a collision after generating n IDs is 1-p^n, so you'll have roughly a 0.17% chance of a collision for each new insertion after 1 million IDs have been inserted, around 1.7% after 10 million IDs, and around 16% after 100 million.
生成 n 个 ID 后发生冲突的概率为 1-p^n，因此在插入 100 万个 ID 后，每个新插入的冲突概率大约为 0.17%，在 1000 万个 ID 后大约为 1.7%，并且1 亿后约为 16%。
1000 IDs/minute works out to about 43 million/month, so as Sklivvz pointed out, using some incrementing ID is probably going to be a better way to go in this case.
1000 个 ID/分钟相当于大约 4300 万/月，所以正如 Sklivvz 指出的那样，在这种情况下使用一些递增的 ID 可能是更好的方法。
EDIT:
编辑：
To explain the math, he's essentially flipping a coin and then picking a number or letter 6 times. There's a 0.5 probability that the coin flip matches, and then 50% of the time there's a 1/10 chance of matching and a 50% chance of a 1/26 chance of matching. That happens 6 times independently, so you multiply those probabilities together.
为了解释数学，他基本上是抛硬币，然后选择一个数字或字母 6 次。硬币翻转匹配的概率为 0.5，然后有 50% 的时间有 1/10 的匹配机会和 50% 的 1/26 机会匹配。这种情况独立发生 6 次，因此您将这些概率相乘。
回答by Greg Hewgill
Look up the Birthday Paradox, it's the exact problem that you're running into.
查找生日悖论，这正是您遇到的问题。
The question is: How many people do you need to get together in a room, so that you have a 50% chance of any two people having the same birthdate? The answer may surprise you.
问题是：你需要多少人在一个房间里聚在一起，这样任何两个人有50%的机会有相同的生日？答案可能会让你大吃一惊。
回答by Omar Kooheji
Why not just use a hashing algorithm? and use a hash of the url?
为什么不直接使用散列算法？并使用 url 的哈希值？
if you are using random numbers chances are you will get clashes because they are indeterminate.
如果您使用随机数，很可能会发生冲突，因为它们是不确定的。
hashes arent proovably unique but there is a fairly good chance that the hash of a string will be unique.
哈希值不是唯一的，但字符串的哈希值很有可能是唯一的。
Correction
更正
Actually wait you want them to be humanly readable... if you put them in hex they are technically humanly readable.
实际上，等待您希望它们具有人类可读性……如果您将它们放入十六进制，它们在技术上是人类可读的。
or you could use an algorithm that converted a hash into a humanly readable string. if the humanly readable string is a different representation of the hash it should also be as "unique" as the hash, ie base 36 of the original hash.
或者您可以使用一种算法将哈希转换为人类可读的字符串。如果人类可读的字符串是散列的不同表示，它也应该与散列一样“唯一”，即原始散列的基数为 36。
回答by Sklivvz
Why do you want to use a random function? I always assumed that tinyurl used a base 62 (0-9A-Za-z) representation of a sequential Id. No clashes and the urls are always as short as possible.
为什么要使用随机函数？我一直认为 tinyurl 使用了一个基本的 62 (0-9A-Za-z) 表示顺序 Id。没有冲突，网址总是尽可能短。
You would have a DB table like
你会有一个像这样的数据库表
Id URL
1 http://google.com
2 ...
... ...
156 ...
... ...
and the corresponding URLs would be:
相应的 URL 将是：
http://example.com/1
http://example.com/2
...
http://example.com/2W
...
回答by mattlant
I would generate a random value representative of the data that you are going to hash, and then hash that and check clahses rather than trying to simulate with random manually made hashes. This will give you a better indicator. And you will have more randomness because you will have more to randomize (Assuming your data to be hashed is larger :) ).
我会生成一个代表您要散列的数据的随机值，然后对其进行散列并检查 clahses，而不是尝试使用随机的手动散列进行模拟。这将为您提供更好的指标。而且您将有更多的随机性，因为您将有更多的随机性（假设要散列的数据更大:)）。
回答by Ryan
If you're using 6 characters, a-z and 0-9, thats a total of 36 characters. The number of permutations is thus 36^6 which is 2176782336.. so it should only clash 1/2176782336 times.
如果您使用 6 个字符，az 和 0-9，则总共 36 个字符。因此，排列的数量是 36^6，即 2176782336.. 所以它应该只冲突 1/2176782336 次。
回答by cfeduke
from wikipedia:
来自维基百科：
When printing fewer characters is desired, GUIDs are sometimes encoded into a base64 or Ascii85 string. Base64-encoded GUID consists of 22 to 24 characters (depending on padding), for instance:
当需要打印较少的字符时，有时会将 GUID 编码为 base64 或 Ascii85 字符串。Base64 编码的 GUID 包含 22 到 24 个字符（取决于填充），例如：
7QDBkvCA1+B9K/U0vrQx1A
7QDBkvCA1+B9K/U0vrQx1A==
and Ascii85 encoding gives only 20 characters, e. g.:
和 Ascii85 编码只给出 20 个字符，例如：
5:$Hj:PfRLB9%kU\Lj
So if you are concerned with uniqueness, a base64 encoded GUID gets you somewhat closer to what you want, though its not 6 characters.
因此，如果您关心唯一性，base64 编码的 GUID 会让您更接近您想要的东西，尽管它不是 6 个字符。
Its best to work in bytes first, then translate those bytes into hexadecimal for display, rather than working with characters directly.
最好先处理字节，然后将这些字节转换为十六进制进行显示，而不是直接处理字符。
回答by ila
Some time ago I did exactly this, and I followed the way Sklivvz mentioned. The whole logic was developed with a SQL server stored procedure and a couple of UDF (user defined functions). The steps were:
前段时间我正是这样做的，我遵循了 Sklivvz 提到的方式。整个逻辑是使用 SQL 服务器存储过程和几个 UDF（用户定义函数）开发的。步骤是：
- say that you want to shorten this url: Creating your own Tinyurl style uid
- Insert the URL in a table
- Obtain the @@identity value of the last insert (a numeric id)
- Transform the id in a corresponding alphanumeric value, based on a "domain" of letters and numbers (I actually used this set: "0123456789abcdefghijklmnopqrstuvwxyz")
- Return that value back, something like 'cc0'
- 说你想缩短这个网址：Creating your own Tinyurl style uid
- 在表格中插入 URL
- 获取最后一次插入的@@identity 值（一个数字 id）
- 根据字母和数字的“域”将 id 转换为相应的字母数字值（我实际上使用了这个集合：“0123456789abcdefghijklmnopqrstuvwxyz”）
- 返回该值，例如“cc0”
The conversion was realized thru a couple of very short UDF.
转换是通过几个非常短的 UDF 实现的。
Two conversion called one after the other would return "sequential" values like these:
一个接一个调用的两个转换将返回“顺序”值，如下所示：
select dbo.FX_CONV (123456) -- returns "1f5n"
select dbo.FX_CONV (123457) -- returns "1f5o"
If you are interested I can share the UDF's code.
如果您有兴趣，我可以分享 UDF 的代码。
