时间戳

首页 > 解决方案 > 没有冲突的高性能散列？

c# - 没有冲突的高性能散列？

问题描述

下面的散列函数大量借鉴了这篇文章，但在我的应用程序中它有太多的冲突。

public static class Hashing
{
  private const int FNV1a_offsetBias = unchecked( ( int )0x81_1c_9d_c5 );
  private const int FNV1a_prime = 16_777_619;

  public static int FNV1a(params dynamic[] values) {
     var hash = FNV1a_offsetBias;

     foreach ( var value in values )
        hash = FNV1a_Crank(hash, value.GetHashCode());

     return hash;
  }

  private static int FNV1a_Crank(int start, int addendum) {
     unchecked {
        start *= FNV1a_prime;
        start += addendum;
     }

     return start;
  }
}

我需要保证唯一的高性能散列。我意识到它可能需要比上面的函数慢，但我希望能找到一些不会显着变慢的东西。上面链接的 SE 帖子引人入胜且有用，但也让我感到困惑并想知道该使用什么。

我的散列用例是这样的：我有一个应用程序，每天将数百万条记录插入我的数据库。插入的表包含唯一键，因此任何违反唯一性的插入都会引发异常。我不能允许抛出这些异常，因为它太慢了，而且出于其他原因最好避免。所以我使用上面的函数对每个插入的复合唯一键中的列值进行哈希处理，并存储在哈希表中。在每次插入之前，我都会生成一个哈希并在哈希表中查找该哈希。如果它不存在，那么我可以安全地进行插入。如果它在那里，则记录已经存在，我跳过插入。

它非常快，一开始我认为它有效。但后来我发现了几十个案例（数百万个），其中哈希冲突，因此我的应用程序认为已经插入了一条记录——而实际上它没有。所以我会丢失记录，这对企业来说是不可接受的。

以下是我正在散列的数据类型的一些示例：

Hasher("Z125",  "99-8ZG10", "SpecialZ_S07181_2");
Hasher("G125");
Hasher("G99-76", "F78_XYZ_92323");

所以我正在寻找 ac# 函数，它提供了保证唯一的最快的哈希算法。换句话说，我需要一种高效的方法来检查该记录是否已经存在于表中数百万次？散列似乎是最快的方法，但唯一性是最重要的。

有任何想法吗？

标签： c#hashcryptography

解决方案

您的目标似乎是为您的数据库记录生成唯一标识符。通常，您的数据库系统将允许您为数据库记录设置主键，然后系统将确保该主键在整个数据库中是唯一的。这样的主键通常对于许多应用程序来说已经足够了。但是，还有其他一些事情需要考虑，例如：

  • 标识符是否必须难以猜测，或者仅仅是“看起来随机”。
  • 标识符是否是唯一授予对记录的访问权限的东西。

生成唯一标识符的最佳方法将取决于这些问题和其他问题，我在“唯一随机标识符”一节中给出了这些问题。您应该使用我在该部分中给出的六个问题的答案来编辑您的问题帖子；答案将进一步建议使用什么样的标识符。但是，如果您不能容忍重复标识符的风险，例如在这种情况下，那么随机数和列值的哈希都不适合作为唯一标识符，除非应用程序检查它们的唯一性。

推荐阅读