哈希函數將int的唯一數組映射到範圍爲0..n的索引

我需要將最大長度從1到4變化的排序整數數組映射到全局數組的索引。像[13,24,32]成爲範圍爲0..n的數字，並且沒有其他數組映射到相同的數字。數組的數量是幾百萬，並且映射必須是「唯一的」（或者對於較小的數組來說至少幾乎沒有碰撞），因爲這些數組代表項目集，我使用k-1較小的項目集來構建一個大小爲k。哈希函數將int的唯一數組映射到範圍爲0..n的索引

我目前的實現使用了一個高效的散列函數，它爲一個數組產生一個0..1之間的雙精度值，並且我將項目集存儲在STL Map中，其中double作爲鍵。從這篇文章有：

ND Atreas，C. KARANIKAS「基於素數和散列逼近更快的模式匹配算法」，2007年

我要實現的這CUDA並行版本，所以我不能使用像STL Map這樣的東西。我可以在GPU全局內存中輕鬆創建一個自我平衡的二叉搜索樹，但這確實很慢。所以爲了將全局內存訪問降到最低，我需要將項目集映射到全局內存中的一個巨大數組。

我試着將double作爲長整型進行轉換，並將其與64位散列函數一起散列，但它會產生一些碰撞，如預期的那樣。

於是，我問，如果有一個爲0..1之間雙打「獨一無二」的哈希函數，或從大小1..4整數數組，給出了大小爲N的表中的唯一索引

來源

2014-10-04 liwing

您正在尋找[最小完美散列函數]（http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function）。 – 2014-10-04 20:22:41

但是我不需要提供一個輸入來構建最小的哈希函數？我的數組會有所不同，它們是單個項目數組中的大小1到4的組合，這些數組也可能會有所不同。 – liwing 2014-10-04 21:15:11

恐怕我對它們的瞭解比名字更多。我希望爲數百萬個元素構建這樣一個功能非常耗時（也許不可能），儘管我可能是錯的。 – 2014-10-04 21:59:59

如果我讓這對您的陣列的假設：

each item of your arrays (such as 13) are 32-bit integers.

然後你問什麼是不可能的。

您至少有2 ^（32 * 4）個可能的值或128位。而你正試圖將這些打包成一個小得多的數組（20百萬條記錄）。你不能在沒有碰撞的情況下做到這一點（或者在元素之間存在一些協議，比如選擇「下一個可用索引」的每個元素，但這不是哈希）。

來源

2014-10-05 02:17:25 Ian

這些都是可能的值，但只有幾千萬。實際上，這些數組元素可以是一個簡短的整數，因爲這些值不會超過一萬個。我並不是在尋找一個完美的散列，因爲這需要從數據中輸入數據，但是像我提到的文章中的算法，它只在很多散列之後纔會產生衝突。對於我的測試數據，它的工作原理就像一個完美的哈希，因爲我用很多測試用例來測試它，並且沒有碰撞。問題是這個哈希值是雙倍的，我希望有人給我一個索引。 – liwing 2014-10-05 03:48:52

哈希函數將int的唯一數組映射到範圍爲0..n的索引

回答

相關問題