代码之家  ›  专栏  ›  技术社区  ›  jakogut

四个无符号整数的哈希函数(C++)

  •  9
  • jakogut  · 技术社区  · 15 年前

    不过,我在编写一个像样的散列函数时遇到了麻烦。当我最初编写这段代码时,我将四个整数中的每一个简单相加,我知道这是不够的。我尝试过其他几种技巧,如移位和添加,但都没有效果。我得到了一个散列,但它的质量很差,而且函数会产生大量冲突。

    哈希输出可以是32位或64位整数。所讨论的函数会生成数十亿个哈希,因此冲突在这里是一个真正的问题,我愿意使用一个更大的变量来确保冲突尽可能少。

    7 回复  |  直到 15 年前
        1
  •  8
  •   Vinko Vrsalovic    15 年前

    为什么不将这四个整数存储在一个合适的数据结构中,并对它们进行比较呢?在这种情况下对它们进行散列的好处在我看来是可疑的,除非存储是一个问题。

    如果存在存储问题,则可以使用所分析的哈希函数之一 here .

        2
  •  4
  •   Steve Jessop    15 年前

    下面是一个从4个整数到1个整数的相当合理的哈希函数:

    unsigned int hash = in[0];
    hash *= 37;
    hash += in[1];
    hash *= 37;
    hash += in[2];
    hash *= 37;
    hash += in[3];
    

    还有其他具有其他特性的散列,但在证明其他特性之前,通过素数乘法进行累加是一个良好的开端。如果愿意,可以尝试使用xor进行累加,而不是加法。无论哪种方式,都很容易产生冲突(例如{1,0,a,b}与所有a,b的{0,37,a,b}冲突),因此您可能希望选择一个素数,您认为它与函数中任何看似合理的实现错误无关。所以,如果你的函数中有很多模-37运算,也许可以用1000003代替。

        3
  •  3
  •   Will    15 年前

    因为散列可以生成冲突,所以无论如何都必须将密钥保留在内存中才能发现这些冲突。Hashmaps和其他标准数据结构在其内部簿记中实现了这一点。

        4
  •  1
  •   Tobias Langner    15 年前

    我完全同意Vinko的观点——只是比较一下。如果你仍然想要一个好的散列函数,你需要分析你的4个非单整数的分布。然后,您必须以某种方式构建哈希函数,结果将均匀分布在整个32位哈希值范围内。

    一个简单的例子——让我们假设大多数时候,每个函数的结果都在0到255之间。然后,您可以轻松地将每个函数的低8位混合到哈希中。大多数时候,您会直接查找结果,只是有时候(当一个函数返回更大的结果时)会发生冲突。

    总之,如果没有关于这4个函数的结果是如何分布的信息,我们就无法帮助您使用一个好的哈希函数。

        5
  •  0
  •   Graphics Noob    15 年前

    为什么要炸土豆条?似乎std::set或std::multi set更适合存储这种输出。您所需要做的就是将四个整数包装在一个结构中,然后编写一个简单的比较函数。

        6
  •  0
  •   Adisak    15 年前

    试用 CRC FNV . FNV很好,因为它速度快,并且有一个定义的折叠位的方法来获得“更小”的散列值(即12位/24位/etc)。

        7
  •  0
  •   larsmoa    15 年前

    可能有点过分,但是考虑一下 Boost.Hash