大多数应用程序，尤其是数据库，可以按小整数或浮点数进行排序和过滤，速度比字符串比较快得多。
因此，我想知道是否有一个散列函数可以用来返回一个 32 位或 64 位的短字符串（大约 5 - 40 个字符），以便我可以通过整数而不是字符串进行比较。
我首先想到了 crc32，但它似乎太小了，可能会导致少于 50,000 个哈希值的冲突（我需要做超过一百万个）。
我最感兴趣的是使用 Python、PHP、V8 Javascript、PostgreSQL 和 MySQL。
问问题
456 次
1 回答
2
在所有 32 位散列中都存在在 50k 条目时可能发生冲突的问题。如果你读了一些关于生日问题的文章，你会发现如果你有周围的sqrt(HashSpace)元素，比如sqrt(2^32) = 64k32 位散列，冲突就很可能发生。
使用 64 位哈希，冲突变得更加罕见。但是我仍然不太愿意将我的程序的正确性押在上面。
使用维基百科的近似值：
我们得到 100 万个元素的概率为 3*10 -8，1000万个元素的概率为 3*10-6。
您可以为此使用 CRC64。或者只是将加密哈希（例如 md5 或 sha1）截断为所需的长度。
如果恶意人员可以选择字符串，通过故意创建冲突来破坏您的程序，那么您至少应该切换到键控哈希，例如 HMAC。
根据您所做的事情，您还可以简单地在 string 和 int 之间创建一个内存映射，您只需为遇到的每个元素增加一个计数器。这为您提供了完美的映射，没有碰撞风险，但仅适用于某些场景。
于 2012-03-16T20:20:55.467 回答