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

4

4 回答 4

4

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

  1. 求和不依赖于顺序,这实际上是简单校验和的一个缺陷(它们不会在一个单词中捕捉到块顺序的变化),并且

  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)
}

在这里小提琴: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));
于 2014-08-03T14:22:01.540 回答
1

如果您为每个字符串计算一个数字哈希码,那么您可以将它们与顺序无关紧要的运算符(例如^XOR 运算符)结合起来,那么您不需要对数组进行排序:

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
};
于 2014-08-03T12:51:53.283 回答
0

如果您的一组可能的字符串长度小于 32 项,则使用非常快的哈希值的想法:使用内置哈希函数对字符串进行哈希处理,该函数将返回 2 的幂作为哈希​​值:

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);
}

然后在你的字符串数组上使用这个散列,对散列( | )进行 ORing:

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

求问!!!使用这种方法,数组被认为是集合,这意味着重复的项目不会改变数组的哈希!!!

这必须更快,因为它只使用 1) 函数调用 2) 查找 3) 整数算术。所以没有排序,没有(长)字符串,没有连接。

jsperf 确认:http: //jsperf.com/hashing-array-of-strings/4

在此处输入图像描述

编辑 :

带有素数的版本,在这里: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
于 2014-08-03T15:27:34.073 回答
0

你可以这样做:

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

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

'\u200b' == '\0'

> false
于 2014-08-03T12:33:02.423 回答