作为解决方案的基础,我想到了两件事:
求和不依赖于顺序,这实际上是简单校验和的一个缺陷(它们不会在一个单词中捕捉到块顺序的变化),并且
我们可以使用它们的字符码将字符串转换为可累加的数字
这是一个要做的功能 (2) :
charsum = function(s) {
var i, sum = 0;
for (i = 0; i < s.length; i++) {
sum += (s.charCodeAt(i) * (i+1));
}
return sum
}
这是 (1) 的一个版本,它通过对 charsum 值求和来计算数组哈希:
array_hash = function(a) {
var i, sum = 0
for (i = 0; i < a.length; i++) {
var cs = charsum(a[i])
sum = sum + (65027 / cs)
}
return ("" + sum).slice(0,16)
}
在这里小提琴:http: //jsfiddle.net/WS9dC/11/
如果我们对 charsum 值进行直接求和,那么数组 ["a", "d"] 将具有与数组 ["b", "c"] 相同的散列 - 导致不希望的冲突。因此,基于使用非 UTF 字符串,其中 charcode 最多为 255,并且每个字符串中允许 255 个字符,那么 charsum 的最大返回值为 255 * 255 = 65025。所以我选择了下一个素数,65027,并使用 (65027 / cs) 来计算哈希。我不是 100% 相信这会消除冲突......也许需要更多的思考......但它确实解决了 [a, d] 与 [b, c] 的情况。测试:
var arr1 = ['alpha','beta','gama'];
var arr2 = ['beta','alpha','gama'];
console.log(array_hash(arr1))
console.log(array_hash(arr2))
console.log(array_hash(arr1) == array_hash(arr2))
输出:
443.5322979371356
443.5322979371356
true
并测试一个显示不同哈希的案例:
var arr3 = ['a', 'd'];
var arr4 = ['b', 'c'];
console.log(array_hash(arr3))
console.log(array_hash(arr4))
console.log(array_hash(arr3) == array_hash(arr4))
输出:
1320.651443298969
1320.3792001649144
false
编辑:
这是一个修改后的版本,它忽略了数组中的重复项,并仅返回基于唯一项的哈希:
http://jsfiddle.net/WS9dC/7/
array_hash = function(a) {
var i, sum = 0, product = 1
for (i = 0; i < a.length; i++) {
var cs = charsum(a[i])
if (product % cs > 0) {
product = product * cs
sum = sum + (65027 / cs)
}
}
return ("" + sum).slice(0, 16)
}
测试:
var arr1 = ['alpha', 'beta', 'gama', 'delta', 'theta', 'alpha', 'gama'];
var arr2 = ["beta", "gama", "alpha", "theta", "delta", "beta"];
console.log(array_hash(arr1))
console.log(array_hash(arr2))
console.log(array_hash(arr1) === array_hash(arr2))
返回:
689.878503111701
689.878503111701
true
编辑
我已经修改了上面的答案,以解释具有相同字母的单词数组。我们需要这些来返回不同的哈希值,他们现在这样做:
var arr1 = ['alpha', 'beta']
var arr2 = ['alhpa', 'ateb']
解决方法是根据 char 索引向 charsum 函数添加一个乘数:
sum += (s.charCodeAt(i) * (i+1));