Generiere einen Hash aus einer Zeichenkette in Javascript / jQuery


Ich muss Strings in eine Form von Hash konvertieren. Ist das in Javascript / jQuery möglich?

Ich benutze keine serverseitige Sprache, also kann ich es nicht so machen.



Answers





BEARBEITEN

basierend auf meinen jsperf-tests ist die akzeptierte antwort tatsächlich schneller: http://jsperf.com/hashcodelordvlad

ORIGINAL

Wenn jemand interessiert ist, hier ist eine verbesserte (schnellere) Version, die bei älteren Browsern fehlschlagen wird, denen die reduce Array-Funktion fehlt.

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



Hinweis: Selbst mit dem besten 32-Bit-Hash müssen Sie sich damit auseinandersetzen, dass es früher oder später zu Kollisionen kommen wird . Dh zwei verschiedene Eingabe-Strings geben den gleichen Hash-Wert mit einer Wahrscheinlichkeit von mindestens 1: 2 ^ 32 zurück.

In einer Antwort auf diese Frage Welcher Hashalgorithmus ist am besten für Einzigartigkeit und Geschwindigkeit? , Ian Boyd hat eine gründliche Analyse veröffentlicht . Kurz gesagt (wie ich es interpretiere) kommt er zu dem Schluss, dass Murmur am besten ist, gefolgt von FNV-1a.
Java's String.hashCode () Algorithmus, den esmiralha vorgeschlagen hat, scheint eine Variante von DJB2 zu sein.

  • FNV-1a hat eine bessere Verteilung als DJB2, ist aber langsamer
  • DJB2 ist schneller als FNV-1a, neigt jedoch zu mehr Kollisionen
  • MurmurHash3 ist besser und schneller als DJB2 und FNV-1a (aber die optimierte Implementierung benötigt mehr Codezeilen als FNV und DJB2)

Einige Benchmarks mit großen Eingabe-Strings finden Sie hier: http://jsperf.com/32-bit-hash
Wenn kurze Eingabe-Strings hashed werden, sinkt die Leistung von murmur relativ zu DJ2B und FNV-1a: http://jsperf.com/32-bit-hash/3

Also würde ich im Allgemeinen murmur3 empfehlen.
Siehe hier für eine JavaScript-Implementierung: https://github.com/garycourt/murmurhash-js

Wenn die Eingabezeichenfolgen kurz sind und die Leistung wichtiger als die Verteilungsqualität ist, verwenden Sie DJB2 (wie von der akzeptierten Antwort von esmiralha vorgeschlagen).

Wenn Qualität und kleine Codegröße wichtiger sind als Geschwindigkeit, verwende ich diese Implementierung von FNV-1a (basierend auf diesem 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;
}



Wenn es jemandem hilft, habe ich die ersten beiden Antworten in einer älteren, browser-toleranten Version kombiniert, die die schnelle Version verwendet, wenn reduce verfügbar ist, und auf esmiralhas Lösung zurückgreift, falls dies nicht der Fall ist.

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

Verwendung ist wie:

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



Basiert auf der akzeptierten Antwort in ES6. Kleiner, wartungsfreundlicher und funktioniert in modernen Browsern.

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

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




Dies ist eine verfeinerte und leistungsfähigere Variante:

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

Dies entspricht der Java-Implementierung des Standards object.hashCode()

Hier ist auch einer, der nur positive Hashcodes zurückgibt:

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

Und hier ist ein passender für Java, der nur positive Hashcodes zurückgibt:

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

Genießen!




Dank dem Beispiel von mar10 habe ich einen Weg gefunden, um die gleichen Ergebnisse in C # UND Javascript für ein FNV-1a zu erhalten. Wenn Unicode-Zeichen vorhanden sind, wird der obere Teil aus Gründen der Leistung verworfen. Ich weiß nicht, warum es hilfreich wäre, diese beim Hashing beizubehalten, da ich bisher nur Hash-Pfade habe.

C # Version

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-Version

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



Ich benötigte eine ähnliche Funktion (aber anders), um eine eindeutige ish-ID basierend auf dem Benutzernamen und der aktuellen Uhrzeit zu generieren. Damit:

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

Produziert:

2DVFXJGEKL
6IZPAKFQFL
ORGOENVMG
... etc 

edit Jun 2015: Für neuen Code verwende ich shortid: https://www.npmjs.com/package/shortid




Ich bin ein bisschen überrascht, dass noch niemand über die neue SubtleCrypto API gesprochen hat.

Um einen Hash aus einer Zeichenfolge zu erhalten, können Sie die Methode subtle.digest verwenden:

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




Eine schnelle und prägnante, die von hier angepasst wurde :

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



Ich habe die beiden Lösungen (Benutzer esmiralha und lordvlad) kombiniert, um eine Funktion zu erhalten, die für Browser, die die js-Funktion reduce () unterstützen, noch schneller sein sollte und weiterhin mit alten Browsern kompatibel ist:

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

Beispiel:

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



Ich habe mich für eine einfache Verkettung von Char-Codes entschieden, die in Hex-Strings konvertiert wurden. Dies dient einem relativ engen Zweck, nämlich dass nur eine Hash-Darstellung einer SHORT-Zeichenfolge (z. B. Titel, Tags) mit einer Serverseite ausgetauscht werden muss, die aus nicht relevanten Gründen den akzeptierten hashCode-Java-Port nicht einfach implementieren kann. Offensichtlich keine Sicherheitsanwendung hier.

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

Dies kann mit Underscore knapper und browser-toleranter gemacht werden. Beispiel:

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

Ich nehme an, wenn Sie größere Strings auf ähnliche Weise hashen wollten, könnten Sie einfach die Char-Codes reduzieren und die resultierende Summe hexieren, anstatt die einzelnen Zeichen miteinander zu verketten:

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"

Natürlich mehr Risiko der Kollision mit dieser Methode, obwohl Sie mit der Arithmetik in der reduzieren konnte aber Sie wollten den Hash zu diversifizieren und verlängern.







Leicht vereinfachte Version von @ esmiralha's Antwort.

Ich überschreibe String in dieser Version nicht, da dies zu unerwünschtem Verhalten führen kann.

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



Mit dieser Lösung können wir den Zeichensatz festlegen, um einige Probleme zu vermeiden, wenn die Werte zwischen Anwendungsebenen gespeichert oder gesendet werden. Beispiel: Wenn die Ergebniszeichenfolge (Hash) eine Prozentcodierung erzeugt und diese Zeichenfolge mit der GET-Methode aus der Ansicht an den Controller gesendet wird Schicht.

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

}