JavaScript-Hashmap-Äquivalent

Question

Wie bereits in Update 3 über diese Antwort diese Notation:

var hash = {};
hash[X]

das Objekt nicht wirklich hasht X ; es wandelt eigentlich nur um X zu einer Zeichenkette (über .toString() wenn es sich um ein Objekt handelt, oder einige andere eingebaute Konvertierungen für verschiedene primitive Typen) und sucht dann diese Zeichenkette, ohne sie zu hashen, in " hash ". Auch die Objektgleichheit wird nicht überprüft - wenn zwei verschiedene Objekte die gleiche Stringkonvertierung haben, überschreiben sie sich einfach gegenseitig.

Angesichts dieser - gibt es eine effiziente Implementierungen von Hashmaps in JavaScript?

(Zum Beispiel, das zweite Google-Ergebnis von javascript hashmap führt zu einer Implementierung, die für jede Operation O(n) ist. Verschiedene andere Ergebnisse ignorieren die Tatsache, dass verschiedene Objekte mit äquivalenten Zeichenkettendarstellungen sich gegenseitig überschreiben.

Answer 1

Verschlüsseln Sie Ihre Objekte selbst manuell und verwenden Sie die resultierenden Zeichenketten als Schlüssel für ein normales JavaScript-Wörterbuch. Schließlich sind Sie in der besten Position, um zu wissen, was Ihre Objekte einzigartig macht. Das ist es, was ich tue.

Beispiel:

var key = function(obj){
  // Some unique object-dependent key
  return obj.totallyUniqueEmployeeIdKey; // Just an example
};

var dict = {};

dict[key(obj1)] = obj1;
dict[key(obj2)] = obj2;

Auf diese Weise können Sie die Indizierung durch JavaScript ohne schweres Heben der Speicherzuweisung und Überlaufbehandlung steuern.

Natürlich, wenn Sie wirklich wollen, dass die "Industrie-grade-Lösung", können Sie eine Klasse parametrisiert durch den Schlüssel-Funktion, und mit allen notwendigen API des Containers, aber wir verwenden JavaScript, und versuchen, einfach und leichtgewichtig zu sein, so dass 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 einer Reihe 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-Kodierung o DojoX UUID . Während die letztgenannten Lösungen eindeutige Schlüssel erzeugen können, versuche ich persönlich, sie um jeden Preis zu vermeiden, vor allem, wenn ich weiß, was meine Objekte einzigartig macht.

Aktualisierung im Jahr 2014: Diese einfache Lösung wurde bereits 2008 beantwortet und bedarf noch immer weiterer Erklärungen. Lassen Sie mich die Idee in Form von Fragen und Antworten erläutern.

Ihre Lösung hat keine echte Raute. Wo ist er?

JavaScript ist eine Hochsprache. Ihre grundlegenden Primitive ( Objekt ) enthält eine Hash-Tabelle zum Speichern von Eigenschaften. Diese Hash-Tabelle wird aus Effizienzgründen normalerweise in einer Low-Level-Sprache geschrieben. Durch die Verwendung eines einfachen Objekts mit String-Schlüsseln nutzen wir eine effizient implementierte Hash-Tabelle ohne jeglichen Aufwand unsererseits.

Woher wissen Sie, dass sie eine Raute verwenden?

Es gibt drei wesentliche Möglichkeiten, eine Sammlung von Objekten über einen Schlüssel adressierbar zu halten:

• Ungeordnet. In diesem Fall müssen wir, um ein Objekt anhand seines Schlüssels zu finden, alle Schlüssel durchgehen und anhalten, wenn wir es gefunden haben. Im Durchschnitt werden n/2 Vergleiche benötigt.
• Bestellt.
  • Beispiel 1: ein sortiertes Array - mit einer binären Suche finden wir unseren Schlüssel im Durchschnitt nach ~log2(n) Vergleichen. Viel besser.
  • Beispiel #2: ein Baum. Wieder werden es ~log(n) Versuche sein.
• Hash-Tabelle. Im Durchschnitt benötigt sie eine konstante Zeit. Vergleiche: O(n) vs. O(log n) vs. O(1). Aufschwung.

Offensichtlich verwenden JavaScript-Objekte Hash-Tabellen in irgendeiner Form, um allgemeine Fälle zu behandeln.

Verwenden Browser-Anbieter wirklich Hash-Tabellen?

Wirklich.

• Chrome/node.js/ V8 : JSObject . Suche nach NameDictionary y NameDictionaryShape mit einschlägigen Details in Objekte.cc y objekte-inl.h .
• Firefox/ Gecko : JSObject , NativeObject und PlainObject mit sachdienlichen Hinweisen in jsobj.cpp y vm/NativeObject.cpp .

Können sie Kollisionen bewältigen?

Ja. Siehe oben. Wenn Sie eine Kollision bei ungleichen Zeichenketten gefunden haben, zögern Sie bitte nicht, einen Fehler bei einem Anbieter zu melden.

Was ist also Ihre Idee?

Wenn Sie ein Objekt mit einem Hash versehen wollen, müssen Sie herausfinden, was es einzigartig macht, und es als Schlüssel verwenden. Versuchen Sie nicht, einen echten Hash zu berechnen oder Hash-Tabellen zu emulieren - das zugrundeliegende JavaScript-Objekt erledigt das bereits effizient.

Verwenden Sie diesen Schlüssel mit der JavaScript-Funktion Object um die eingebaute Hashtabelle zu nutzen und gleichzeitig mögliche Konflikte mit Standardeigenschaften zu vermeiden.

Beispiele für den Anfang:

• Wenn Ihre Objekte einen eindeutigen Benutzernamen enthalten, verwenden Sie diesen als Schlüssel.
• Wenn sie eine eindeutige Kundennummer enthält, verwenden Sie diese als Schlüssel.
  • Wenn sie eindeutige, von der Regierung vergebene Nummern enthält, wie US SSNs oder eine Reisepassnummer, und Ihr System lässt keine Duplikate zu - verwenden Sie sie als Schlüssel.
• Wenn eine Kombination von Feldern eindeutig ist, verwenden Sie sie als Schlüssel.
  • Die Abkürzung des US-Bundesstaates + Führerscheinnummer ergibt einen hervorragenden Schlüssel.
  • Länderkürzel + Passnummer ist auch ein ausgezeichneter Schlüssel.
• Einige Funktionen für Felder oder ein ganzes Objekt können einen eindeutigen Wert zurückgeben - verwenden Sie ihn als Schlüssel.

Ich habe Ihren Vorschlag befolgt und alle Objekte unter Verwendung eines Benutzernamens im Cache gespeichert. Aber ein Schlauberger heißt "toString", was eine eingebaute Eigenschaft ist! Was soll ich jetzt tun?

Wenn es auch nur im Entferntesten möglich ist, dass der resultierende Schlüssel ausschließlich aus lateinischen Buchstaben besteht, sollten Sie natürlich etwas dagegen tun. Fügen Sie zum Beispiel ein beliebiges nicht-lateinisches Unicode-Zeichen am Anfang oder am Ende ein, um einen Konflikt mit den Standardeigenschaften zu vermeiden: "#toString", "#MarySmith". Wenn ein zusammengesetzter Schlüssel verwendet wird, trennen Sie die Schlüsselkomponenten mit einem nicht-lateinischen Trennzeichen: "Name,Stadt,Bundesland".

Im Allgemeinen ist dies der Ort, an dem wir kreativ sein und die einfachsten Schlüssel mit den gegebenen Einschränkungen (Eindeutigkeit, potenzielle Konflikte mit Standardeigenschaften) auswählen müssen.

Hinweis: Eindeutige Schlüssel kollidieren nicht per Definition, während mögliche Hash-Kollisionen von der zugrunde liegenden Object .

Warum gefallen Ihnen die industriellen Lösungen nicht?

IMHO ist der beste Code überhaupt kein Code: er ist fehlerfrei, erfordert keine Wartung, ist leicht verständlich und wird sofort ausgeführt. Alle "Hashtabellen in JavaScript", die ich gesehen habe, bestanden aus mehr als 100 Zeilen Code und umfassten mehrere Objekte. Vergleichen Sie das mit: dict[key] = value .

Ein weiterer Punkt: Ist es überhaupt möglich, die Leistung eines in einer Niedrigsprache geschriebenen Urobjekts zu übertreffen, indem man JavaScript und dieselben Urobjekte verwendet, 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 (veröffentlicht im Juni 2015) definiert Karte y einstellen. .

Nach der Definition zu urteilen, können sie die Adresse eines Objekts als Schlüssel verwenden, was Objekte ohne künstliche Schlüssel sofort unterscheidbar macht. OTOH, zwei verschiedene, aber identische Objekte, werden als unterschiedlich abgebildet werden.

Aufschlüsselung des Vergleichs von MDN :

Objekte ähneln Maps insofern, als dass man mit beiden Schlüsseln Werte festlegen kann, diese Werte abrufen, Schlüssel löschen und feststellen, ob etwas unter einem unter einem Schlüssel gespeichert ist. Aus diesem Grund (und weil es keine eingebauten Alternativen gab), wurden Objects in der Vergangenheit als Maps verwendet; allerdings gibt es jedoch wichtige Unterschiede, die die Verwendung einer Map in folgenden Fällen vorteilhafter machen bestimmten Fällen vorzuziehen:

• Die Schlüssel eines Objekts sind Zeichenketten und Symbole, während sie bei einer Karte jeder Wert sein können, einschließlich Funktionen, Objekte und beliebige Primitive.
• Die Schlüssel in Map sind geordnet, während die zum Objekt hinzugefügten Schlüssel nicht geordnet sind. Wenn man also über ein Map-Objekt iteriert, werden die Schlüssel in der Reihenfolge der Einfügung zurück.
• Die Größe einer Karte lässt sich leicht mit der Eigenschaft size ermitteln, während die Anzahl der Eigenschaften eines Objekts manuell bestimmt werden muss.
• Eine Map ist eine Iterable und kann daher direkt iteriert werden, während die Iteration über ein Objekt erfordert, dass man seine Schlüssel auf irgendeine Weise erhält und über sie zu iterieren.
• Ein Objekt hat einen Prototyp, d.h. es gibt Standardschlüssel in der Map, die mit Ihren Schlüsseln kollidieren können, wenn Sie nicht vorsichtig sind. Ab ES5 kann dies map = Object.create(null) umgangen werden, aber das wird nur selten gemacht.
• Eine Map kann in Szenarien, in denen häufig Schlüsselpaare hinzugefügt und entfernt werden, besser funktionieren.

Answer 2

Beschreibung des Problems

JavaScript hat keine eingebauten allgemeinen Karte Typ (manchmal auch vereinigende Reihe ou Wörterbuch ), die den Zugriff auf beliebige Werte über beliebige Schlüssel ermöglicht. Die grundlegende Datenstruktur von JavaScript ist die Objekt ein spezieller Typ von Map, der nur Zeichenketten als Schlüssel akzeptiert und eine spezielle Semantik wie prototypische Vererbung, Getter und Setter und weiteres Voodoo hat.

Wenn Sie Objekte als Maps verwenden, müssen Sie daran denken, dass der Schlüssel in einen Zeichenkettenwert umgewandelt wird über toString() , was zu einer Abbildung 5 y '5' auf denselben Wert gesetzt und alle Objekte, die nicht die toString() Methode auf den Wert, der durch '[object Object]' . Sie könnten auch ungewollt auf die geerbten Eigenschaften zugreifen, wenn Sie nicht die Option hasOwnProperty() .

Die in JavaScript eingebaute Array Typs ist nicht gerade hilfreich: JavaScript-Arrays sind keine assoziativen Arrays, sondern einfach nur Objekte mit ein paar weiteren speziellen Eigenschaften. Wenn Sie wissen wollen, warum sie nicht als Maps verwendet werden können, siehe hier .

Eugene's Lösung

Eugene Lazutkin beschrieb bereits die Grundidee, eine benutzerdefinierte Hash-Funktion zu verwenden, um eindeutige Zeichenfolgen zu erzeugen, die zum Nachschlagen der zugehörigen Werte als Eigenschaften eines Wörterbuchobjekts verwendet werden können. Dies wird höchstwahrscheinlich die schnellste Lösung sein, da Objekte intern implementiert sind als Hash-Tabellen .

• Anmerkung: Hash-Tabellen (manchmal auch Hash-Karten ) sind eine besondere Umsetzung des Map-Konzepts unter Verwendung eines Backing-Arrays und der Suche über numerische Hash-Werte. Die Laufzeitumgebung kann andere Strukturen verwenden (z.B. Suchbäume ou Überspringungslisten ), um JavaScript-Objekte zu implementieren, aber da Objekte die grundlegende Datenstruktur sind, sollten sie ausreichend optimiert sein.

Um einen eindeutigen Hash-Wert für beliebige Objekte zu erhalten, besteht eine Möglichkeit darin, einen globalen Zähler zu verwenden und den Hash-Wert im Objekt selbst zwischenzuspeichern (zum Beispiel in einer Eigenschaft namens __hash ).

Eine Hash-Funktion, die dies tut und sowohl für primitive Werte als auch für Objekte funktioniert, ist:

function hash(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
}

hash.current = 0;

Diese Funktion kann wie von Eugene beschrieben verwendet werden. Der Einfachheit halber verpacken wir sie zusätzlich in eine Map Klasse.

Meine Map Umsetzung

Die folgende Implementierung speichert die Schlüssel-Wert-Paare zusätzlich in einer doppelt verknüpften Liste, um eine schnelle Iteration über Schlüssel und Werte zu ermöglichen. Um Ihre eigene Hash-Funktion bereitzustellen, können Sie die Instanz überschreiben hash() Methode nach der Erstellung.

// Linking the key-value-pairs is optional.
// If no argument is provided, linkItems === undefined, i.e. !== false
// --> linking will be enabled
function Map(linkItems) {
    this.current = undefined;
    this.size = 0;

    if(linkItems === false)
        this.disableLinking();
}

Map.noop = function() {
    return this;
};

Map.illegal = function() {
    throw new Error("illegal operation for maps without linking");
};

// Map initialisation from an existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
    var map = new Map;

    for(var prop in obj) {
        if(foreignKeys || obj.hasOwnProperty(prop))
            map.put(prop, obj[prop]);
    }

    return map;
};

Map.prototype.disableLinking = function() {
    this.link = Map.noop;
    this.unlink = Map.noop;
    this.disableLinking = Map.noop;
    this.next = Map.illegal;
    this.key = Map.illegal;
    this.value = Map.illegal;
    this.removeAll = Map.illegal;

    return this;
};

// Overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
};

Map.prototype.hash.current = 0;

// --- Mapping functions

Map.prototype.get = function(key) {
    var item = this[this.hash(key)];
    return item === undefined ? undefined : item.value;
};

Map.prototype.put = function(key, value) {
    var hash = this.hash(key);

    if(this[hash] === undefined) {
        var item = { key : key, value : value };
        this[hash] = item;

        this.link(item);
        ++this.size;
    }
    else this[hash].value = value;

    return this;
};

Map.prototype.remove = function(key) {
    var hash = this.hash(key);
    var item = this[hash];

    if(item !== undefined) {
        --this.size;
        this.unlink(item);

        delete this[hash];
    }

    return this;
};

// Only works if linked
Map.prototype.removeAll = function() {
    while(this.size)
        this.remove(this.key());

    return this;
};

// --- Linked list helper functions

Map.prototype.link = function(item) {
    if(this.size == 0) {
        item.prev = item;
        item.next = item;
        this.current = item;
    }
    else {
        item.prev = this.current.prev;
        item.prev.next = item;
        item.next = this.current;
        this.current.prev = item;
    }
};

Map.prototype.unlink = function(item) {
    if(this.size == 0)
        this.current = undefined;
    else {
        item.prev.next = item.next;
        item.next.prev = item.prev;
        if(item === this.current)
            this.current = item.next;
    }
};

// --- Iterator functions - only work if map is linked

Map.prototype.next = function() {
    this.current = this.current.next;
};

Map.prototype.key = function() {
    return this.current.key;
};

Map.prototype.value = function() {
    return this.current.value;
};

Beispiel

Das folgende Skript,

var map = new Map;

map.put('spam', 'eggs').
    put('foo', 'bar').
    put('foo', 'baz').
    put({}, 'an object').
    put({}, 'another object').
    put(5, 'five').
    put(5, 'five again').
    put('5', 'another five');

for(var i = 0; i++ < map.size; map.next())
    document.writeln(map.hash(map.key()) + ' : ' + map.value());

erzeugt diese Ausgabe:

string spam : eggs
string foo : baz
object 1 : an object
object 2 : another object
number 5 : five again
string 5 : another five

Weitere Überlegungen

PEZ vorgeschlagen zum Überschreiben der toString() Methode, vermutlich mit unserer Hash-Funktion. Dies ist nicht machbar, da es nicht für primitive Werte funktioniert (Ändern toString() für Primitive ist eine sehr schlechte Idee). Wenn wir wollen toString() um sinnvolle Werte für beliebige Objekte zurückzugeben, müssten wir die Object.prototype was einige Leute (mich nicht eingeschlossen) als verboten .

---

Die aktuelle Version meiner Map Implementierung sowie andere JavaScript-Goodies kann hier bezogen werden .

Answer 3

Heutzutage gibt es einige wirklich gute Lösungen mit externen Bibliotheken:

• collections.js
• Unveränderlich.js

JavaScript hat auch seine spracheigene Map auch.

• Karte

Answer 4

Gemäß ECMAScript 2015 (ES6) verfügt das Standard-JavaScript über eine Map-Implementierung. Mehr darüber kann gefunden werden aquí .

Grundlegende Verwendung:

var myMap = new Map();
var keyString = "a string",
    keyObj = {},
    keyFunc = function () {};

// Setting the values
myMap.set(keyString, "value associated with 'a string'");
myMap.set(keyObj, "value associated with keyObj");
myMap.set(keyFunc, "value associated with keyFunc");

myMap.size; // 3

// Getting the values
myMap.get(keyString);    // "value associated with 'a string'"
myMap.get(keyObj);       // "value associated with keyObj"
myMap.get(keyFunc);      // "value associated with keyFunc"

Answer 5

Hier ist eine einfache und bequeme Möglichkeit, etwas Ähnliches wie die Java-Karte zu verwenden:

var map = {
              'map_name_1': map_value_1,
              'map_name_2': map_value_2,
              'map_name_3': map_value_3,
              'map_name_4': map_value_4
          }

Und um den Wert zu erhalten:

alert(map['map_name_1']);    // Gives the value of map_value_1

... etc. ...