Ich muss Strings in eine Art Hash konvertieren. Ist das in JavaScript möglich?
Ich verwende keine serverseitige Sprache, daher kann ich das nicht so machen.
javascript
hash
Freesnöw
quelle
quelle
Antworten:
Quelle: http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/
quelle
hash << 5 - hash
ist das gleiche wiehash * 31 + char
aber viel schneller. Es ist schön, weil es so schnell ist und 31 eine kleine Primzahl ist. Win Win dort.(hash * 31) + char
ist identisch mit der Ausgabe des Shift-basierten Codes((hash<<5)-hash)+char
, selbst für sehr lange Zeichenfolgen (ich habe sie mit Zeichenfolgen mit mehr als einer Million Zeichen getestet), sodass sie nicht "unbrauchbar" ist der Genauigkeit. Die Komplexität ist O (n) sowohl für die zahlenbasierte als auch für die verschiebungsbasierte Version, daher ist sie hinsichtlich der Komplexität nicht "unbrauchbar".n
, was ist der größte,n
für den ich möglicherweise keine Kollision haben kann?var hashCode = function hashCode (str) {etc...}
? Und dann verwenden alshashCode("mystring")
?BEARBEITEN
Basierend auf meinen jsperf-Tests ist die akzeptierte Antwort tatsächlich schneller: http://jsperf.com/hashcodelordvlad
ORIGINAL
Wenn jemand interessiert ist, ist hier eine verbesserte (schnellere) Version, die bei älteren Browsern, denen die
reduce
Array-Funktion fehlt, fehlschlägt .Version mit einzeiliger Pfeilfunktion:
quelle
In einer Antwort auf diese Frage Welcher Hashing-Algorithmus eignet sich am besten für Eindeutigkeit und Geschwindigkeit? Ian Boyd hat eine gründliche Analyse veröffentlicht . Kurz gesagt (wie ich es interpretiere) kommt er zu dem Schluss, dass Murmeln am besten ist, gefolgt von FNV-1a.
Der von esmiralha vorgeschlagene String.hashCode () -Algorithmus von Java scheint eine Variante von DJB2 zu sein.
Einige Benchmarks mit großen Eingabezeichenfolgen hier: http://jsperf.com/32-bit-hash
Wenn kurze Eingabezeichenfolgen gehasht werden, sinkt die Leistung des Murmelns im Vergleich zu DJ2B und FNV-1a: http://jsperf.com/32- Bit-Hash / 3
Im Allgemeinen würde ich murmur3 empfehlen.
Eine JavaScript-Implementierung finden Sie hier: https://github.com/garycourt/murmurhash-js
Wenn die Eingabezeichenfolgen 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 kleine Codegröße wichtiger sind als Geschwindigkeit, verwende ich diese Implementierung von FNV-1a (basierend auf diesem Code ).
Kollisionswahrscheinlichkeit verbessern
Wie hier erklärt , können wir die Hash-Bitgröße mit diesem Trick erweitern:
Gehen Sie vorsichtig damit um und erwarten Sie nicht zu viel.
quelle
("0000000" + (hval >>> 0).toString(16)).substr(-8);
? Ist das nicht dasselbe wie(hval >>> 0).toString(16)
?hval
,(hval >>> 0).toString(16)
vielleicht weniger als 8 Zeichen lang sein, so dass Sie Pad mit Nullen. Ich war nur verwirrt, weil ich(hval >>> 0).toString(16)
immer genau 8 Zeichen hatte.Math.imul
Funktion implementiert wird . Das allein macht es zu Top-Benchmarks und letztendlich zu einer besseren Wahl als DJB2 auf lange Sicht.Basierend auf der akzeptierten Antwort in ES6. Kleiner, wartbar und funktioniert in modernen Browsern.
EDIT (2019-11-04) :
Version mit einzeiliger Pfeilfunktion:
quelle
str += ""
vor dem Hashing hinzugefügt habe , um Ausnahmen zu vermeiden, diestr.split is not a function
ausgelöst wurden, wenn Nicht-Strings als Parameter übergeben wurdenhash |= 0
, um in ein 32-Bit-Int zu konvertieren. Diese Implementierung funktioniert nicht. Ist das ein Fehler?Hier ist etwas Besseres - cyrb53 , ein einfacher, aber qualitativ hochwertiger 53-Bit-Hash. Es ist ziemlich schnell, bietet eine sehr gute Hash-Verteilung und deutlich niedrigere Kollisionsraten als jeder 32-Bit-Hash.
Ähnlich wie bei den bekannten MurmurHash / xxHash-Algorithmen wird eine Kombination aus Multiplikation und Xorshift verwendet , um den Hash zu generieren, jedoch nicht so gründlich. Dadurch ist es schneller als JavaScript und wesentlich einfacher zu implementieren.
Es wird eine Lawine (nicht streng) erreicht, was im Grunde bedeutet, dass kleine Änderungen in der Eingabe große Änderungen in der Ausgabe haben, wodurch der resultierende Hash zufällig erscheint:
Sie können auch einen Startwert für alternative Streams derselben Eingabe angeben:
Technisch gesehen handelt es sich um einen 64-Bit-Hash (zwei nicht korrelierte 32-Bit-Hashes parallel), aber JavaScript ist auf 53-Bit-Ganzzahlen beschränkt. Bei Bedarf kann die vollständige 64-Bit-Ausgabe weiterhin verwendet werden, indem die Rückgabezeile für eine Hex-Zeichenfolge oder ein Array geändert wird.
Beachten Sie, dass das Erstellen von Hex-Zeichenfolgen die Stapelverarbeitung in leistungskritischen Situationen drastisch verlangsamen kann.
Und nur zum Spaß, hier ist ein minimaler 32-Bit-Hash in 89 Zeichen mit höherer Qualität als sogar FNV oder DJB2:
quelle
ch
initialisiert?'imul'
.Wenn es jemandem hilft, habe ich die beiden
reduce
wichtigsten Antworten zu einer Version kombiniert, die ältere Browser toleriert. Diese Version verwendet die schnelle Version, sofern verfügbar, und greift auf die Lösung von esmiralha zurück, wenn dies nicht der Fall ist.Verwendung ist wie:
quelle
String.prototype.hashCode = function(){ var hash = 5381; if (this.length === 0) return hash; for (var i = 0; i < this.length; i++) { var character = this.charCodeAt(i); hash = ((hash<<5)+hash)^character; // Convert to 32bit integer } return hash; }
Dies ist eine raffinierte und leistungsstärkere Variante:
Dies entspricht der Implementierung des Standards durch Java
object.hashCode()
Hier ist auch eine, die nur positive Hashcodes zurückgibt:
Und hier ist eine passende für Java, die nur positive Hashcodes zurückgibt:
Genießen!
quelle
Ich bin ein bisschen überrascht, dass noch niemand über die neue SubtleCrypto-API gesprochen hat.
Um einen Hash aus einer Zeichenfolge abzurufen, können Sie die folgende
subtle.digest
Methode verwenden:quelle
var promise = crypto.subtle.digest({name: "SHA-256"}, Uint8Array.from(data)); promise.then(function(result){ console.log(Array.prototype.map.call(new Uint8Array(result), x => x.toString(16).padStart(2, '0')).join('')); });
crypto
ist nicht gerade performant.Dank des Beispiels von mar10 habe ich einen Weg gefunden, die gleichen Ergebnisse in C # AND Javascript für einen FNV-1a zu erzielen. 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 momentan nur URL-Pfade hashe.
C # -Version
JavaScript-Version
quelle
Math.imul
kann es für den Multiplikationsschritt verwendet werden, wodurch die Leistung erheblich verbessert wird . Das einzige Problem ist, dass es in IE11 ohne Shim nicht funktioniert .Eine schnelle und prägnante, die von hier angepasst wurde :
quelle
Ich brauchte eine ähnliche Funktion (aber anders), um eine eindeutige ID basierend auf dem Benutzernamen und der aktuellen Uhrzeit zu generieren. Damit:
Produziert:
edit Jun 2015: Für neuen Code verwende ich shortid: https://www.npmjs.com/package/shortid
quelle
Mein schneller (sehr langer) Einzeiler basierend auf der
Multiply+Xor
Methode von FNV :quelle
SubtleCrypto.digest
Sind Sie sicher , können Sie es nicht tun , dass die Art und Weise ?
Haben Sie vergessen, dass Sie Javascript verwenden, die Sprache, die sich ständig weiterentwickelt?
Versuchen Sie es
SubtleCrypto
. Es unterstützt die Hash-Funktionen SHA-1, SHA-128, SHA-256 und SHA-512.quelle
Ich bin etwas spät zur Party, aber Sie können dieses Modul verwenden: crypto :
Das Ergebnis dieser Funktion ist immer eine
64
Zeichenfolge. etwas wie das:"aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"
quelle
Ich habe die beiden Lösungen (Benutzer esmiralha und lordvlad) kombiniert, um eine Funktion zu erhalten, die für Browser, die die js-Funktion reduct () unterstützen, schneller sein sollte und dennoch mit alten Browsern kompatibel ist:
Beispiel:
quelle
Wenn Sie Kollisionen vermeiden möchten, können Sie einen sicheren Hash wie SHA-256 verwenden . Es gibt mehrere JavaScript SHA-256-Implementierungen.
Ich habe Tests geschrieben, um mehrere Hash-Implementierungen zu vergleichen, siehe https://github.com/brillout/test-javascript-hash-implementations .
Oder gehen Sie zu http://brillout.github.io/test-javascript-hash-implementations/ , um die Tests auszuführen.
quelle
Dies sollte ein bisschen sicherer sein als einige andere Antworten, jedoch in einer Funktion ohne vorinstallierte Quelle
Ich habe im Grunde eine minimierte vereinfachte Version von sha1 erstellt.
Sie nehmen die Bytes der Zeichenfolge und gruppieren sie nach 4 bis 32 Bit "Wörtern".
Dann erweitern wir alle 8 Wörter auf 40 Wörter (für eine größere Auswirkung auf das Ergebnis).
Dies geht zur Hashing-Funktion (der letzten Reduzierung), wo wir mit dem aktuellen Status und der Eingabe einige Berechnungen durchführen. Wir bekommen immer 4 Wörter raus.
Dies ist fast eine Ein-Befehls- / Ein-Zeilen-Version mit Map, Reduce ... anstelle von Schleifen, aber es ist immer noch ziemlich schnell
Wir konvertieren auch die Ausgabe in hex, um eine Zeichenfolge anstelle eines Wortarrays zu erhalten.
Die Verwendung ist einfach. zum Beispiel
"a string".hash()
wird zurückkehren"88a09e8f9cc6f8c71c4497fbb36f84cd"
Code-Snippet anzeigen
quelle
Ich habe mich für eine einfache Verkettung von Zeichencodes entschieden, die in Hex-Zeichenfolgen konvertiert wurden. Dies dient einem relativ engen Zweck, nämlich lediglich einer Hash-Darstellung einer SHORT-Zeichenfolge (z. B. Titel, Tags), die 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.
Dies kann mit Underscore knapper und browserverträglicher gemacht werden. Beispiel:
Ich nehme an, wenn Sie größere Zeichenfolgen auf ähnliche Weise hashen möchten, können Sie einfach die Zeichencodes reduzieren und die resultierende Summe hexifizieren, anstatt die einzelnen Zeichen miteinander zu verketten:
Natürlich mehr Kollisionsrisiko mit dieser Methode, obwohl Sie mit der Arithmetik in der Reduzierung herumspielen könnten, aber Sie wollten den Hash diversifizieren und verlängern.
quelle
Leicht vereinfachte Version von @ esmiralhas Antwort.
Ich überschreibe String in dieser Version nicht, da dies zu unerwünschtem Verhalten führen kann.
quelle
Fügen Sie dies hinzu, weil es noch niemand getan hat, und dies scheint viel gefragt und mit Hashes implementiert zu sein, aber es wird immer sehr schlecht gemacht ...
Dies erfordert eine Zeichenfolgeneingabe und eine maximale Anzahl, der der Hash entsprechen soll, und erzeugt eine eindeutige Zahl basierend auf der Zeichenfolgeneingabe.
Sie können dies verwenden, um einen eindeutigen Index für ein Array von Bildern zu erstellen (Wenn Sie einen bestimmten Avatar für einen Benutzer zurückgeben möchten, der zufällig ausgewählt, aber auch anhand seines Namens ausgewählt wurde, wird er immer einer Person mit diesem Namen zugewiesen ).
Sie können dies natürlich auch verwenden, um einen Index in ein Array von Farben zurückzugeben, z. B. um eindeutige Avatar-Hintergrundfarben basierend auf dem Namen einer Person zu generieren.
quelle
Ich sehe keinen Grund, diesen überkomplizierten Kryptocode anstelle von gebrauchsfertigen Lösungen wie Objekt-Hash-Bibliotheken usw. zu verwenden. Die Abhängigkeit vom Anbieter ist produktiver, spart Zeit und reduziert die Wartungskosten.
Verwenden Sie einfach https://github.com/puleos/object-hash
quelle
var crypto = require('crypto');
. Ich denke, es fügt diesen Abhängigkeitscode des Herstellers in der minimierten Version während eines Builds hinzu.