在 Javascript中从字符串生成哈希

我需要将字符串转换为某种形式的哈希。这在 JavaScript 中可能吗?

我需要将字符串转换为某种形式的哈希。这在 JavaScript 中可能吗?

我没有使用服务器端语言,所以我不能这样做。

997
String.prototype.hashCode = function() {
  var hash = 0,
    i, chr;
  if (this.length === 0) return hash;
  for (i = 0; i < this.length; i++) {
    chr = this.charCodeAt(i);
    hash = ((hash << 5) - hash) + chr;
    hash |= 0; // Convert to 32bit integer
  }
  return hash;
}
const str = 'revenue'
console.log(str, str.hashCode())
Source
295

这里的许多答案都是从 Java 中获取的相同的String.hashCode哈希函数。它可以追溯到 1981 年的 Gosling Emacs,非常弱,并且在现代 JavaScript 中实现了零意义的性能。实际上,使用 ES6Math.imul可以显着提高实现速度,但是没有人注意到。在基本相同的性能下,我们可以做得更好。

这是我做的一个-cyrb53,一个简单但高质量的 53 位哈希。它非常快,提供非常好的 * 哈希分布,并且由于它输出 53 位,与任何32 位哈希相比,具有显着更低的冲突率。此外,您可以忽略 SA 的 CC 许可证,因为它是public domain on my GitHub

const cyrb53 = (str, seed = 0) => {
  let h1 = 0xdeadbeef ^ seed,
    h2 = 0x41c6ce57 ^ seed;
  for (let i = 0, ch; i < str.length; i++) {
    ch = str.charCodeAt(i);
    h1 = Math.imul(h1 ^ ch, 2654435761);
    h2 = Math.imul(h2 ^ ch, 1597334677);
  }
  
  h1 = Math.imul(h1 ^ (h1 >>> 16), 2246822507) ^ Math.imul(h2 ^ (h2 >>> 13), 3266489909);
  h2 = Math.imul(h2 ^ (h2 >>> 16), 2246822507) ^ Math.imul(h1 ^ (h1 >>> 13), 3266489909);
  
  return 4294967296 * (2097151 & h2) + (h1 >>> 0);
};
console.log(`cyrb53('a') -> ${cyrb53('a')}`)
console.log(`cyrb53('b') -> ${cyrb53('b')}`)
console.log(`cyrb53('revenge') -> ${cyrb53('revenge')}`)
console.log(`cyrb53('revenue') -> ${cyrb53('revenue')}`)
console.log(`cyrb53('revenue', 1) -> ${cyrb53('revenue', 1)}`)
console.log(`cyrb53('revenue', 2) -> ${cyrb53('revenue', 2)}`)
console.log(`cyrb53('revenue', 3) -> ${cyrb53('revenue', 3)}`)

* 它大致类似于著名的 MurmurHash / xxHash 算法。它使用乘法和Xorshift的组合来生成哈希,但不那么彻底。因此,它比 JavaScript 中的任何一个都要快,并且实现起来要简单得多,但可能无法通过 SMHasher 中的所有测试。这不是加密哈希函数,因此不要将其用于安全目的。

像任何适当的哈希一样,它具有雪崩效应,这基本上意味着输入中的小变化在输出中具有大变化,使得结果哈希看起来更“随机”:

"501c2ba782c97901" = cyrb53("a")
"459eda5bc254d2bf" = cyrb53("b")
"fbce64cc3b748385" = cyrb53("revenge")
"fb1d85148d13f93a" = cyrb53("revenue")

您可以选择为相同输入的备用流提供(无符号整数,最大 32 位):

"76fee5e6598ccd5c" = cyrb53("revenue", 1)
"1f672e2831253862" = cyrb53("revenue", 2)
"2b10de31708e6ab7" = cyrb53("revenue", 3)

从技术上讲,它是一个 64 位哈希,即两个不相关的 32 位哈希并行计算,但 JavaScript 仅限于 53 位整数。如果方便,可以通过使用十六进制字符串或数组更改return 语句来使用完整的 64 位输出。

return [h2>>>0, h1>>>0];
// or
return (h2>>>0).toString(16).padStart(8,0)+(h1>>>0).toString(16).padStart(8,0);
// or 
return 4294967296n * BigInt(h2) + BigInt(h1);

请注意,构造十六进制字符串会大大减慢批处理速度。数组效率要高得多,但显然需要两次检查而不是一次。我还包括BigInt,它应该比String稍快,但仍然比ArrayNumber慢得多。

只是为了好玩,这里是 TinySimpleHash,我能想出的最小哈希值仍然不错。它是89 chars中的 32 位哈希,具有比 FNV 或 DJB2 更好的质量随机性:

TSH=s=>{for(var i=0,h=9;i<s.length;)h=Math.imul(h^s.charCodeAt(i++),9**9);return h^h>>>9}
189
EDIT

根据我的 jsperf 测试,接受的答案实际上更快:http://jsperf.com/hashcodelordvlad

ORIGINAL

如果有人感兴趣,这里是一个改进的(更快的)版本,它将在缺少reduce数组函数的较旧浏览器上失败。

hashCode = function(s){
  return s.split("").reduce(function(a,b){a=((a<<5)-a)+b.charCodeAt(0);return a&a},0);              
}

单线箭头函数版本:

hashCode = s => s.split('').reduce((a,b)=>{a=((a<<5)-a)+b.charCodeAt(0);return a&a},0)
131

注意:即使使用最佳的 32 位哈希,冲突迟早会发生。

The hash collision probability can be calculated as 1 - e ^ (-k(k-1) / 2N, approximated as k^2 / 2N (see here). This may be higher than intuition suggests:
Assuming a 32-bit hash and k=10,000 items, a collision will occur with a probability of 1.2%. For 77,163 samples the probability becomes 50%! (calculator).
I suggest a workaround at the bottom.

在对这个问题Which hashing algorithm is best for uniqueness and speed?的回答中,伊恩 · 博伊德发布了一个很好的in depth ysis。简而言之 (正如我所解释的),他得出的结论是MurmurHash最好,其次是FNV-1a
esmiralha 提出的 Java 的String.hashCode()算法似乎是4

FNV-1a具有比 DJB2 更好的分布,但速度较慢

DJB2比 FNV-1a 快,但往往会产生更多的碰撞

MurmurHash3比 DJB2 和 FNV-1a 更好,更快(但是优化的实现比 FNV 和 DJB2 需要更多的代码行)

这里有一些带有大输入字符串的基准测试:http://jsperf.com/32-bit-hash
short输入字符串被哈希时,相对于 DJ2B 和 FNV-1a,杂音的性能下降:http://jsperf.com/32-bit-hash/3

因此,总的来说,我建议使用 murmur3。
请参阅此处的 JavaScript 实现:https://github.com/garycourt/murmurhash-js

如果输入字符串很短,并且性能比分发质量更重要,请使用 DJB2(如 esmiralha 接受的答案所建议的那样)。

如果质量和小代码大小比速度更重要,我使用 FNV-1a 的这种实现(基于this code)。

/**
 * Calculate a 32 bit FNV-1a hash
 * Found here: https://gist.github.com/vaiorabbit/5657561
 * Ref.: http://isthe.com/chongo/tech/comp/fnv/
 *
 * @param {string} str the input value
 * @param {boolean} [asString=false] set to true to return the hash value as 
 *     8-digit hex string instead of an integer
 * @param {integer} [seed] optionally pass the hash of the previous chunk
 * @returns {integer | string}
 */
function hashFnv32a(str, asString, seed) {
    /*jshint bitwise:false */
    var i, l,
        hval = (seed === undefined) ? 0x811c9dc5 : seed;
    for (i = 0, l = str.length; i < l; i++) {
        hval ^= str.charCodeAt(i);
        hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
    }
    if( asString ){
        // Convert to 8 digit hex string
        return ("0000000" + (hval >>> 0).toString(16)).substr(-8);
    }
    return hval >>> 0;
}

提高碰撞概率

As explained here,我们可以使用此技巧扩展哈希位大小:

function hash64(str) {
    var h1 = hash32(str);  // returns 32 bit (as 8 byte hex string)
    return h1 + hash32(h1 + str);  // 64 bit (as 16 byte hex string)
}

小心使用它,不要期望太多。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处

(907)
猜猜-谁最佳算法(guess who questions)
上一篇
不受版本控制的文件不知从哪里出现(appear from nowhere)
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(36条)