algorithm - 将域中的一组整数散列到一组桶中
问题描述
假设我有一组介于 1-100 之间的整数。我只会从帽子中提取出其中的 5 个整数。然后,我想将这 5 个整数放入 5 个保证唯一的桶中(无需重复数据删除或任何使用二次探测之类的东西)。想知道如何做到这一点。
例如,假设我有这些数字(从 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
想知道如何编写散列函数,以便它x
从一个数字域中获取一个数字,D
并从该域中获取一组数字,并从一组 buckets 中D(X)
输出 1个 bucket 。b
B
H : D(X) -> B
下一次我可能有 6 个介于 1 和 1,000 之间的数字,进入 6 个桶。那么我需要一个使用这些约束(6 个数字,6 个桶,范围 1-1,000)工作的新哈希函数。
目标是尽可能少的步骤。
注意:这个例子的散列函数不会接受大于 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 ]
1
以某种方式“散列”到slot2
大小为 5 的数组中的位置(该插槽对于此示例是任意的)等。
解决方案
假设您的整数值的域是从 0 到 n-1 的范围,并且您希望值集 [x 0 , x 1 , ..., x k-1 ] 映射到从 0 到 k-1 的值.
创建一个 n 值数组,其中包含从 0 到 k-1 的大致相等数量的数字,例如 [a 0 = 0, a 1 = 1, ..., a k = 0, ..., a n = n %k]。
然后对于初始集合中的每个 k 值(x i,其中 i = 0 .. k-1),通过直接赋值或与其他地方的值交换,将此数组的第 k 个元素更改为 i (注意不要破坏初始集合的前一个元素的值集)。
然后散列一个值 y,只需从这个数组中获取第 y 个值。
演示
这是一个基本实现上述算法的 Javascript 演示,不同之处在于它不是用从 0 到 k-1 的值预先填充数组,而是首先插入所选项目的哈希值,然后用重复序列填充剩余的项目从 0 到 k-1 的数字。通过使用随机序列而不是递增值,您可能会获得更好的抗碰撞性,但我希望您能明白这一点。
var hash_array;
function generate_hash() {
var i, j, k;
var v = document.getElementById;
var n = document.getElementById("n").value;
// Create a new hash lookup table
hash_array = Array(n);
// Initialize every value to -1
for (i=0; i<n; i++) hash_array[i] = -1;
// Map the given values to the first k hash buckets
var initial_values = document.getElementById("init").value.split(/ +/);
k = initial_values.length;
for (i=0; i<k; i++) {
hash_array[initial_values[i]] = i;
}
// Fill the remaining buckets with values from 0 to k-1
// This could be done by selecting values randomly, but
// here we're just cycling through the values from 0 to k-1
for (i=j=0; i<hash_array.length; i++) {
if (hash_array[i] == -1) {
hash_array[i] = j;
j = (j + 1) % k;
}
}
document.getElementById("gen").innerHTML = "Hash lookup table:<br>" + hash_array.join(", ");
}
<h2>Demo</h2>
<p>Creating a hash function that works on integer values less than <i>n</i>. What is the value of <i>n</i>?<br>
<input type="number" id="n" min="6" max="100" value="20"/></p>
<p>Enter a few different values separated by spaces. These will hash to the first buckets<br/>
<input type="text" size="40" id="init" value="2 3 5 6 9"/></p>
<p id="gen"><button onclick="generate_hash(); return false">Generate hash table</button></p>
推荐阅读
- angular - Angular 单元测试很烦人:不要在构建/编译时发现问题
- python - 如何查找和使用我导入的模块?
- fortran - Fortran 可分配数组的低性能
- python - BeautifulSoup:如何保持 HTML 实体,&qout;
- javascript - “TypeError:无法读取未定义的属性”
- sql - 使用 LAG 更新 SQL
- python - 在 pygame 上应用三角函数和极坐标
- reactjs - 如何在 WordPress Api 上编辑用户信息
- angular - 从 Ionic/Angular 是否可以获得对底层 Stencil Web 组件的引用?
- xml - Rust serde 如何反序列化 xml “奇怪”列表?