在Javascript / jQuery中从字符串生成哈希


我需要将字符串转换为某种形式的散列。 这是可能的JavaScript / jQuery?

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


Answers






编辑

基于我的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);              
}



注意:即使使用最好的32位散列,也必须处理碰撞迟早发生的事实。 即两个不同的输入字符串将返回相同的散列值,概率至少为1:2 ^ 32。

在这个问题的答案哈希算法是最好的唯一性和速度? Ian Boyd发表了一篇很好的深度分析报告 。 总之(正如我的解释),他得出的结论是,Murmur是最好的,其次是FNV-1a。
Java的String.hashCode()算法esmiralha提出似乎是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;
}



如果有帮助的话,我把前两个答案结合到一个较老的浏览器容忍的版本中,如果有可用的版本,它会使用快速版本,如果没有的话,可以回到esmiralha的解决方案。

/**
 * @see http://.com/q/7616461/940217
 * @return {number}
 */
String.prototype.hashCode = function(){
    if (Array.prototype.reduce){
        return this.split("").reduce(function(a,b){a=((a<<5)-a)+b.charCodeAt(0);return a&a},0);              
    } 
    var hash = 0;
    if (this.length === 0) return hash;
    for (var i = 0; i < this.length; i++) {
        var character  = this.charCodeAt(i);
        hash  = ((hash<<5)-hash)+character;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
}

用法如下:

var hash = new String("some string to be hashed").hashCode();



基于ES6中接受的答案 。 更小,可维护,适用于现代浏览器。

function hashCode(str) {
  return str.split('').reduce((prevHash, currVal) =>
    ((prevHash << 5) - prevHash) + currVal.charCodeAt(0), 0);
}

// Test
console.log("hashCode(\"Hello!\"): ", hashCode('Hello!'));




这是一个精致,性能更好的变体:

String.prototype.hashCode = function() {
    var hash = 0, i = 0, len = this.length;
    while ( i < len ) {
        hash  = ((hash << 5) - hash + this.charCodeAt(i++)) << 0;
    }
    return hash;
};

这与Java的标准object.hashCode()的实现相匹配

这也是一个只返回肯定的hashcode:

String.prototype.hashcode = function() {
    return (this.hashCode() + 2147483647) + 1;
};

这里是一个匹配的Java只返回正的hashcode:

public static long hashcode(Object obj) {
    return ((long) obj.hashCode()) + Integer.MAX_VALUE + 1l;
}

请享用!




感谢mar10的例子,我发现了一种在C#和Javascript中为FNV-1a获得相同结果的方法。 如果存在unicode字符,则为了性能而丢弃上部分。 不知道为什么在散列的时候保持这些是有帮助的,因为现在只有散列url路径。

C#版本

private static readonly UInt32 FNV_OFFSET_32 = 0x811c9dc5;   // 2166136261
private static readonly UInt32 FNV_PRIME_32 = 0x1000193;     // 16777619

// Unsigned 32bit integer FNV-1a
public static UInt32 HashFnv32u(this string s)
{
    // byte[] arr = Encoding.UTF8.GetBytes(s);      // 8 bit expanded unicode array
    char[] arr = s.ToCharArray();                   // 16 bit unicode is native .net 

    UInt32 hash = FNV_OFFSET_32;
    for (var i = 0; i < s.Length; i++)
    {
        // Strips unicode bits, only the lower 8 bits of the values are used
        hash = hash ^ unchecked((byte)(arr[i] & 0xFF));
        hash = hash * FNV_PRIME_32;
    }
    return hash;
}

// Signed hash for storing in SQL Server
public static Int32 HashFnv32s(this string s)
{
    return unchecked((int)s.HashFnv32u());
}

JavaScript版本

var utils = utils || {};

utils.FNV_OFFSET_32 = 0x811c9dc5;

utils.hashFnv32a = function (input) {
    var hval = utils.FNV_OFFSET_32;

    // Strips unicode bits, only the lower 8 bits of the values are used
    for (var i = 0; i < input.length; i++) {
        hval = hval ^ (input.charCodeAt(i) & 0xFF);
        hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
    }

    return hval >>> 0;
}

utils.toHex = function (val) {
    return ("0000000" + (val >>> 0).toString(16)).substr(-8);
}



我需要一个类似的功能(但不同)来根据用户名和当前时间生成一个唯一的ID。 所以:

window.newId = ->
  # create a number based on the username
  unless window.userNumber?
    window.userNumber = 0
  for c,i in window.MyNamespace.userName
    char = window.MyNamespace.userName.charCodeAt(i)
    window.MyNamespace.userNumber+=char
  ((window.MyNamespace.userNumber + Math.floor(Math.random() * 1e15) + new Date().getMilliseconds()).toString(36)).toUpperCase()

生产:

2DVFXJGEKL
6IZPAKFQFL
ORGOENVMG
... etc 

编辑2015年6月:对于新代码,我使用shortid: https ://www.npmjs.com/package/shortid




我有点惊讶没有人谈论新的SubtleCrypto API呢。

要从字符串中获取散列,可以使用subtle.digest方法:

function getHash(str, algo = "SHA-256") {
  let strBuf = new TextEncoder('utf-8').encode(str);
  return crypto.subtle.digest(algo, strBuf)
    .then(hash => {
      window.hash = hash;
      // here hash is an arrayBuffer, 
      // so we'll connvert it to its hex version
      let result = '';
      const view = new DataView(hash);
      for (let i = 0; i < hash.byteLength; i += 4) {
        result += ('00000000' + view.getUint32(i).toString(16)).slice(-8);
      }
      return result;
    });
}

getHash('hello world')
  .then(hash => {
    console.log(hash);
  });




一个从这里改编的快速简洁的一个:

String.prototype.hashCode = function() {
  var hash = 5381, i = this.length
  while(i)
    hash = (hash * 33) ^ this.charCodeAt(--i)
  return hash >>> 0;
}



我已经将两个解决方案(用户esmiralha和lordvlad)结合起来,为支持js函数reduce()的浏览器提供了一个更快的功能,并且仍然与旧浏览器兼容:

String.prototype.hashCode = function() {

    if (Array.prototype.reduce) {
        return this.split("").reduce(function(a,b){a=((a<<5)-a)+b.charCodeAt(0);return a&a},0);   
    } else {

        var hash = 0, i, chr, len;
        if (this.length == 0) return hash;
        for (i = 0, len = this.length; i < len; i++) {
        chr   = this.charCodeAt(i);
        hash  = ((hash << 5) - hash) + chr;
        hash |= 0; // Convert to 32bit integer
        }
        return hash;
    }
};

例:

my_string = 'xyz';
my_string.hashCode();



我去了一个简单的连接字符代码转换为十六进制字符串。 这提供了相对较窄的目的,即只需要与服务器端交换的SHORT字符串(例如标题,标签)的哈希表示,由于不相关的原因,不能轻易地实现接受的哈希码Java端口。 显然这里没有安全应用程序。

String.prototype.hash = function() {
  var self = this, range = Array(this.length);
  for(var i = 0; i < this.length; i++) {
    range[i] = i;
  }
  return Array.prototype.map.call(range, function(i) {
    return self.charCodeAt(i).toString(16);
  }).join('');
}

用Underscore可以使这个更简洁和浏览器容忍。 例:

"Lorem Ipsum".hash()
"4c6f72656d20497073756d"

我想,如果你想以类似的方式散列较大的字符串,你可以减少字符代码,并把结果和,而不是把各个字符连接在一起:

String.prototype.hashLarge = function() {
  var self = this, range = Array(this.length);
  for(var i = 0; i < this.length; i++) {
    range[i] = i;
  }
  return Array.prototype.reduce.call(range, function(sum, i) {
    return sum + self.charCodeAt(i);
  }, 0).toString(16);
}

'One time, I hired a monkey to take notes for me in class. I would just sit back with my mind completely blank while the monkey scribbled on little pieces of paper. At the end of the week, the teacher said, "Class, I want you to write a paper using your notes." So I wrote a paper that said, "Hello! My name is Bingo! I like to climb on things! Can I have a banana? Eek, eek!" I got an F. When I told my mom about it, she said, "I told you, never trust a monkey!"'.hashLarge()
"9ce7"

这种方法自然会产生更多的碰撞风险,尽管你可以在减少算术的时候调整算法,但是你想要多样化和加长哈希。







@ esmiralha的答案略微简化的版本。

我不重写在这个版本的字符串,因为这可能会导致一些不受欢迎的行为。

function hashCode(str) {
    var hash = 0;
    for (var i = 0; i < str.length; i++) {
        hash = ~~(((hash << 5) - hash) + str.charCodeAt(i));
    }
    return hash;
}



使用这个解决方案,我们可以指定字符集,以避免在应用程序层之间存储或发送值时出现一些问题,例如:当结果字符串(哈希)产生百分比编码,并且该字符串从视图中使用GET方法发送给控制器层。

function doHashCode() {
    String.prototype.hashCode = function () {
        var text = "";
        var possible = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

        for (var i = 0; i < 15; i++)
            text += possible.charAt(Math.floor(Math.random() * possible.length));
        return text;
    }

    var hash = new String().hashCode();
    $('#input-text-hash').val(hash); // your html input text

}