另一个类代替 SHA1 管理使校验和的长度小于 128 个字节

Question

我有一个表，其中有一列 (AbsoluteUrl NVARCHAR(2048))，并且我想查询该列，因此需要很长时间才能将每条记录与我自己的字符串进行比较。这张表至少有1000000条记录。

现在我认为有更好的解决方案来为每个 AbsoluteUrl 制作校验和并将其与校验和一起比较而不是与 AbsoluteUrl 列进行比较。所以我使用下面的方法来生成校验和。但我想要另一个类来制作长度小于 128 个字节的校验和。

public static byte[] GenerateChecksumAsByte(string content)
    {
        var buffer = Encoding.UTF8.GetBytes(content);
        return new SHA1Managed().ComputeHash(buffer);
    }

这种方法对我的工作有好处吗？

更新

根据答案，我想更深入地解释。所以实际上我正在研究非常简单的网络搜索引擎。如果我想简单地解释一下，我必须说，当提取网页的所有 url 时（找到的 url 的集合），那么我将把它索引到 Urls 表中。

UrlId uniqueidentifier NotNull 主键（聚集索引） AbsoluteUrl nvarchar(2048) NoyNull Checksum varbinary(128) NotNull

所以我首先搜索表是否有相同的 url 之前已索引或未索引。如果没有则创建新记录。

public Url Get(byte[] checksum)
    {
        return _dataContext.Urls.SingleOrDefault(url => url.Checksum == checksum);
        //Or querying by AbsoluteUrl field
   }

和保存方法。

public void Save(Url url)
    {
        if (url == null)
            throw new ArgumentNullException("url");
        var origin = _dataContext.Urls.GetOriginalEntityState(url);
        if (origin == null)
        {
            _dataContext.Urls.Attach(url);
            _dataContext.Refresh(RefreshMode.KeepCurrentValues, url);
        }
        else
            _dataContext.Urls.InsertOnSubmit(url);
        _dataContext.SubmitChanges();
    }

例如，如果我在一页上找到 2000 个 url，我必须搜索 2000 次。

Answer 1

我同意史蒂文的观点，您应该首先在该字段上尝试索引，看看它是否真的是“比较每个记录”才是瓶颈。

但是，根据您的数据库，对 NVARCHAR(2048) 建立索引可能是不可能的，而且实际上可能是瓶颈。在这种情况下，如果出现以下情况，生成校验和实际上可以提高搜索性能：

1. 您执行的比较次数比插入次数多得多。
2. 比较校验和比比较 NVARCHAR 更快。
3. 大多数校验和都是不同的。

您没有向我们展示任何查询或示例数据，因此我无法知道这些是否属实。如果它们是真的，您确实可以通过为每个 AbsoluteUrl 生成校验和并假设这些校验和不同的值不同来提高性能。如果校验和相同，则必须进行字符串比较以查看值是否匹配，但如果校验和不同，则可以确定字符串不同。

在这种情况下，不需要加密校验和，您可以使用更小、更快的校验和算法，例如 CRC64 。

正如史蒂文指出的，如果你的校验和相同，你就不能假设你的值是相同的。但是，如果您的大多数值都不同并且您有一个良好的校验和，则您的大多数校验和将不同并且不需要字符串比较。

Answer 2

不，这不是一个好方法。

对于索引字段来说，一百万条记录没什么大不了的。另一方面，由于鸽巢原理（又名生日悖论），任何校验和/哈希/您生成的任何内容都可能出现误报。让它变大会减少但不会消除这种机会，但它确实会减慢速度，直至速度不再增加。

只需在字段上添加一个索引，看看会发生什么。

Answer 3

您想要使用大小为 (p) 的散列作为键，预计最多 1m 条记录 (u)。要回答这个问题，您必须首先进行数学计算...

针对要考虑的每个哈希大小解决以下问题： 1 - e ^ (-u^2 / (2 * p))

• 32 位：100% 碰撞机会
• 64 -位：0.00000271% 碰撞机会
• 128 位：0%（太小，无法用双精度计算）

现在您应该有足够的信息来做出明智的决定。以下是在 64 位密钥上生成上述计算的代码：

double keySize = 64;
double possibleKeys = Math.Pow(2, keySize);
double universeSize = 1000000;
double v1, v2;
v1 = -Math.Pow(universeSize, 2);
v2 = 2.0 * possibleKeys;
v1 = v1 / v2;
v1 = Math.Pow(2.718281828, v1);
v1 = 1.0 - v1;
Console.WriteLine("The resulting percentage is {0:n40}%", v1 * 100.0);

就我个人而言，我自己至少坚持使用 128 位哈希。此外，如果冲突可能导致任何形式的安全漏洞，您至少需要使用 v2 SHA 哈希 (SHA256/SHA512)。

现在，如果这只是数据库的优化，请考虑以下事项：

1. 向表中添加 32 位哈希码。
2. 创建一个包含 32 位哈希值和原始字符串的复合密钥。
3. 始终在哈希值和原始字符串上查找。
4. 假设哈希只是一种优化，而不是唯一的。