Erzeugen eines Hash aus einem String in Javascript

Question

Ich muss Zeichenketten in eine Form von Hash konvertieren. Ist dies in JavaScript möglich?

Ich verwende keine serverseitige Sprache, also kann ich es nicht auf diese Weise tun.

Answer 1

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

Fuente

Answer 2

Viele der Antworten hier sind die gleichen String.hashCode Hash-Funktion, die aus Java übernommen wurde. Sie stammt aus dem Jahr 1981 von Gosling Emacs, ist extrem schwach und macht in modernem JavaScript leistungsmäßig keinen Sinn. Tatsächlich könnten Implementierungen durch die Verwendung von ES6 deutlich schneller sein Math.imul aber niemand hat es bemerkt. Wir können das viel besser machen, bei im Wesentlichen gleicher Leistung.

Hier ist eine, die ich gemacht habe. cyrb53 einen einfachen, aber qualitativ hochwertigen 53-Bit-Hash. Er ist recht schnell, bietet eine sehr gute* Hash-Verteilung und hat, da er 53 Bits ausgibt, deutlich niedrigere Kollisionsraten im Vergleich zu jede 32-Bit-Hash. Außerdem können Sie die CC-Lizenz von SA ignorieren, da sie öffentlich zugänglich auf meinem 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)}`)

*Er ähnelt in etwa den bekannten MurmurHash/xxHash-Algorithmen. Er verwendet eine Kombination aus Multiplikation und Xorshift um den Hash zu erzeugen, aber nicht so gründlich. Das Ergebnis ist, dass es schneller ist als in JavaScript und wesentlich einfacher zu implementieren ist, aber möglicherweise nicht alle Tests in SMHasher besteht. Dies ist keine kryptografische Hash-Funktion, also verwenden Sie sie nicht für Sicherheitszwecke.

Wie jeder richtige Hash hat er einen Avalanche-Effekt, d. h. kleine Änderungen in der Eingabe haben große Änderungen in der Ausgabe zur Folge, wodurch der resultierende Hash "zufälliger" erscheint:

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

Sie können optional einen Seed (ganze Zahl ohne Vorzeichen, maximal 32 Bit) für alternative Streams derselben Eingabe angeben:

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

Technisch gesehen handelt es sich um einen 64-Bit-Hash, d. h. um zwei unkorrelierte 32-Bit-Hashes, die parallel berechnet werden, aber JavaScript ist auf 53-Bit-Ganzzahlen beschränkt. Wenn es zweckmäßig ist, kann die volle 64-Bit-Ausgabe verwendet werden, indem die Rückkehranweisung mit einer Hex-Zeichenkette oder einem Array.

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

Beachten Sie, dass die Konstruktion von Hex-Strings die Stapelverarbeitung drastisch verlangsamt. Das Array ist viel effizienter, erfordert aber natürlich zwei Überprüfungen anstelle von einer. Ich habe auch BigInt was etwas schneller sein sollte als String aber immer noch viel langsamer als Array o Number .

---

Hier ist TinySimpleHash, der kleinste Hash, den ich finden konnte und der immer noch anständig ist, nur zum Spaß. Es ist ein 32-Bit-Hash in 89 Zeichen mit besserer Zufallsqualität als sogar FNV oder 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}

Answer 3

EDITAR

Nach meinen Tests mit jsperf ist die akzeptierte Antwort tatsächlich schneller: http://jsperf.com/hashcodelordvlad

ORIGINAL

falls es jemanden interessiert, hier ist eine verbesserte (schnellere) Version, die auf älteren Browsern, die nicht die reduce Array-Funktion.

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

Einzeiler-Pfeilfunktion Version :

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

Answer 4

Anmerkung: Selbst mit dem besten 32-Bit-Hash gibt es Kollisionen se früher oder später auftreten.

Die Hash-Kollisionswahrscheinlichkeit kann wie folgt berechnet werden , angenähert als ( siehe hier ). Dieser Wert könnte höher sein, als die Intuition vermuten lässt:
Geht man von einem 32-Bit-Hash und k=10.000 Elementen aus, so tritt eine Kollision mit einer Wahrscheinlichkeit von 1,2 % auf. Bei 77.163 Stichproben liegt die Wahrscheinlichkeit bei 50%! ( Rechner ).
Ich schlage unten eine Umgehung vor.

In einer Antwort auf diese Frage Welcher Hashing-Algorithmus ist am besten für Eindeutigkeit und Geschwindigkeit geeignet? , Ian Boyd hat einen guten vertiefte Analyse . Kurz gesagt (wie ich es interpretiere), kommt er zu dem Schluss, dass MurmurHash ist am besten, gefolgt von FNV-1a .
Java's String.hashCode() Algorithmus, den esmiralha vorgeschlagen hat, scheint eine Variante zu sein von DJB2 .

• FNV-1a hat eine bessere Verteilung als DJB2, ist aber langsamer
• DJB2 ist schneller als FNV-1a, führt aber tendenziell zu mehr Kollisionen
• MurmurHash3 ist besser und schneller als DJB2 und FNV-1a (aber die optimierte Implementierung erfordert mehr Codezeilen als FNV und DJB2)

Hier einige Benchmarks mit großen Eingabestrings: http://jsperf.com/32-bit-hash
Wenn kurz Eingabezeichenfolgen gehasht werden, sinkt die Leistung von murmur im Vergleich zu DJ2B und FNV-1a: http://jsperf.com/32-bit-hash/3

Generell würde ich also murmur3 empfehlen.
Hier finden Sie eine JavaScript-Implementierung: https://github.com/garycourt/murmurhash-js

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

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

Verbesserung der Kollisionswahrscheinlichkeit

Wie hier erklärt können wir die Hash-Bitgröße mit diesem Trick erweitern:

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

Verwenden Sie es mit Vorsicht und erwarten Sie nicht zu viel.

Answer 5

Basierend auf akzeptierte Antwort in ES6. Kleiner, wartbar und funktioniert in modernen Browsern.

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

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

BEARBEITEN (2019-11-04) :

Einzeiler-Pfeilfunktion Version :

const hashCode = s => s.split('').reduce((a,b) => (((a << 5) - a) + b.charCodeAt(0))|0, 0)

// test
console.log(hashCode('Hello!'))