JavaScript中字符串数组的哈希化

Question

JavaScript中字符串数组的哈希化

4

我在想是否有其他方法可以实现这个目标。

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

（注：此处为链接，无法翻译）

- FredyC

JSON.stringify可能是一个选项，比join更好，但我仍然需要进行排序。我怀疑那是无法避免的。 - FredyC

2

@FredyC 你能否举个例子，说明分隔符会成为问题的情况？ - thefourtheye

2

另一方面，您可以使用 arr.join("\0")，似乎没有人会在字符串中放置空字符... - Bart

3

如果您使用 | 作为分隔符，这两个数组将产生相同的哈希值：["abc", "def|ghi"] 和 ["abc","def","ghi"]。 - Barmar

1

此外，不能保证 MD5 是唯一的，尽管碰撞是不太可能的。 - Barmar

显示剩余14条评论

4个回答

1

如果你为每个字符串计算一个数值哈希码，然后使用一个运算符将它们组合起来，其中顺序不重要，例如异或（^）运算符，那么你就不需要对数组进行排序。

function hashStringArray(array) {
  var code = 0;
  for (var i = 0; i < array.length; i++) {
    var n = 0;
    for (var j = 0; j < array[i].length; j++) {
      n = n * 251 ^ array[i].charCodeAt(j);
    }
    code ^= n;
  }
  return code
};

- Guffa

@sifriday 我希望在运行之前过滤掉重复项。我不认为有避免这种情况的方法。 - FredyC

无论如何，我试着进行基准测试。坦率地说，我很惊讶，因为@Guffa的解决方案真的快得多... http://jsperf.com/hashing-array-of-strings - FredyC

我刚刚发布了一个建议，使用简单的求和而不是异或，并尝试使用质数来减少碰撞。这对于重复数据没问题 - 我想 - 允许数组条目每个有255个字符... - sifriday

在 n = n * 251 ^ array[i].charCodeAt(j); -> n = (n * 251) ^ array[i].charCodeAt(j); 中，n * 251 的目的是什么？ - tonix

另外，为什么要使用XOR而不是其他可交换的位运算符，比如OR？ - tonix

显示剩余4条评论

0

你可以这样做：

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

\u200b 字符是一个 Unicode 字符，也表示 null，但它与最广泛使用的 \0 字符不同。

'\u200b' == '\0'

> false

- Marco Bonelli

0

如果您的字符串集合长度小于32个项目，那么一种非常快速的哈希方法是：使用内置哈希函数对字符串进行哈希，并返回二次幂作为哈希值。

function getStringHash(aString) {
   var currentPO2 = 0;
   var hashSet = [];
   getStringHash = function ( aString) {
       var aHash = hashSet[aString];
       if (aHash) return aHash;
       aHash = 1 << currentPO2++;
       hashSet[aString] = aHash; 
       return aHash;
   }
   return getStringHash(aString);
}

然后在你的字符串数组上使用这个哈希值，将哈希值进行按位或操作（|）：

function getStringArrayHash( aStringArray) {
    var aHash = 0;
    for (var i=0; i<aStringArray.length; i++) {
        aHash |= getStringHash(aStringArray[i]);
    }
    return aHash;
}

所以为了进行一些测试：

console.log(getStringHash('alpha'));  // 1
console.log(getStringHash('beta'));   // 2
console.log(getStringHash('gamma'));  // 4
console.log(getStringHash('alpha'));  // 1 again

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

console.log(getStringArrayHash(arr1)); // 11
console.log(getStringArrayHash(arr2)); // 11 also, like for arr1

var arr3 = ['alpha', 'teta'];
console.log(getStringArrayHash(arr3)); // 17 : a different array has != hashset

jsbin在这里：http://jsbin.com/rozanufa/1/edit?js,console

RQ !!! 这种方法中，数组被视为集合，这意味着重复的项不会改变数组的哈希值!!!

这一定会更快，因为它仅使用1）函数调用2）查找3）整数算术。所以没有排序，没有（长）字符串，没有连接。

jsperf证实了这一点： http://jsperf.com/hashing-array-of-strings/4

enter image description here

编辑：

带有质数的版本，请参见：http://jsbin.com/rozanufa/3/edit?js,console

        // return the unique prime associated with the string.
    function getPrimeStringHash(aString) {
       var hashSet = [];
       var currentPrimeIndex = 0;
       var primes = [ 2, 3, 5, 7, 11, 13, 17 ];
       getPrimeStringHash = function ( aString) {
           var aPrime = hashSet[aString];
           if (aPrime) return aPrime;
           if (currentPrimeIndex == primes.length) aPrime = getNextPrime();
           else aPrime = primes[currentPrimeIndex]; 
           currentPrimeIndex++
           hashSet[aString] = aPrime; 
           return aPrime;
       };
       return getPrimeStringHash(aString);
       // compute next prime number, store it and returns it.
       function getNextPrime() {
         var pr = primes[primes.length-1];
         do {
             pr+=2;
             var divides = false;
             // discard the number if it divides by one earlier prime.
             for (var i=0; i<primes.length; i++) {
                 if ( ( pr % primes[i] ) == 0 ) {
                     divides = true;
                     break;
                 }
             }
          } while (divides == true)
          primes.push(pr);
         return pr;
        }
    }

    function getStringPrimeArrayHash( aStringArray) {
        var primeMul = 1;
        for (var i=0; i<aStringArray.length; i++) {
            primeMul *= getPrimeStringHash(aStringArray[i]);
        }
        return primeMul;
    }

    function compareByPrimeHash( aStringArray, anotherStringArray)  {
        var mul1 = getStringPrimeArrayHash ( aStringArray ) ;
        var mul2 = getStringPrimeArrayHash ( anotherStringArray ) ;
        return  ( mul1 > mul2 ) ? 
                                   ! ( mul1 % mul2 ) 
                                 : ! ( mul2 % mul1 );
      // Rq : just test for mul1 == mul2 if you are sure there's no duplicates
    }

测试：

console.log(getPrimeStringHash('alpha'));  // 2
console.log(getPrimeStringHash('beta'));   // 3
console.log(getPrimeStringHash('gamma'));  // 5
console.log(getPrimeStringHash('alpha'));  // 2 again
console.log(getPrimeStringHash('a1'));  // 7 
console.log(getPrimeStringHash('a2'));  // 11


var arr1 = ['alpha','beta','gamma'];
var arr2 = ['beta','alpha','gamma'];
var arr3 = ['alpha', 'teta'];
var arr4 = ['alpha','beta','gamma', 'alpha']; // == arr1 + duplicate 'alpha'

console.log(getStringPrimeArrayHash(arr1)); // 30
console.log(getStringPrimeArrayHash(arr2)); // 30 also, like for arr1

var arr3 = ['alpha', 'teta'];
console.log(getStringPrimeArrayHash(arr3)); // 26 : a different array has != hashset

console.log(compareByPrimeHash(arr1, arr2) ); // true
console.log(compareByPrimeHash(arr1, arr3) ); // false
console.log(compareByPrimeHash(arr1, arr4) ); // true despite duplicate

- GameAlchemist

我还没有仔细检查过，但您能否将此添加到基准测试中，以便我们与@sifriday的解决方案进行比较？ - FredyC

哎呀，我刚意识到我不能使用这个解决方案。总共肯定会有超过32个字符串 :( - FredyC

我可能需要一些帮助。我甚至不知道如何通过程序找到质数 :( - FredyC

好的，我已经弄清楚了质数并且理解乘法。但是我不确定最后一部分。我需要运行模数来做什么？难道只比较这两个数字是否相等就不够了吗？ - FredyC

好的，谢谢。我也在考虑使用质数来解决问题。我会尝试将其实现到我的应用程序中。 - FredyC

显示剩余6条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sifriday · Accepted Answer

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

求和不依赖于顺序，这实际上是简单校验和的缺陷（它们无法捕获单词内块顺序的更改），
我们可以使用字符编码将字符串转换为可相加的数字

下面是一个执行（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 字符串，其中 charcodes 最高可达 255，并允许每个字符串中有 255 个字符，则 charsum 的最大返回值为 255 * 255 = 65025。因此，我选择了下一个素数 65027，并使用 (65027 / cs) 计算哈希。我并不百分之百地确信这会消除冲突...也许需要更多思考...但它肯定修复了 [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']

修复方法是基于字符索引向charsum函数添加乘数：

sum += (s.charCodeAt(i) * (i+1));