什么整数散列函数是好的,接受整数散列键？

什么整数散列函数是好的,接受整数散列键？

1> Thomas Muell..：

---

我发现以下算法提供了非常好的统计分布.每个输入位以大约50%的概率影响每个输出位.没有碰撞(每个输入产生不同的输出).除非CPU没有内置的整数乘法单元,否则算法很快.C代码,假设int为32位(对于Java,替换>>为>>>和删除unsigned):

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

幻数是使用一个运行了几个小时的特殊多线程测试程序计算出来的,该程序计算雪崩效应(如果单个输入位发生变化,输出位数会发生变化;平均应该接近16),独立性输出位发生变化(输出位不应相互依赖),以及每个输出位发生变化的概率(如果有任何输入位发生变化).计算值优于MurmurHash使用的32位终结器,并且几乎与使用AES时一样好(不完全).一个小优点是两次使用相同的常数(它确实使我上次测试时的速度略快,不确定是否仍然如此).

如果替换0x45d9f3bwith 0x119de1f3(乘法逆),则可以反转该过程(从散列中获取输入值):

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

对于64位数字,我建议使用以下内容,即使它可能不是最快的.这个基于splitmix64,它似乎基于博客文章Better Bit Mixing(mix 13).

uint64_t hash(uint64_t x) {
    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
}

对于Java,使用long,添加L到恒,更换>>与>>>和删除unsigned.在这种情况下,倒车更复杂:

uint64_t unhash(uint64_t x) {
    x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
    x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
    x = x ^ (x >> 30) ^ (x >> 60);
    return x;
}

更新:您可能还想查看Hash Function Prospector项目,其中列出了其他(可能更好的)常量.

---

不,这不是一个错字,第二行进一步混合位.仅使用一次乘法就不那么好了.

---

我更改了幻数,因为根据我编写的[测试用例](http://code.google.com/p/h2database/source/browse/trunk/h2/src/test/org/h2/test/store/ CalculateHashConstant.java)值0x45d9f3b提供更好的[混淆和扩散](http://en.wikipedia.org/wiki/Confusion_and_diffusion),特别是如果一个输出位发生变化,则每个其他输出位的变化概率大致相同(在如果输入位改变,则对所有输出位的加法以相同的概率改变).你是如何衡量0x3335b369对你有用的？你是一个int 32位吗？

---

我正在寻找一个很好的哈希函数64位无符号int到32位unsigned int.对于那种情况,上面的幻数会是一样的吗？我移动了32位而不是16位.

---

我相信在这种情况下,一个更大的因素会更好,但你需要进行一些测试.或者(这是我做的)首先使用`x =((x >> 32)^ x)`然后使用上面的32位乘法.我不确定什么更好.您可能还想查看[Murmur3的64位终结器](http://code.google.com/p/smhasher/wiki/MurmurHash3)

---

前两行完全一样!这里有错字吗？

---

@RocketRoy如果你之后使用modulo,当然在某些时候会有碰撞.关键不是要避免碰撞,而是要使它们不太可能.你可能获得的最好的概率与真正的随机数相同(不是伪随机数,而是真随机数),但这是不可行的.第二好的是与加密安全随机数发生器(例如AES或SHA-3)相同的概率,但这很慢.上面的算法很快但在概率方面接近AES.

---

@SantoshGhimire是的，在这种情况下可以反转操作，因为没有碰撞。您只需要在公式（倒数）中将“ 0x45d9f3b”替换为“ 0x119de1f3”即可。

---

@SantoshGhimire,关键的警告是没有碰撞,否则两个(或更多)不同的值由相同的键表示,其中一个必须是不可逆的.除非内存非常重要,特别是如果是CPU,你不会想要这样做.由于哈希是CPU密集型的,因此最好查找它.散列函数执行范围缩减,最好将其视为有损压缩.请谨慎使用逆转.

---

@SantoshGhimire它适用于我,请参阅http://codepad.org/WwSVNRnX上的示例代码

2> Rafał Dowgir..：

---

Knuth的乘法方法:

hash(i)=i*2654435761 mod 2^32

通常,您应该选择一个乘以您的散列大小(2^32在示例中)的乘数,并且没有与之相关的公因子.这样,哈希函数统一覆盖了所有哈希空间.

编辑:这个哈希函数的最大缺点是它保留了可分性,所以如果你的整数都可以被2或4整除(这并不罕见),它们的哈希也是如此.这是哈希表中的一个问题 - 您最终只能使用1/2或1/4的桶.

---

这是一个非常糟糕的哈希函数,虽然附有一个着名的名字.

---

对于好奇,这个常量被选择为散列大小(2 ^ 32)除以Phi

---

仔细观察,事实证明2654435761实际上是一个素数.所以这可能是为什么它被选中而不是2654435769.

---

Paolo:Knuth的方法是"糟糕的",因为它不会在高位上雪崩

---

如果与主表大小一起使用,它根本不是一个糟糕的哈希函数.此外,它适用于_closed_散列.如果散列值不是均匀分布的,则乘法散列可确保来自一个值的冲突不太可能"干扰"具有其他散列值的项目.

---

值得注意的是,此函数具有非常差的雪崩属性(它以非均匀的方式传播值),因此在用于示例哈希表时可能会导致聚类

---

答案没有提到必须使用哈希值的“高位”以获得良好的性能（表大小为2的幂的右移）。使用`hash（i）％table_size`会导致大量的冲突。

3> erikkallen..：

---

取决于您的数据如何分布.对于一个简单的计数器,最简单的功能

f(i) = i

会很好(我怀疑是最佳的,但我无法证明).

---

@Rafal:这就是为什么响应说"对于一个简单的计数器"和"取决于你的数据如何分配"

---

由于其分布属性(或缺乏属性),身份函数在许多实际应用中作为哈希是相当无用的,除非当然,局部性是所需的属性

---

这实际上是Sun在java.lang.Integer中实现方法hashCode()http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/lang/ Integer.java#Integer.hashCode%28%29

---

@JuandeCarrion这是误导,因为这不是正在使用的哈希.在转换为使用两种表大小的功能之后,Java重新使用`.hashCode()`返回的每个哈希,请参阅[here](http://grepcode.com/file/repository.grepcode.com/java/root/jdk /openjdk/6-b14/java/util/HashMap.java#HashMap.hash%28int%29).

---

这样做的问题在于,通常有大的整数集可以被公共因子整除(字对齐的存储器地址等).现在,如果您的哈希表碰巧可以被相同的因子整除,那么最终只使用了一半(或1/4,1/8等)桶.

4> Tyler McHenr..：

---

这个页面列出了一些简单的散列函数,这些散列函数通常都很合适,但是任何简单的散列都有病态的情况,它不能正常工作.

5> bill..：

---

32位乘法方法(非常快)请参阅@rafal

#define hash32(x) ((x)*2654435761)
#define H_BITS 24 // Hashtable size
#define H_SHIFT (32-H_BITS)
unsigned hashtab[1<> H_SHIFT

位于:MurmurHash的 32位和64位(良好分布)

整数散列函数