指針值的散列值

有時您需要採用指針的散列函數;不是指針指向的對象，而是指針本身。很多時候，人們只是將指針值作爲一個整數來使用，切掉一些高位以使其適合，也許在底部移出已知的零位。事情是，指針值在代碼空間中不一定是很好的分佈;事實上，如果你的分配器正在完成它的工作，那麼他們很可能會聚集在一起。指針值的散列值

所以，我的問題是，有沒有人開發了這個好的散列函數？取一個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

指針值的散列值

回答

相關問題