logo标签列表

什么是适用于短字符串（标签名称）的最佳32位哈希函数？

algorithmhashtags32-bit
55

什么是针对相对较短字符串的最佳32位哈希函数？

这里的字符串是由英文字母、数字、空格以及一些其他字符(#, $, ., ...)组成的标签名。例如：单元测试，C# 2.0。

我正在寻找“最好”的哈希函数，即“最小碰撞”，对于我的目标来说性能并不重要。

1
可能是重复的问题 https://dev59.com/lHVC5IYBdhLWcg3wjyDu - N 1.1
2
并不完全是这样，因为我的问题在哈希大小方面更具体，并忽略了性能。我不仅仅在寻找一个哈希函数，我在寻找一个有意义的选择——我知道有CRC32和FNV32，但哪个对我的领域更好呢？ - Andrey Shchekin
你的标签列表是固定的字符串集合还是会随着时间动态增长？ - Vinko Vrsalovic
@Andrey：有什么限制吗？ - kennytm
27
以下页面提供了多种通用哈希函数的实现，这些函数高效且碰撞最小化：http://partow.net/programming/hashfunctions/index.html - Matthieu N.
显示剩余2条评论
9个回答
29

我不确定这是否是最好的选择，但这里是一个用于字符串的哈希函数：

编程实践（哈希表，第57页）

/* hash: compute hash value of string */
unsigned int hash(char *str)
{
   unsigned int h;
   unsigned char *p;

   h = 0;
   for (p = (unsigned char*)str; *p != '\0'; p++)
      h = MULTIPLIER * h + *p;
   return h; // or, h % ARRAY_SIZE;
}

经验上，对于 ASCII 字符串的哈希函数，取乘数为31和37已被证明是一个不错的选择。

3
是的，我们对于字符串和路径使用这个确切的哈希函数，其中MULTIPLIER = 37。这对我们来说非常有效，即使在两年后我仍未遇到冲突问题（当然并不能保证以后不会出现）。 - zebrabox
这看起来肯定足够简单。如果更简单的方法可行，为什么还要创建FNV呢？ - Andrey Shchekin
@Andrey Shchekin，当我处理原始字节（blob）时，我使用FNV哈希。也许，上述函数在处理字符串时会产生更好的结果。我不确定。 - Nick Dandoulakis
1
@Andrey和Nick D - 我们使用上述算法的主要原因是为了速度。我知道性能不是Andrey的优先考虑因素，所以可能并不相关。我也使用过FNV32，但更适用于像Nick D所提到的二进制数据哈希。虽然无法进行完全比较，但可以尝试两种方法，并查看哪一种具有更低的碰撞率。 - zebrabox
2
我注意到Perl的哈希算法使用MULTIPLIER=33，并在最后执行一个额外的步骤：h += (h >> 5)以改善低位比特的分布。 - Owen S.
2
该算法是http://www.cse.yorku.ca/~oz/hash.html上讨论的变体之一。不幸的是，它容易受到基本的哈希碰撞攻击（请参见[http://www.ocert.org/advisories/ocert-2011-003.html]），因为使用基于子字符串的（请参见引用的论文）碰撞计算非常简单；但如果从未与外部提供的密钥一起使用，则可能效果良好。 - StaxMan
26
如果性能不是很重要，只需使用安全哈希（例如MD5或SHA1），并将其输出截断为32位。这将给您一个与随机分布无法区分的哈希码分布。
3
MD4(参见http://tools.ietf.org/html/rfc1320)可能比MD5更好，因为其实现略微简单。请注意，MD4和MD5都不是不可区分于随机数的（两者都被“密码破解”），但它们对于手头的目的仍然足够接近。 - Thomas Pornin
2
@Thomas MD5在某种意义上是有问题的，因为你可以创建哈希冲突——两个明文产生相同的哈希值。这并不意味着MD5的输出可区分于随机性——没有反像攻击能够对抗MD5。哪种更容易实现也不太相关——他几乎肯定会在他所选择的编程语言中使用预先制作好的MD5或SHA1实现。 - Nick Johnson
3
@Nick: 对MD5的攻击基于差分路径。通过在一个MD5输入上应用输入差异，您有很小但高于随机概率的可能性可以找到预期输出的差异。这并不导致原像攻击，但它使MD5与随机预言机有所不同。在MD4的情况下，当用于HMAC时（其中碰撞本身不是问题），已经证明它可以被（学术上）利用。 - Thomas Pornin
@Thomas 我改口了。我不知道MD4甚至对于HMACs也是有漏洞的 - 这是一个有趣的结果！ - Nick Johnson
我已经测试了MD5、Sha1和普通的CRC32，它们几乎具有相同的碰撞率，都约为0.23%。因此，在这里，MD5和SHA1并没有做得更好。是否有比MD5和SHA1更好的哈希算法？ - Max
显示剩余3条评论
23

很抱歉对于此事回复非常晚。今年早些时候，我写了一篇标题为“散列短字符串的方法”的页面，可能会对这个讨论有所帮助。总之，我发现CRC-32和FNV-1a对于散列短字符串是优秀的选择。它们高效并且在我的测试中产生了广泛分布和无碰撞的哈希值。当输出折叠至32位时，我惊讶地发现MD5、SHA-1和SHA-3产生了少量碰撞。

CRC32仍然是最佳答案。 - aggsol
我也认为CRC32应该是排名最高的答案。 - Nikolay Dimitrov
1
实际上，与其他替代方案相比，CRC32分布非常糟糕。对于32位哈希值，即使是像乘积/旋转这样的朴素算法也可以为<8字节的字符串产生更好的分布，并且可能更快。说到这一点，xxHash正是如此，但其分布更好，并且专门针对现代处理器进行了优化（与CRC32非常不同）。对于哈希大量小字符串并具有较低冲突数（例如在词法分析时），DJB2可能是最佳选择。 - yyny
2
@yyny 上面发布的文章展示了DJB2算法，用于生成长度为2个字符的字符串2220个碰撞和长度为3个字符的字符串70164个碰撞。对于哈希大量小字符串来说，使用碰撞率更低的哈希函数，例如FNV-1a，是否更好呢？ - aganm
3
这取决于您的硬件。在现代硬件上，即具有SSE4.2或arm7的Intel / AMD上，应使用内部的_mm_crc32_uxx内嵌函数，因为它们对于短字符串是最优的。（对于长键也是如此，但是更好地使用Adler的线程版本，如zlib）
在旧硬件或未知硬件上，要么运行时探测SSE4.2或CRC32功能，要么只使用一个简单的好哈希函数。例如Murmur2或City
这里是质量和性能概述： https://github.com/rurban/smhasher#smhasher 还有所有实现。受欢迎的是https://github.com/rurban/smhasher/blob/master/crc32_hw.c和https://github.com/rurban/smhasher/blob/master/MurmurHash2.cpp 如果您事先知道密钥，请使用完美哈希而不是哈希函数。例如gperf或我的phash：https://github.com/rurban/Perfect-Hash#name 现在通过c编译器生成完美哈希非常快，甚至可以动态加载它们。
1
更新：Murmur2和City不再被称为简单好的哈希函数。 最快的是FNV1或CRC32-C，更好的是Metro或Farmhash。 - rurban
SpookyHash64仍然是我发现的所有哈希函数中具有最佳avalanching/最低碰撞率的，我强烈建议在罗宾汉哈希映射中使用它，除非你已经经验性地发现其他哈希函数更好/更快。对于小输入，我建议使用FNV1A或DJB2。SpookyHash的设置成本相当高，大约为30个周期。Metro/Farm/Murmur/City/xxHash/许多其他哈希函数非常适合快速、通用的哈希处理，设置时间较短，但碰撞率较高。当需要低碰撞率时，我不会使用它们。 - yyny
2

使用 MaPrime2c 哈希函数：

static const unsigned char sTable[256] =
{
  0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9,
  0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28,
  0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53,
  0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2,
  0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8,
  0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90,
  0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76,
  0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d,
  0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18,
  0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4,
  0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40,
  0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5,
  0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2,
  0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8,
  0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac,
  0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46
};


#define PRIME_MULT 1717


unsigned int
maPrime2cHash (unsigned char *str, unsigned int len)
{
  unsigned int hash = len, i;


  for (i = 0; i != len; i++, str++)
    {

      hash ^= sTable[( *str + i) & 255];
      hash = hash * PRIME_MULT;
    }

  return hash;
}

请访问www.amsoftware.narod.ru/algo2.html，了解MaFastPrime、MaRushPrime等测试相关信息。

1
你可以尝试使用murmurhash2。它速度快，即使对于小字符串也是如此，并且具有良好的混合最终步骤，因此即使对于非常小的字符串也是很好的混合。
0
#include <cstdint>
#include <string_view> // C++17

uint32_t short_string_hash(std::string_view str) {
    uint32_t hash = 0;
    const uint32_t num32 = static_cast<uint32_t>(str.length() / sizeof(uint32_t));
    constexpr uint32_t magic = 37;
    {
        const uint32_t *pU32 = reinterpret_cast<const uint32_t *>(str.data());
        for (uint32_t i = 0; i < num32; ++i) {
            hash = (magic * hash) + pU32[i];
        }
    }
    {
        str.remove_prefix(num32 * sizeof(uint32_t));
        for (const char c : str) {
            hash = (magic * hash) + c;
        }
    }
    return hash;
}

我对这个哈希算法进行了15280个独特的短字符串的测试，没有发现冲突。

注意：这基本上只是https://dev59.com/3HE95IYBdhLWcg3wWMdQ#2351171的批处理版本。将块分组为u32，然后处理剩余部分。

0
如果用户很少添加新标签，那么您可以使用完美哈希（http://en.wikipedia.org/wiki/Perfect_hash_function），每次添加新标签时重新计算。当然，如果不知道您真正想解决的问题，那么猜测您可能会做什么是没有意义的。
0
如果您的程序需要与其他系统通信，最好使用众所周知的算法。快速且简单的方法是使用md5哈希的前几个字符。您不需要花费数小时或数天在项目中发明轮子。
缺点是冲突的可能性非常高。但是，如果您的哈希用于时间戳会话或短期任务，则可以使用它而没有问题。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接