javascript - 在javascript中散列字符串数组

Question

只是想知道是否还有其他方法。

var hashStringArray = function(array) {
    array.sort();
    return array.join('|');
};

我不太喜欢排序，如果分隔符包含在其中一个字符串中，则使用该分隔符也不安全。总的来说，无论字符串的顺序如何，我都需要生成相同的散列。这将是相当短的数组(最多 10 个项目)，但会经常需要它，所以它不应该太慢。

我打算将它与 ES6 Map 对象一起使用，我需要轻松找到相同的数组集合。

更新的使用示例

var theMap = new Map();
var lookup = function(arr) {
    var item = null;
    var hashed = hashStringArray(arr);
    if (item = theMap.get( hashed )) {
        return item;
    }
    theMap.set( hashed, itemBasedOnInput );
    return itemBasedOnInput;
}

var arr1 = ['alpha','beta','gama'];
var arr2 = ['beta','alpha','gama'];

lookup(arr1) === lookup(arr2)

性能测试

http://jsperf.com/hashing-array-of-strings/5

Answer 1

作为解决方案的基础，我想到了两件事:

1. 求和不依赖于顺序，这实际上是简单校验和的一个缺陷(它们不会捕获单词内 block 顺序的变化)，并且

2. 我们可以使用字符代码将字符串转换为可求和的数字

这是要执行 (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)
}

在这里 fiddle :http://jsfiddle.net/WS9dC/11/

如果我们对 charsum 值进行直接求和，那么数组 ["a", "d"] 将具有与数组 ["b", "c"] 相同的散列 - 导致意外的冲突。因此，基于使用非 UTF 字符串，其中 charcodes 最多为 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));