用於將整數映射到給定範圍的哈希函數？

我有一組整數，每個都有8,9或10位數字的大小。我有數以百萬計。我想把它們中的每一個映射到1到1000範圍內的一個整數。我不能對整數做一個簡單的mod，因爲這些數字發出的方式存在系統偏差（例如，偶數比奇數），所以用於將整數映射到給定範圍的哈希函數？

$id % 1000

會產生更頻繁的偶數和更少的頻率奇數。是否有任何簡單的函數（無論是數學函數還是棘手的函數都可以進行按位運算），這些函數可以幫助我在Perl或R中進行映射？非常感謝。

來源

2013-01-16 broccoli

只使用該範圍內的隨機生成器就足夠了嗎？ – squiguy

在執行模運算之前將它們乘以奇數（最好是素數）？ – wildplasser

如果我使用隨機數字發生器，我需要存儲映射。如果它是一個可計算的功能，那麼就沒有存儲需求。 @wildplasser爲什麼這個方法有效？我的意思是如果乘數是素數，它是否保證隨機性？ – broccoli

你基本上要求的散列函數映射到數字值在0到999之間，並

要構建的是，你可以先用哈希函數映射到擺脫任何系統性的模式值，然後用MOD限制在0和999

這裏的輸出值的的R實現這種想法的：

library(digest) 
set.seed(1) 

(x <- sample(1e9, size=6)) 
# [1] 265508664 372123900 572853364 908207790 201681932 898389685 

## To hash R's internal representation of these numbers 
strtoi(substr(sapply(x, digest), 28, 32), 16L) %% 1e3 
# [1] 552 511 233 293 607 819 

## Or, for a hash mapping that's comparable to other programs' md5 hash 
## implementations 
strtoi(substr(sapply(as.character(x), digest, serialize=FALSE),28,32),16L) %% 1e3 
# [1] 153 180 892 294 267 807

打破了一個班輪下來成片應做什麼它做了位更清晰：

## Compute md5 hash of R representation of each input number 
(sapply(x, digest)) 
# [1] "a276b4d73a46e5a827ccc1ad970dc780" "328dd60879c478d49ee9f3488d71a0af" 
# [3] "e312c7f09be7f2e8391bee2b85f77c11" "e4ac99a3f0a904b385bfdcd45aca93e5" 
# [5] "470d800a40ad5bc34abf2bac4ce88f37" "0008f4edeebbafcc995f7de0d5c0e5cb" 

## Only really need the last few hex digits 
substr(sapply(x, digest), 28, 32) 
# [1] "dc780" "1a0af" "77c11" "a93e5" "88f37" "0e5cb" 

## Convert hex strings to decimal integers 
strtoi(substr(sapply(x, digest), 28, 32), 16L) 
# [1] 903040 106671 490513 693221 560951 58827 

## Map those to range between 0 and 999 
strtoi(substr(sapply(x, digest), 28, 32), 16L) %% 1e3 
# [1] 40 671 513 221 951 827

來源

2013-01-16 19:46:50

這個解決方案很好。投票（不知道誰投了票） – broccoli

喜歡這個解決方案，但有沒有辦法獲得沒有額外的軟件包R中的字符串的數字表示？ – Qbik

除非你能定義可用號碼的數學特性（例如，他們甚至，指數分佈或其他）有沒有辦法，任何確定性函數將這些數字映射到任何給定的範圍均勻。

您選擇的每個函數都必須將某個類別的數字映射到輸出範圍內的一個小區域。如果散列函數複雜，則可能難以確定將被錯誤處理的類。當然，這是散列函數的一個普遍問題。你總是不得不在輸入上假設一些東西。

理論上，唯一的解決方案（如果您不知道數字或無法分析它們）是以真正的隨機序列對輸入數字進行異或運算，然後使用mod操作。

實際上，喬希的解決方案可能會奏效。

注意：如果您可以在散列數字時分析結果數組，則可以更改散列函數以均勻分佈結果。這可能適用於創建一個散列表供以後搜索。但是，這似乎不是你的應用程序。

來源

2013-01-16 20:05:57 nimrodm

你在決定論方面是正確的 – broccoli

用於將整數映射到給定範圍的哈希函數？

回答

相關問題