用于处理短链接冲突的最快 C# 实现

Question

我正在为我正在构建的缩短链接的服务预先生成短代码。它不是您常用的链接缩短器，因此我无法使用现成的链接缩短器，因为我们需要每秒处理近 1000 次缩短。

我有一项服务每 12 小时运行一次，向查找表中添加另外 200,000 个短链接，以快速生成链接。

随着短链接表变得越来越长，服务所需的时间也越来越长，以至于我们无法跟上所请求的短链接的需求。

缩短链接表有 180 万行。在用完之前，我们还剩下 28 万个链接。现在生成20万个链接需要1个多小时。

我显然做错了什么，可能是因为我只使用 List 进行比较。下面是代码块：

Stopwatch sw = Stopwatch.StartNew();
LtsDataContext ldc = new LtsDataContext();
List<string> currentCodes = ldc.ShortUrls.Select(s => s.ShortCode).ToList();
currentCodes = 
    currentCodes.Union(ldc.FastShortCodes.Select(s => s.ShortCode)).ToList();

int count = args.Length > 0 ? int.Parse(args[0]) : 200000;

List<string> newCodes = new List<string>(count);

for (int i = 0; i < count; i++)
{
    string newCode = Guid.NewGuid().ToString("N").Substring(0, 8);
    while (currentCodes.Contains(newCode) || newCodes.Contains(newCode))
        newCode = Guid.NewGuid().ToString("N").Substring(0, 8);
    newCodes.Add(newCode);
}

ldc.FastShortCodes.InsertAllOnSubmit(newCodes.Select(s => 
    new FastShortCode() { ShortCode = s }));
ldc.SubmitChanges();
Console.Write((decimal)sw.ElapsedMilliseconds / (decimal)1000);
Console.ReadKey();

Answer 1

您的问题是，通过使用 GUID 片段，您必须检查与越来越大的表的冲突。

我假设您不想创建顺序键，因为它很容易受到 URL 探索的影响，但是您应该从顺序的东西开始，然后对其进行混淆。

编辑

根据评论者的建议，我会：

1. take a sequential key
2. shift left 8
3. add a random value between 0 and 255
4. encode base-62 (0-9,A-Z,a-z)

您将不会发生冲突，并且随机位意味着随机尝试 URL 的人每 255 次尝试中只会获得一次命中。

Answer 2

如果我错了，请纠正我，但看起来您正在将整个短链接表（180 万）加载到列表中，然后使用 Contains 函数搜索它，正如 @Jeff Foster 指出的那样，这是一个 O(n ） 手术。

为什么不使用更乐观的方法呢？在数据库中，向 ShortUrls/FastShortCodes 表的 ShortCode 列添加唯一约束。然后简单地生成新的短代码并尝试插入它们。如果它们未满足唯一约束（这种情况不应经常发生），则只需捕获异常并重试即可。

我也同意 @egruin 的观点，即通过使用 GUID 的子字符串，您将自己限制为只有 15 个字符（0-9，AF）。我会寻找一种至少使用所有字母数字字符（0-9，AZ）的方法，这将显着减少您遇到的冲突次数。

Answer 3

为什么不对 currentCodes 和 newCodes 使用 Dictionary ？ List 的 Contains 方法需要遍历所有列表条目 O(n)，而 Dictionary 的运行时间复杂度为 O(1 ）。

编辑1
如果您无论如何都将所有链接保存在数据库中，为什么还需要 Guid？为什么不在链接中简单地使用数据库的主键呢？

编辑2
由于代码已经存在的可能性非常低，您可以尝试插入并捕获异常，然后再次尝试（乐观插入）。

Answer 4

这是您在这一行中的问题：

currentCodes.Contains(newCode) || newCodes.Contains(newCode)

随着描述问题的每次添加，这将需要越来越多的内容。我怀疑您是否对此的数学复杂性感兴趣，但这将接近 (N*N)/2。

解决方案是使用HashTable。