在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

}