将整数映射到给定范围的散列函数？
将整数映射到给定范围的散列函数？
提问于 2013-01-17 03:09:42
我有一组整数，每个整数都有8,9或10位数字。我有上百万个。我希望将它们中的每一个映射到1到1000范围内的整数。我不能对整数进行简单的mod，因为这些数字的发布方式存在系统性偏差(例如，偶数比奇数更有可能)，因此
$id % 1000会产生更频繁的偶数和更少的奇数。提前谢谢你。
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-01-17 03:46:51
您实际上是在请求一个将数字映射到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 827Stack Overflow用户
发布于 2013-01-17 04:05:58
除非你能定义可用数字的数学属性(例如，它们是偶数、指数分布等)，否则任何确定性函数都不可能将这些数字均匀地映射到任何给定的范围内。
您选择的每个函数都必须将特定类别的数字映射到输出范围内的一个小区域。如果散列函数很复杂，可能很难先验地确定将被错误处理的类。当然，这是散列函数的一个普遍问题。你总是需要在输入上做一些假设。
从理论上讲，惟一的解决方案(如果您对数字一无所知或无法分析它们)是将输入的数字与真正的随机序列进行xor，然后使用mod操作。
在实践中，Josh的解决方案可能会奏效。
注意:如果您可以在对数字进行散列时分析结果数组，则可以更改散列函数以均匀分布结果。这可能适用于创建哈希表以供以后搜索。但是，这似乎不是您的应用程序。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14365911
复制相关文章
相似问题
腾讯云开发者
