假设我有一组整数,范围在1到100之间。我只会从中抽出其中的5个整数。然后我想将这5个整数放入5个桶中,保证唯一性(无需使用类似quadratic probing之类的去重方法)。请问如何实现。
例如,我有以下数字(从1-100中随机选择):
使用一些哈希函数来完成它。例如,可能像这样:
下一次我可能会有6个数字,范围在1到1000之间,分成6个桶。那么我需要一个新的哈希函数来使用这些约束条件(6个数字,6个桶,范围为1-1000)。
目标是尽可能少的步骤。
注意:此示例的哈希函数不会接受大于10,000的整数域,以及整数集大小也限制在像1,000这样的小数字。
但我不知道如何动态构建哈希函数。
一种解决方案(使用JavaScript)是创建一个类似于这样的映射表:
但这有点作弊,因为JavaScript中的对象在底层实现为哈希表(或类似的结构)。因此,我正在寻找如何在低级别上使用基本上只提供给你的汇编语言来完成这个任务。
基本上,我想做到这一点:
在大小为5的数组中,“1”以某种方式被“散列”,进入那个“slot2”(对于这个示例,该槽是任意的),等等。
例如,我有以下数字(从1-100中随机选择):
1 5 20 50 100
我希望将这些数字放入以下的5个桶中:
a b c d e
使用一些哈希函数来完成它。例如,可能像这样:
hash(1) -> b
hash(5) -> a
hash(20) -> e
hash(50) -> d
hash(100) -> c
想知道如何编写哈希函数,以便它从数字域 D
中获取数字 x
和该域中的一组数字 D(X)
,并从桶集合 B
中输出1个桶 b
。
H : D(X) -> B
下一次我可能会有6个数字,范围在1到1000之间,分成6个桶。那么我需要一个新的哈希函数来使用这些约束条件(6个数字,6个桶,范围为1-1000)。
目标是尽可能少的步骤。
注意:此示例的哈希函数不会接受大于10,000的整数域,以及整数集大小也限制在像1,000这样的小数字。
更新
我正在尝试实现以下目标:
// var domain = [1, 2, ..., 100]
// var set = [1, 5, 20, 50, 100]
// var buckets = [1, 2, 3, 4, 5]
hash(1) // 2
hash(5) // 1
hash(20) // 5
hash(50) // 4
hash(100) // 3
function hash(integer) {
if (integer == 1) return 2
if (integer == 5) return 1
if (integer == 20) return 5
if (integer == 50) return 4
if (integer == 100) return 3
}
但我不知道如何动态构建哈希函数。
一种解决方案(使用JavaScript)是创建一个类似于这样的映射表:
var map = {
1: 2,
5: 1,
20: 5,
50: 4,
100: 3
}
但这有点作弊,因为JavaScript中的对象在底层实现为哈希表(或类似的结构)。因此,我正在寻找如何在低级别上使用基本上只提供给你的汇编语言来完成这个任务。
基本上,我想做到这一点:
1
5 |
| | 20
| | 50 |
| | 100 | |
[ slot1, slot2, slot3, slot4, slot5 ]
在大小为5的数组中,“1”以某种方式被“散列”,进入那个“slot2”(对于这个示例,该槽是任意的),等等。