对未知输入具有良好均匀性的散列函数

我正在寻找一个散列函数，它将一大组输入数据以良好的均匀性分区到少数分区（比如说100或 256）。这意味着我期望有很多碰撞，我不关心碰撞。对未知输入具有良好均匀性的散列函数

输入数据未预先知道。我预计长度为的字符串可能在6到100个字节之间。这些字符串可能分布不均匀（例如大部分填充空格或仅包含数字）。

CRC算法是首先想到的想法之一。 CRC8已经提出，但没有提供有关其统一性的信息;对于CRC32显然是uniformity is not that good。

有一系列simple或general purpose散列函数，但没有告诉它们的一致性。

Bob Jenkins在散列函数上有一个完整的article，该散列函数返回一个 32位值。我想对于均匀分布的32位值也应该均匀分布所有可能的8位子集，所以是很好的候选者。但是，如果8位的算法比较简单，那么将32位值减小为8位值可能会矫枉过正？

来源

2011-12-20 pesche

伯恩斯坦的哈希至极是詹金斯的页面上也一点也不坏，这是死的简单。当需要“只是一些散列”时，我正在使用它。没有任何问题。如果你担心它不是“足够随机”的，你甚至可以将添加剂和异或变量合并成一个，这通常会流水到相同的循环次数。请注意，CRC的设计原理主要不是为了产生散布良好的散列，而是为了检测意外的位翻转。 – Damon 2011-12-20 13:09:54

在使用本机寄存器大小（32位）进行计算时不会有任何惩罚，大多数操作都是在（符号）操作数扩展到本地int大小之后执行的。截断（或取模）将是便宜的（但不是免费的）。并非所有散列函数在最右边的位都有足够的熵。 – wildplasser 2011-12-26 14:53:29

我发现SDBM算法表现出良好的均匀度，是相当简单：

 h := 0. 
     forEach ch in str { 
      h := (h * 65599) + ch; 
     }

来源

2011-12-26 12:28:03 blabla999

对未知输入具有良好均匀性的散列函数

回答

相关问题