Wie in Update 3 zu dieser Antwort klargestellt, lautet diese Notation:
var hash = {};
hash[X]
hasht das Objekt nicht wirklich X
; Es konvertiert tatsächlich nur X
in eine Zeichenfolge (über, .toString()
wenn es sich um ein Objekt handelt, oder über andere integrierte Konvertierungen für verschiedene primitive Typen) und sucht diese Zeichenfolge dann in " hash
" , ohne sie zu hashen . Die Objektgleichheit wird ebenfalls nicht überprüft. Wenn zwei verschiedene Objekte dieselbe Zeichenfolgenkonvertierung haben, überschreiben sie sich gegenseitig.
Vor diesem Hintergrund - gibt es effiziente Implementierungen von Hashmaps in Javascript? (Beispielsweise javascript hashmap
liefert das 2. Google-Ergebnis von eine Implementierung, die für jede Operation O (n) ist. Verschiedene andere Ergebnisse ignorieren die Tatsache, dass sich verschiedene Objekte mit äquivalenten Zeichenfolgendarstellungen gegenseitig überschreiben.
Antworten:
Warum haschen Sie Ihre Objekte nicht selbst manuell und verwenden die resultierenden Zeichenfolgen als Schlüssel für ein reguläres JavaScript-Wörterbuch? Schließlich sind Sie in der besten Position, um zu wissen, was Ihre Objekte einzigartig macht. Das ist, was ich tue.
Beispiel:
Auf diese Weise können Sie die von JavaScript durchgeführte Indizierung steuern, ohne die Speicherzuweisung und die Überlaufbehandlung erheblich zu beeinträchtigen.
Wenn Sie wirklich die "industrielle Lösung" wollen, können Sie natürlich eine Klasse erstellen, die durch die Schlüsselfunktion und mit allen erforderlichen APIs des Containers parametrisiert wird, aber ... wir verwenden JavaScript und versuchen, einfach und leicht zu sein Diese funktionale Lösung ist einfach und schnell.
Die Schlüsselfunktion kann so einfach sein wie die Auswahl der richtigen Attribute des Objekts, z. B. eines Schlüssels oder eines Satzes von Schlüsseln, die bereits eindeutig sind, einer Kombination von Schlüsseln, die zusammen eindeutig sind, oder so komplex wie die Verwendung einiger kryptografischer Hashes wie in DojoX-Codierung oder DojoX-UUID . Während letztere Lösungen eindeutige Schlüssel erzeugen können, versuche ich persönlich, sie um jeden Preis zu vermeiden, insbesondere wenn ich weiß, was meine Objekte einzigartig macht.
Update im Jahr 2014: Bereits im Jahr 2008 beantwortet, erfordert diese einfache Lösung noch weitere Erklärungen. Lassen Sie mich die Idee in einem Q & A-Formular erläutern.
Ihre Lösung hat keinen echten Hash. Wo ist es???
JavaScript ist eine Hochsprache. Das Grundelement ( Objekt ) enthält eine Hash-Tabelle, um die Eigenschaften beizubehalten. Diese Hash-Tabelle wird normalerweise aus Effizienzgründen in einer einfachen Sprache geschrieben. Mit einem einfachen Objekt mit String-Schlüsseln verwenden wir eine effizient implementierte Hash-Tabelle, ohne dass wir uns darum bemühen müssen.
Woher weißt du, dass sie Hash verwenden?
Es gibt drei Möglichkeiten, eine Sammlung von Objekten mit einem Schlüssel adressierbar zu halten:
Offensichtlich verwenden JavaScript-Objekte Hash-Tabellen in irgendeiner Form, um allgemeine Fälle zu behandeln.
Verwenden Browser-Anbieter wirklich Hash-Tabellen?
Ja wirklich.
Behandeln sie Kollisionen?
Ja. Siehe oben. Wenn Sie eine Kollision mit ungleichen Zeichenfolgen gefunden haben, zögern Sie bitte nicht, einen Fehler bei einem Anbieter einzureichen.
Was ist deine Idee?
Wenn Sie ein Objekt hashen möchten, finden Sie heraus, was es einzigartig macht, und verwenden Sie es als Schlüssel. Versuchen Sie nicht, echten Hash zu berechnen oder Hash-Tabellen zu emulieren - dies wird bereits vom zugrunde liegenden JavaScript-Objekt effizient verarbeitet.
Verwenden Sie diesen Schlüssel mit JavaScript
Object
, um die integrierte Hash-Tabelle zu nutzen und mögliche Konflikte mit Standardeigenschaften zu vermeiden.Beispiele für den Einstieg:
Ich habe Ihren Vorschlag verwendet und alle Objekte mit einem Benutzernamen zwischengespeichert. Aber ein weiser Kerl heißt "toString", was eine eingebaute Eigenschaft ist! Was sollte ich jetzt tun?
Wenn es auch nur aus der Ferne möglich ist, dass der resultierende Schlüssel ausschließlich aus lateinischen Zeichen besteht, sollten Sie natürlich etwas dagegen tun. Fügen Sie beispielsweise ein beliebiges nicht-lateinisches Unicode-Zeichen am Anfang oder am Ende hinzu, um die Kollision mit den Standardeigenschaften aufzuheben: "#toString", "#MarySmith". Wenn ein zusammengesetzter Schlüssel verwendet wird, trennen Sie die Schlüsselkomponenten mithilfe eines nicht lateinischen Trennzeichens: "Name, Stadt, Bundesland".
Im Allgemeinen ist dies der Ort, an dem wir kreativ sein und die einfachsten Schlüssel mit bestimmten Einschränkungen auswählen müssen (Eindeutigkeit, mögliche Konflikte mit Standardeigenschaften).
Hinweis: Eindeutige Schlüssel kollidieren per Definition nicht, während potenzielle Hash-Konflikte vom Basiswert behandelt werden
Object
.Warum magst du keine industriellen Lösungen?
IMHO, der beste Code ist überhaupt kein Code: Er hat keine Fehler, erfordert keine Wartung, ist leicht zu verstehen und wird sofort ausgeführt. Alle "Hash-Tabellen in JavaScript", die ich sah, waren> 100 Codezeilen und umfassten mehrere Objekte. Vergleichen Sie es mit :
dict[key] = value
.Ein weiterer Punkt: Ist es überhaupt möglich, die Leistung eines in einer einfachen Sprache geschriebenen Urobjekts zu übertreffen, indem JavaScript und dieselben Urobjekte verwendet werden, um das zu implementieren, was bereits implementiert ist?
Ich möchte meine Objekte immer noch ohne Schlüssel hashen!
Wir haben Glück: ECMAScript 6 (geplant für die Veröffentlichung Mitte 2015, geben oder nehmen Sie 1-2 Jahre danach, um sich zu verbreiten) definiert Karte und Set .
Gemessen an der Definition können sie die Adresse des Objekts als Schlüssel verwenden, wodurch Objekte ohne künstliche Schlüssel sofort unterschieden werden. OTOH, zwei verschiedene, aber identische Objekte, werden als unterschiedlich abgebildet.
Vergleichsaufschlüsselung von MDN :
quelle
Problembeschreibung
JavaScript verfügt über keinen integrierten allgemeinen Kartentyp (manchmal auch als assoziatives Array oder Wörterbuch bezeichnet ), mit dem über beliebige Schlüssel auf beliebige Werte zugegriffen werden kann. Die grundlegende Datenstruktur von JavaScript ist das Objekt , ein spezieller Kartentyp, der nur Zeichenfolgen als Schlüssel akzeptiert und über eine spezielle Semantik wie prototypische Vererbung, Getter und Setter sowie einige weitere Voodoos verfügt.
Wenn Sie Objekte als Zuordnungen verwenden, müssen Sie berücksichtigen, dass der Schlüssel über in einen Zeichenfolgenwert konvertiert wird
toString()
, was zu einer Zuordnung5
und'5'
zu demselben Wert führt, sowie zu allen Objekten, die dietoString()
Methode nicht auf den von indizierten Wert überschreiben'[object Object]'
. Sie können auch unfreiwillig auf die geerbten Eigenschaften zugreifen, wenn Sie dies nicht überprüfenhasOwnProperty()
.Der in JavaScript integrierte Array- Typ hilft kein bisschen: JavaScript-Arrays sind keine assoziativen Arrays, sondern nur Objekte mit einigen besonderen Eigenschaften. Wenn Sie wissen möchten, warum sie nicht als Karten verwendet werden können, klicken Sie hier .
Eugenes Lösung
Eugene Lazutkin hat bereits die Grundidee beschrieben, eine benutzerdefinierte Hash-Funktion zu verwenden, um eindeutige Zeichenfolgen zu generieren, mit denen die zugehörigen Werte als Eigenschaften eines Wörterbuchobjekts nachgeschlagen werden können. Dies ist höchstwahrscheinlich die schnellste Lösung, da Objekte intern als Hash-Tabellen implementiert werden .
Um einen eindeutigen Hashwert für beliebige Objekte zu erhalten, besteht eine Möglichkeit darin, einen globalen Zähler zu verwenden und den Hashwert im Objekt selbst zwischenzuspeichern (z. B. in einer Eigenschaft mit dem Namen
__hash
).Eine Hash-Funktion, die dies tut und sowohl für primitive Werte als auch für Objekte funktioniert, ist:
Diese Funktion kann wie von Eugene beschrieben verwendet werden. Der Einfachheit halber werden wir es weiter in eine
Map
Klasse einwickeln .Meine
Map
ImplementierungDie folgende Implementierung speichert die Schlüssel-Wert-Paare zusätzlich in einer doppelt verknüpften Liste, um eine schnelle Iteration sowohl über Schlüssel als auch über Werte zu ermöglichen. Um Ihre eigene Hash-Funktion bereitzustellen, können Sie die
hash()
Methode der Instanz nach der Erstellung überschreiben .Beispiel
Das folgende Skript
generiert diese Ausgabe:
Weitere Überlegungen
PEZ schlug vor, die
toString()
Methode zu überschreiben , vermutlich mit unserer Hash-Funktion. Dies ist nicht möglich, da es für primitive Werte nicht funktioniert (das ÄnderntoString()
für primitive Werte ist eine sehr schlechte Idee). Wenn wirtoString()
aussagekräftige Werte für beliebige Objekte zurückgeben möchten, müssten wir Änderungen vornehmenObject.prototype
, die einige Leute (ich selbst nicht eingeschlossen) als verboten betrachten .Bearbeiten: Die aktuelle Version meiner
Map
Implementierung sowie andere JavaScript-Extras erhalten Sie hier .quelle
Map._counter = 0
, und im Map-Konstruktor tunthis._hash = 'object ' + Map._counter++
. Dann wird hash ()return (value && value._hash) || (typeof(value) + ' ' + String(value));
Ich weiß, dass diese Frage ziemlich alt ist, aber es gibt heutzutage einige wirklich großartige Lösungen für externe Bibliotheken.
JavaScript hat auch seine Sprache zur Verfügung gestellt
Map
.quelle
Hier ist eine einfache und bequeme Möglichkeit, etwas Ähnliches wie die Java-Karte zu verwenden:
Und um den Wert zu erhalten:
quelle
Gemäß ECMAScript 2015 (ES6) verfügt Standard-Javascript über eine Map-Implementierung. Mehr dazu finden Sie hier
Grundlegende Verwendung:
quelle
Sie können ES6 verwenden
WeakMap
oderMap
:Beachten Sie, dass beides nicht allgemein unterstützt wird, aber Sie können ES6 Shim (erfordert natives ES5 oder ES5 Shim ) zur Unterstützung verwenden
Map
, aber nichtWeakMap
( siehe warum ).quelle
Sie müssten in einigen internen Statuskopplungen von Objekt / Wert-Paaren speichern
Und benutze es als solches:
Natürlich liegt diese Implementierung auch irgendwo in der Richtung von O (n). Die obigen Beispiele von Eugene sind die einzige Möglichkeit, einen Hash zu erhalten, der mit jeder Geschwindigkeit funktioniert, die Sie von einem echten Hash erwarten.
Aktualisieren:
Ein anderer Ansatz im Sinne von Eugenes Antwort besteht darin, allen Objekten eine eindeutige ID zuzuweisen. Einer meiner bevorzugten Ansätze besteht darin, eine der von der Objekt-Superklasse geerbten integrierten Methoden durch ein benutzerdefiniertes Funktions-Passthrough zu ersetzen und Eigenschaften an dieses Funktionsobjekt anzuhängen. Wenn Sie meine HashMap-Methode dazu umschreiben würden, würde dies folgendermaßen aussehen:
Diese Version scheint nur geringfügig schneller zu sein, aber theoretisch wird sie für große Datenmengen erheblich schneller sein.
quelle
Leider war keine der obigen Antworten für meinen Fall gut: Verschiedene Schlüsselobjekte haben möglicherweise denselben Hashcode. Deshalb habe ich eine einfache Java-ähnliche HashMap-Version geschrieben:
Hinweis: Schlüsselobjekte müssen die Methoden hashCode () und equals () "implementieren".
quelle
new Array()
over[]
ist es, die absolute Java-Ähnlichkeit Ihres Codes sicherzustellen? :)Ich habe eine JavaScript-HashMap implementiert, deren Code unter http://github.com/lambder/HashMapJS/tree/master abgerufen werden kann
Hier ist der Code:
quelle
HashMap
s einfügen .In ECMA6 können Sie WeakMap verwenden
Beispiel:
Aber:
quelle
Javascript integriert keine Map / Hashmap. Es sollte assoziatives Array genannt werden .
hash["X"]
ist gleichhash.X
, erlaubt aber "X" als Stringvariable. Mit anderen Worten,hash[x]
ist funktional gleicheval("hash."+x.toString())
Es ähnelt eher object.properties als der Schlüsselwertzuordnung. Wenn Sie nach einer besseren Schlüssel- / Wertzuordnung in Javascript suchen, verwenden Sie bitte das Map-Objekt, das Sie im Web finden.
quelle
Probieren Sie die Implementierung meiner JavaScript-Hash-Tabelle aus: http://www.timdown.co.uk/jshashtable
Es wird nach einer hashCode () -Methode für Schlüsselobjekte gesucht, oder Sie können beim Erstellen eines Hashtable-Objekts eine Hashing-Funktion angeben.
quelle
Dies scheint eine ziemlich robuste Lösung zu sein: https://github.com/flesler/hashmap . Es funktioniert sogar gut für Funktionen und Objekte, die identisch aussehen. Der einzige Hack, den es verwendet, ist das Hinzufügen eines obskuren Mitglieds zu einem Objekt, um es zu identifizieren. Wenn Ihr Programm diese obskure Variable nicht überschreibt (es ist so etwas wie Hashid ), sind Sie golden.
quelle
Wenn die Leistung nicht kritisch ist (zB die Höhe der Tasten relativ klein ist ) , und Sie wollen nicht Ihre (oder vielleicht nicht Ihre) Objekte mit zusätzlichen Feldern wie verschmutzen
_hash
,_id
etc., dann kann man sich die Tatsache zunutze machen , dassArray.prototype.indexOf
beschäftigt strenge Gleichheit. Hier ist eine einfache Implementierung:Anwendungsbeispiel:
Im Vergleich zu ES6 WeakMap gibt es zwei Probleme: O (n) Suchzeit und Nichtschwäche (dh es kommt zu einem Speicherverlust, wenn Sie keine Schlüssel verwenden
delete
oderclear
freigeben).quelle
Meine Kartenimplementierung, abgeleitet von Christophs Beispiel:
Anwendungsbeispiel:
quelle
Eine weitere Lösung hinzufügen: Es
HashMap
ist so ziemlich die erste Klasse, die ich von Java nach Javascript portiert habe. Man könnte sagen, es gibt viel Overhead, aber die Implementierung entspricht fast 100% der Java-Implementierung und umfasst alle Schnittstellen und Unterklassen.Das Projekt finden Sie hier: https://github.com/Airblader/jsava Ich werde auch den (aktuellen) Quellcode für die HashMap-Klasse anhängen, aber wie angegeben hängt es auch von der Superklasse usw. ab. Das verwendete OOP-Framework ist qooxdoo.
Bearbeiten: Bitte beachten Sie, dass dieser Code bereits veraltet ist und beziehen Sie sich auf das Github-Projekt für die aktuelle Arbeit. Zum Zeitpunkt des Schreibens gibt es auch eine
ArrayList
Implementierung.quelle
Noch eine Kartenimplementierung von mir. Mit Randomizer, 'Generics' und 'Iterator' =)
Beispiel:
quelle