协慌网

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

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

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

来源： http：//werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/

编辑

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

原来的

如果有人感兴趣，这是一个改进的（更快的）版本，它将在缺少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)

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

哈希冲突概率可以计算为 ，近似为 （请参阅此处）。这可能比直觉暗示的要高：
假设一个 32 位哈希且 k = 10,000 个项目，则发生碰撞的概率为 1.2％。对于 77,163 个样本，概率变为 50％！ （计算器）。
我建议在底部的一种解决方法。

在回答这个问题时， 哪种哈希算法最适合唯一性和速度？ ，伊恩 · 博伊德（Ian Boyd）进行了深入的分析。简而言之（据我的解释），他得出的结论是 Murmur 最好，其次是 FNV-1a。
esmiralha 提出的 Java String.hashCode（）算法似乎是 DJB2 的一种变体。

• FNV-1a 具有比 DJB2 更好的分布，但速度较慢
• DJB2 比 FNV-1a 快，但往往会产生更多碰撞
• MurmurHash3 比 DJB2 和 FNV-1a 更好和更快（但是优化的实现比 FNV 和 DJB2 需要更多的代码行）

一些带有较大输入字符串的基准测试： http://jsperf.com/32-bit-hash
当短输入字符串被散列时，相对于 DJ2B 和 FNV-1a，杂音的性能下降： http://jsperf.com/32-bit-hash/3

因此，一般而言，我会推荐 murmur3。
参见此处以获取 JavaScript 实现： https：//github.com/garycourt/murmurhash-js

如果输入字符串短并且性能比分发质量更重要，请使用 DJB2（由 esmiralha 接受的答案提出）。

如果质量和小的代码大小比速度更重要，那么我将使用 FNV-1a 的此实现（基于此代码）。

/**
 * 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;
}

提高碰撞概率

如此处所述，我们可以使用以下技巧扩展哈希位的大小：

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

请谨慎使用，但不要期望过高。