指针值的散列值

有时您需要采用指针的散列函数;不是指针指向的对象，而是指针本身。很多时候，人们只是将指针值作为一个整数来使用，切掉一些高位以使其适合，也许在底部移出已知的零位。事情是，指针值在代码空间中不一定是很好的分布;事实上，如果你的分配器正在完成它的工作，那么他们很可能会聚集在一起。指针值的散列值

所以，我的问题是，有没有人开发了这个好的散列函数？取一个32位或64位的值，可能会得到12位熵，并将其平均分布在32位数字空间中。

来源

2010-08-09 zwol

的可能重复[什么整数散列函数是好的，接受一个整数哈希键？]（http://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-一个整数散列键） – 2010-08-09 17:56:11

This page列出了几种方法，可能是有用的。由于Knuth的原因，其中之一是2654435761乘以（32位）的简单方法，但如果按键的高位不同，则会产生“坏散列结果”。在指针的情况下，这是一个非常罕见的情况。

Here是一些算法，包括性能测试。

看来，这些魔法字是“整数哈希”。

来源

2010-08-09 17:47:29 Thomas

而当你搜索“整数散列”，你会得到另一个SO页面，这个页面有效地复制。 :-) – 2010-08-09 17:56:57

谢谢。我没有想到要搜索“整数哈希”，因为我被卡在值指针*上，但这些页面看起来非常有帮助。 – zwol 2010-08-09 18:08:47

但在32位系统的地址的高位可以很好地使用... – 2010-08-10 18:20:22

为什么不直接使用现有的hash function？

来源

2010-08-09 17:50:25 DShook

我怀疑他们的动机是速度。 – 2010-08-09 17:54:33

他们很可能会呈现出局部性，是的 - 但在低位，这意味着对象将通过哈希表分发。如果指针的地址是另一个指针的哈希表长度的倍数，那么只会看到冲突。

来源

2010-08-09 20:06:50

这不是我的直觉。我希望堆中的典型（32位）指针的形式为'CCCC XXX8'（十六进制） - 高半常数或几乎如此，*低半部分可能是* 12位熵，最低低几率再一次。而下半部分可能会剔出一个数字，并且在其主因子分解中有很多两个数字。 – zwol 2010-08-09 20:13:32

您已经提到将低位移出。如果这就是熵的所有位，那么散列的数量也不会增加。 – 2010-08-10 09:48:17

如果你知道的尽可能低的指针地址（这是常有的事，如果你是一个大的缓冲区内工作），只是指针转换减去最低的指针值的整数;例如。这可能是缓冲区的基址。 - 记住：从指针减去的指针等于偏移量（整数）。所以：不要“切掉”位;转换为偏移量会更好。这将导致偏移值远小于指针值。在某些情况下，它可能有助于进一步将指针值右移两次（例如除以4），然后再对其进行哈希处理。指针的问题通常是小块内存可能分配在相同的地址上（例如，一个块被释放，另一个块正在释放该块的位置）。

来源

2014-11-02 22:49:01

指针值的散列值

回答

相关问题