webentwicklung-frage-antwort-db.com.de

JavaScript-Hashmap-Äquivalent

Wie in Update 3 am diese Antwort verdeutlicht, lautet diese Notation:

_var hash = {};
hash[X]
_

hasht das Objekt nicht wirklich X; es konvertiert tatsächlich nur X in einen String (über .toString(), wenn es sich um ein Objekt handelt, oder einige andere eingebaute Konvertierungen für verschiedene primitive Typen) und sucht dann diesen String, ohne ihn zu haschen, in "hash". Die Objektgleichheit wird ebenfalls nicht überprüft. Wenn zwei verschiedene Objekte dieselbe Zeichenfolgenkonvertierung haben, überschreiben sie sich gegenseitig.

In Anbetracht dessen - gibt es effiziente Implementierungen von Hashmaps in Javascript? (Zum Beispiel liefert das 2. Google-Ergebnis von javascript hashmap eine Implementierung, die O(n) für jede Operation ist. Verschiedene andere Ergebnisse ignorieren die Tatsache, dass unterschiedliche Objekte mit äquivalente Zeichenfolgendarstellungen überschreiben sich gegenseitig.

312
Claudiu

Warum hashen Sie Ihre Objekte nicht manuell und verwenden die resultierenden Zeichenfolgen als Schlüssel für ein reguläres JavaScript-Wörterbuch? Schließlich wissen Sie am besten, was Ihre Objekte einzigartig macht. Das ist, 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 steuern, ohne die Speicherzuweisung und die Überlaufbehandlung zu beeinträchtigen.

Natürlich können Sie, wenn Sie wirklich die "Industrielösung" wollen, eine Klasse erstellen, die durch die Schlüsselfunktion und mit allen erforderlichen APIs des Containers parametrisiert ist, 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 das Auswählen 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 gemeinsam eindeutig sind, oder so komplex wie das Verwenden einiger kryptografischer Hashes wie in DojoX-Codierung oder DojoX-UUID . Während die letztgenannten Lösungen möglicherweise eindeutige Schlüssel erzeugen, versuche ich persönlich, diese um jeden Preis zu vermeiden, insbesondere, wenn ich weiß, was meine Objekte einzigartig macht.

Update 2014: Diese einfache Lösung, die bereits 2008 beantwortet wurde, bedarf noch weiterer Erläuterungen. Lassen Sie mich die Idee in einem Frage- und Antwortformular erläutern.

Ihre Lösung hat keinen echten Hash. Wo ist es???

JavaScript ist eine Hochsprache. Das Grundelement ( Object ) enthält eine Hash-Tabelle, um die Eigenschaften beizubehalten. Diese Hash-Tabelle wird aus Effizienzgründen normalerweise in einer einfachen Sprache geschrieben. Unter Verwendung eines einfachen Objekts mit Zeichenfolgenschlüsseln verwenden wir eine effizient implementierte Hash-Tabelle, ohne dass unser Aufwand dafür erforderlich ist.

Woher wissen Sie, dass sie Hash verwenden?

Es gibt drei Möglichkeiten, eine Sammlung von Objekten mit einem Schlüssel adressierbar zu halten:

  • Ungeordnet. In diesem Fall müssen wir, um ein Objekt anhand seines Schlüssels abzurufen, alle Schlüssel durchgehen, die anhalten, wenn wir es finden. Im Durchschnitt dauert es n/2 Vergleiche.
  • Bestellt.
    • Beispiel # 1: Ein sortiertes Array - bei 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 es eine konstante Zeit. Vergleiche: O(n) vs. O (log n) vs. O (1). Boom.

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.

Also, was ist deine Idee?

Wenn Sie ein Objekt hashen möchten, suchen Sie, was es einzigartig macht, und verwenden Sie es als Schlüssel. Versuchen Sie nicht, einen echten Hash zu berechnen oder Hash-Tabellen zu emulieren - dieser 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 den Standardeigenschaften zu vermeiden.

Beispiele für den Einstieg:

  • Wenn Ihre Objekte einen eindeutigen Benutzernamen enthalten, verwenden Sie diesen als Schlüssel.
  • Wenn es eine eindeutige Kundennummer enthält, verwenden Sie diese als Schlüssel.
    • Wenn es eindeutige, von der Regierung herausgegebene Nummern wie eine SSN oder eine Passnummer enthält und Ihr System keine Duplikate zulässt, verwenden Sie es als Schlüssel.
  • Wenn eine Kombination von Feldern eindeutig ist, verwenden Sie sie als Schlüssel.
    • Staatliche Abkürzung + Führerscheinnummer ist ein ausgezeichneter Schlüssel.
    • Länderkürzel + Passnummer sind ebenfalls 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 verwendet und alle Objekte mit einem Benutzernamen zwischengespeichert. Aber ein weiser Typ heißt "toString", was eine eingebaute Eigenschaft ist! Was sollte ich jetzt tun?

Wenn es sogar remote möglich ist, dass der resultierende Schlüssel ausschließlich aus lateinischen Zeichen besteht, sollten Sie offensichtlich etwas dagegen tun. Fügen Sie beispielsweise ein beliebiges nicht-lateinisches Unicode-Zeichen am Anfang oder am Ende hinzu, um die Überschneidung mit den Standardeigenschaften aufzuheben: "#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 bestimmten Einschränkungen auswählen müssen (Eindeutigkeit, mögliche Konflikte mit den Standardeigenschaften).

Hinweis: Eindeutige Schlüssel kollidieren nicht per Definition, während potenzielle Hash-Konflikte vom zugrunde liegenden Object behandelt werden.

Warum mögen Sie keine industriellen Lösungen?

IMHO, der beste Code ist überhaupt kein Code: Er enthält 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, eine Leistung eines in einer einfachen Sprache geschriebenen primordialen Objekts zu übertreffen, indem JavaScript und dieselben primordialen Objekte verwendet werden, um das zu implementieren, was bereits implementiert ist?

Ich möchte meine Objekte immer noch ohne Schlüssel hacken!

Wir haben Glück: ECMAScript 6 (voraussichtlich Mitte 2015, 1-2 Jahre später verfügbar) definiert map 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 voneinander unterschieden werden. OTOH, zwei verschiedene, aber identische Objekte, werden als unterschiedliche Objekte abgebildet.

Vergleichsaufschlüsselung von MDN :

Objekte ähneln Maps dahingehend, dass Sie mit beiden Schlüsseln Werte festlegen, diese Werte abrufen, Schlüssel löschen und feststellen können, ob auf einem Schlüssel etwas gespeichert ist. Aus diesem Grund (und weil es keine eingebauten Alternativen gab) wurden Objekte historisch als Karten verwendet. Es gibt jedoch wichtige Unterschiede, die die Verwendung einer Karte in bestimmten Fällen vorziehen:

  • Die Schlüssel eines Objekts sind Zeichenfolgen und Symbole, während sie für eine Map einen beliebigen Wert haben können, einschließlich Funktionen, Objekten und beliebigen Grundelementen.
  • Die Schlüssel in Map sind geordnet, die zum Objekt hinzugefügten nicht. Wenn Sie also darüber iterieren, gibt ein Map-Objekt die Schlüssel in der Reihenfolge ihrer Einfügung zurück.
  • Mit der Eigenschaft size können Sie die Größe einer Karte auf einfache Weise ermitteln, während die Anzahl der Eigenschaften in einem Objekt manuell festgelegt werden muss.
  • Eine Map ist ein iterierbares Objekt und kann daher direkt iteriert werden, wohingegen das Iterieren über ein Objekt das Erhalten seiner Schlüssel in gewisser Weise und das Iterieren über sie erfordert.
  • Ein Objekt hat einen Prototyp, daher gibt es Standardschlüssel in der Map, die mit Ihren Schlüsseln kollidieren können, wenn Sie nicht vorsichtig sind. Ab ES5 kann dies mit map = Object.create (null) umgangen werden, dies wird jedoch selten durchgeführt.
  • Eine Karte kann in Szenarien, in denen häufig Schlüsselpaare hinzugefügt oder entfernt werden, eine bessere Leistung erbringen.
317
Eugene Lazutkin

Problembeschreibung

JavaScript hat keinen eingebauten allgemeinen map -Typ (manchmal assoziatives Array oder Wörterbuch genannt), der den Zugriff auf beliebige Werte mit beliebigen Schlüsseln ermöglicht. Die grundlegende Datenstruktur von JavaScript ist object, ein spezieller Kartentyp, der nur Zeichenfolgen als Schlüssel akzeptiert und spezielle Semantiken wie prototypische Vererbung, Getter und Setter sowie einige weitere Voodoos aufweist.

Wenn Sie Objekte als Zuordnungen verwenden, müssen Sie beachten, dass der Schlüssel über toString() in einen Zeichenfolgenwert konvertiert wird, was dazu führt, dass 5 und '5' demselben Wert und allen Objekten zugeordnet werden, die Überschreiben Sie die Methode toString() nicht mit dem von '[object Object]' indizierten Wert. Sie können auch ungewollt auf die geerbten Eigenschaften zugreifen, wenn Sie hasOwnProperty() nicht aktivieren.

Der integrierte JavaScript-Typ array hilft nicht weiter: JavaScript-Arrays sind keine assoziativen Arrays, sondern nur Objekte mit ein paar besonderen Eigenschaften. Wenn Sie wissen möchten, warum sie nicht als Karten verwendet werden können, siehe hier .

Eugenes Lösung

Eugene Lazutkin hat bereits die Grundidee beschrieben, mithilfe einer benutzerdefinierten Hash-Funktion eindeutige Zeichenfolgen zu generieren, mit denen die zugehörigen Werte als Eigenschaften eines Dictionary-Objekts nachgeschlagen werden können. Dies ist höchstwahrscheinlich die schnellste Lösung, da Objekte intern als Hash-Tabellen implementiert werden.

  • Hinweis: Hash-Tabellen (manchmal auch als Hash-Maps bezeichnet) sind eine spezielle Implementierung des Map-Konzepts unter Verwendung eines Backing-Arrays und der Suche über numerische Hashwerte. Die Laufzeitumgebung verwendet möglicherweise andere Strukturen (z. B. Suchbäume oder Überspringen von Listen), um JavaScript-Objekte zu implementieren. Da Objekte jedoch die grundlegende Datenstruktur darstellen, sollten sie ausreichend optimiert werden.

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 (z. B. in einer Eigenschaft namens __hash).

Eine Hash-Funktion, die dies sowohl für Grundwerte als auch für Objekte ausführt und 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 werden wir es in eine Klasse Map einbinden.

Meine Map Implementierung

Die 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 Methode hash() der Instanz nach der Erstellung überschreiben.

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

generiert 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 schlug vor, die Methode toString() zu überschreiben, vermutlich mit unserer Hash-Funktion. Dies ist nicht machbar, da es für primitive Werte nicht funktioniert (das Ändern von toString() für primitive Werte ist eine sehr schlechte Idee). Wenn wir möchten, dass toString() sinnvolle Werte für beliebige Objekte zurückgibt, müssten wir Object.prototype ändern, was einige Leute (ich selbst nicht eingeschlossen) als verboten betrachten.


Bearbeiten: Die aktuelle Version meiner Map -Implementierung sowie andere JavaScript-Extras hier erhältlich .

170
Christoph

Ich weiß, dass diese Frage ziemlich alt ist, aber es gibt heutzutage einige wirklich gute Lösungen für externe Bibliotheken.

JavaScript hat auch die Sprache Map zur Verfügung gestellt.

42
Jamel Toms

Hier ist eine einfache und bequeme Möglichkeit, etwas zu verwenden, das der Java-Map ähnelt:

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 bekommen:

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

......  etc  .....
26
Miloš

Sie können ES6 WeakMap oder Map verwenden:

  • WeakMaps sind Schlüssel-/Wertzuordnungen, in denen Schlüssel Objekte sind.

  • Map-Objekte sind einfache Schlüssel-/Wertzuordnungen. Jeder Wert (sowohl Objekte als auch Grundwerte) kann entweder als Schlüssel oder als Wert verwendet werden.

Beachten Sie, dass keines von beiden allgemein unterstützt wird, aber Sie können ES6 Shim (erfordert natives ES5 oder ES5 Shim ) verwenden, um Map zu unterstützen, aber nicht WeakMap ( siehe warum) ).

19
Oriol

Gemäß dem ECMAScript 2015 (ES6) -Standard verfügt Javascript über eine Map-Implementierung. Mehr darüber finden Sie hier

Grundsätzliche 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"
18

Sie müssten in einigen internen Zustandskopplungen von Objekt/Wert-Paaren speichern

HashMap = function(){
  this._dict = [];
}
HashMap.prototype._get = function(key){
  for(var i=0, couplet; couplet = this._dict[i]; i++){
    if(couplet[0] === key){
      return couplet;
    }
  }
}
HashMap.prototype.put = function(key, value){
  var couplet = this._get(key);
  if(couplet){
    couplet[1] = value;
  }else{
    this._dict.Push([key, value]);
  }
  return this; // for chaining
}
HashMap.prototype.get = function(key){
  var couplet = this._get(key);
  if(couplet){
    return couplet[1];
  }
}

Und benutze es als solches:

var color = {}; // unique object instance
var shape = {}; // unique object instance
var map = new HashMap();
map.put(color, "blue");
map.put(shape, "round");
console.log("Item is", map.get(color), "and", map.get(shape));

Natürlich ist 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 würden.

pdate:

Ein anderer Ansatz in Anlehnung an Eugenes Antwort besteht darin, allen Objekten eine eindeutige ID zuzuweisen. Einer meiner bevorzugten Ansätze besteht darin, eine der von der Object-Superklasse geerbten integrierten Methoden zu verwenden, sie durch ein benutzerdefiniertes Funktions-Passthrough zu ersetzen und Eigenschaften an dieses Funktionsobjekt anzuhängen. Wenn Sie dazu meine HashMap-Methode neu schreiben würden, würde dies folgendermaßen aussehen:

HashMap = function(){
  this._dict = {};
}
HashMap.prototype._shared = {id: 1};
HashMap.prototype.put = function put(key, value){
  if(typeof key == "object"){
    if(!key.hasOwnProperty._id){
      key.hasOwnProperty = function(key){
        return Object.prototype.hasOwnProperty.call(this, key);
      }
      key.hasOwnProperty._id = this._shared.id++;
    }
    this._dict[key.hasOwnProperty._id] = value;
  }else{
    this._dict[key] = value;
  }
  return this; // for chaining
}
HashMap.prototype.get = function get(key){
  if(typeof key == "object"){
    return this._dict[key.hasOwnProperty._id];
  }
  return this._dict[key];
}

Diese Version scheint nur geringfügig schneller zu sein, theoretisch ist sie jedoch für große Datenmengen erheblich schneller.

13
pottedmeat

Leider war keine der obigen Antworten für meinen Fall gut: Verschiedene Schlüsselobjekte haben möglicherweise den gleichen Hash-Code. Deshalb habe ich eine einfache Java-ähnliche HashMap-Version geschrieben:

function HashMap() {
    this.buckets = {};
}

HashMap.prototype.put = function(key, value) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        bucket = new Array();
        this.buckets[hashCode] = bucket;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            bucket[i].value = value;
            return;
        }
    }
    bucket.Push({ key: key, value: value });
}

HashMap.prototype.get = function(key) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        return null;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            return bucket[i].value;
        }
    }
}

HashMap.prototype.keys = function() {
    var keys = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            keys.Push(bucket[i].key);
        }
    }
    return keys;
}

HashMap.prototype.values = function() {
    var values = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            values.Push(bucket[i].value);
        }
    }
    return values;
}

Hinweis: Schlüsselobjekte müssen die Methoden hashCode () und equals () "implementieren".

11
Michael Spector

Ich habe eine JavaScript-HashMap implementiert, deren Code unter http://github.com/lambder/HashMapJS/tree/master abgerufen werden kann

Hier ist der Code:

/*
 =====================================================================
 @license MIT
 @author Lambder
 @copyright 2009 Lambder.
 @end
 =====================================================================
 */
var HashMap = function() {
  this.initialize();
}

HashMap.prototype = {
  hashkey_prefix: "<#HashMapHashkeyPerfix>",
  hashcode_field: "<#HashMapHashkeyPerfix>",

  initialize: function() {
    this.backing_hash = {};
    this.code = 0;
  },
  /*
   maps value to key returning previous assocciation
   */
  put: function(key, value) {
    var prev;
    if (key && value) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        prev = this.backing_hash[hashCode];
      } else {
        this.code += 1;
        hashCode = this.hashkey_prefix + this.code;
        key[this.hashcode_field] = hashCode;
      }
      this.backing_hash[hashCode] = value;
    }
    return prev;
  },
  /*
   returns value associated with given key
   */
  get: function(key) {
    var value;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        value = this.backing_hash[hashCode];
      }
    }
    return value;
  },
  /*
   deletes association by given key.
   Returns true if the assocciation existed, false otherwise
   */
  del: function(key) {
    var success = false;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        var prev = this.backing_hash[hashCode];
        this.backing_hash[hashCode] = undefined;
        if(prev !== undefined)
          success = true;
      }
    }
    return success;
  }
}

//// Usage

// creation

var my_map = new HashMap();

// insertion

var a_key = {};
var a_value = {struct: "structA"};
var b_key = {};
var b_value = {struct: "structB"};
var c_key = {};
var c_value = {struct: "structC"};

my_map.put(a_key, a_value);
my_map.put(b_key, b_value);
var prev_b = my_map.put(b_key, c_value);

// retrieval

if(my_map.get(a_key) !== a_value){
  throw("fail1")
}
if(my_map.get(b_key) !== c_value){
  throw("fail2")
}
if(prev_b !== b_value){
  throw("fail3")
}

// deletion

var a_existed = my_map.del(a_key);
var c_existed = my_map.del(c_key);
var a2_existed = my_map.del(a_key);

if(a_existed !== true){
  throw("fail4")
}
if(c_existed !== false){
  throw("fail5")
}
if(a2_existed !== false){
  throw("fail6")
}
5
Lambder

In ECMA6 können Sie WeakMap verwenden

Beispiel:

var wm1 = new WeakMap(),
    wm2 = new WeakMap(),
    wm3 = new WeakMap();
var o1 = {},
    o2 = function(){},
    o3 = window;

wm1.set(o1, 37);
wm1.set(o2, "azerty");
wm2.set(o1, o2); // a value can be anything, including an object or a function
wm2.set(o3, undefined);
wm2.set(wm1, wm2); // keys and values can be any objects. Even WeakMaps!

wm1.get(o2); // "azerty"
wm2.get(o2); // undefined, because there is no value for o2 on wm2
wm2.get(o3); // undefined, because that is the set value

wm1.has(o2); // true
wm2.has(o2); // false
wm2.has(o3); // true (even if the value itself is 'undefined')

wm3.set(o1, 37);
wm3.get(o1); // 37
wm3.clear();
wm3.get(o1); // undefined, because wm3 was cleared and there is no value for o1 anymore

wm1.has(o1);   // true
wm1.delete(o1);
wm1.has(o1);   // false

Aber:

Because of references being weak, WeakMap keys are not enumerable (i.e. there is no method giving you a list of the keys). 
5
Nox73

Javascript hat keine eingebaute Map/Hashmap. Es sollte assoziatives Array heißen.

hash["X"] ist gleich hash.X, lässt jedoch "X" als Zeichenfolgenvariable zu. Mit anderen Worten, hash[x] ist funktional gleich eval("hash."+x.toString())

Es ähnelt eher object.properties als der Zuordnung von Schlüsselwerten. Wenn Sie eine bessere Zuordnung von Schlüsseln und Werten in Javascript suchen, verwenden Sie bitte das Kartenobjekt, das Sie im Web finden.

2
Dennis C

Wenn die Leistung nicht kritisch ist (z. B. die Anzahl der Schlüssel relativ gering ist) und Sie Ihre (oder möglicherweise auch nicht Ihre) Objekte nicht mit zusätzlichen Feldern wie __hash_, __id_ usw. verschmutzen möchten, dann können Sie die Tatsache ausnutzen, dass Array.prototype.indexOf strenge Gleichheit anwendet. Hier ist eine einfache Implementierung:

_var Dict = (function(){
    // IE 8 and earlier has no Array.prototype.indexOf
    function indexOfPolyfill(val) {
      for (var i = 0, l = this.length; i < l; ++i) {
        if (this[i] === val) {
          return i;
        }
      }
      return -1;
    }

    function Dict(){
      this.keys = [];
      this.values = [];
      if (!this.keys.indexOf) {
        this.keys.indexOf = indexOfPolyfill;
      }
    };

    Dict.prototype.has = function(key){
      return this.keys.indexOf(key) != -1;
    };

    Dict.prototype.get = function(key, defaultValue){
      var index = this.keys.indexOf(key);
      return index == -1 ? defaultValue : this.values[index];
    };

    Dict.prototype.set = function(key, value){
      var index = this.keys.indexOf(key);
      if (index == -1) {
        this.keys.Push(key);
        this.values.Push(value);
      } else {
        var prevValue = this.values[index];
        this.values[index] = value;
        return prevValue;
      }
    };

    Dict.prototype.delete = function(key){
      var index = this.keys.indexOf(key);
      if (index != -1) {
        this.keys.splice(index, 1);
        return this.values.splice(index, 1)[0];
      }
    };

    Dict.prototype.clear = function(){
      this.keys.splice(0, this.keys.length);
      this.values.splice(0, this.values.length);
    };

    return Dict;
})();
_

Anwendungsbeispiel:

_var a = {}, b = {},
    c = { toString: function(){ return '1'; } },
    d = 1, s = '1', u = undefined, n = null,
    dict = new Dict();

// keys and values can be anything
dict.set(a, 'a');
dict.set(b, 'b');
dict.set(c, 'c');
dict.set(d, 'd');
dict.set(s, 's');
dict.set(u, 'u');
dict.set(n, 'n');

dict.get(a); // 'a'
dict.get(b); // 'b'
dict.get(s); // 's'
dict.get(u); // 'u'
dict.get(n); // 'n'
// etc.
_

Im Vergleich zu ES6 WeakMap gibt es zwei Probleme: O(n) Suchzeit und Nichtschwäche (dh es führt zu einem Speicherverlust, wenn Sie delete oder clear bis nicht verwenden Tasten loslassen).

2
skozin

Meine Kartenimplementierung, abgeleitet von Christophs Beispiel:

Beispiel Verwendung:

var map = new Map();  //creates an "in-memory" map
var map = new Map("storageId");  //creates a map that is loaded/persisted using html5 storage

function Map(storageId) {
    this.current = undefined;
    this.size = 0;
    this.storageId = storageId;
    if (this.storageId) {
        this.keys = new Array();
        this.disableLinking();
    }
}

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

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

// map initialisation from 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)];
    if (item === undefined) {
        if (this.storageId) {
            try {
                var itemStr = localStorage.getItem(this.storageId + key);
                if (itemStr && itemStr !== 'undefined') {
                    item = JSON.parse(itemStr);
                    this[this.hash(key)] = item;
                    this.keys.Push(key);
                    ++this.size;
                }
            } catch (e) {
                console.log(e);
            }
        }
    }
    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;
    if (this.storageId) {
        this.keys.Push(key);
        try {
            localStorage.setItem(this.storageId + key, JSON.stringify(this[hash]));
        } catch (e) {
            console.log(e);
        }
    }
    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];
    }
    if (this.storageId) {
        try {
            localStorage.setItem(this.storageId + key, undefined);
        } catch (e) {
            console.log(e);
        }
    }
    return this;
};

// only works if linked
Map.prototype.removeAll = function() {
    if (this.storageId) {
        for (var i=0; i<this.keys.length; i++) {
            this.remove(this.keys[i]);
        }
        this.keys.length = 0;
    } else {
        while(this.size)
            this.remove(this.key());
    }
    return this;
};

// --- linked list helper functions

Map.prototype.link = function(item) {
    if (this.storageId) {
        return;
    }
    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.storageId) {
        return;
    }
    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() {
    if (this.storageId) {
        return undefined;
    } else {
        return this.current.key;
    }
};

Map.prototype.value = function() {
    if (this.storageId) {
        return undefined;
    }
    return this.current.value;
};
2
g00dnatur3

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 Hashfunktion angeben.

2
Tim Down

Dies sieht nach einer ziemlich robusten Lösung aus: 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 unbekannten Elements zu einem Objekt, um es zu identifizieren. Wenn Ihr Programm diese obskure Variable nicht überschreibt (es ist so etwas wie hashid ), sind Sie golden.

2
B T

Hinzufügen einer weiteren Lösung: HashMap ist so ziemlich die erste Klasse, die ich von Java nach Javascript portiert habe. Man könnte sagen, dass es eine Menge Overhead gibt, aber die Implementierung entspricht fast zu 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 gesagt, es hängt auch vom Super ab Klasse usw. Das verwendete OOP Framework ist qooxdoo.

Bearbeiten: Bitte beachten Sie, dass dieser Code bereits veraltet ist und sich auf das Github-Projekt für die aktuelle Arbeit bezieht. Ab diesem Zeitpunkt gibt es auch eine ArrayList -Implementierung.

qx.Class.define( 'jsava.util.HashMap', {
    extend: jsava.util.AbstractMap,
    implement: [jsava.util.Map, jsava.io.Serializable, jsava.lang.Cloneable],

    construct: function () {
        var args = Array.prototype.slice.call( arguments ),
            initialCapacity = this.self( arguments ).DEFAULT_INITIAL_CAPACITY,
            loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;

        switch( args.length ) {
            case 1:
                if( qx.Class.implementsInterface( args[0], jsava.util.Map ) ) {
                    initialCapacity = Math.max( ((args[0].size() / this.self( arguments ).DEFAULT_LOAD_FACTOR) | 0) + 1,
                        this.self( arguments ).DEFAULT_INITIAL_CAPACITY );
                    loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;
                } else {
                    initialCapacity = args[0];
                }
                break;
            case 2:
                initialCapacity = args[0];
                loadFactor = args[1];
                break;
        }

        if( initialCapacity < 0 ) {
            throw new jsava.lang.IllegalArgumentException( 'Illegal initial capacity: ' + initialCapacity );
        }
        if( initialCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
            initialCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
        }
        if( loadFactor <= 0 || isNaN( loadFactor ) ) {
            throw new jsava.lang.IllegalArgumentException( 'Illegal load factor: ' + loadFactor );
        }

        var capacity = 1;
        while( capacity < initialCapacity ) {
            capacity <<= 1;
        }

        this._loadFactor = loadFactor;
        this._threshold = (capacity * loadFactor) | 0;
        this._table = jsava.JsavaUtils.emptyArrayOfGivenSize( capacity, null );
        this._init();
    },

    statics: {
        serialVersionUID: 1,

        DEFAULT_INITIAL_CAPACITY: 16,
        MAXIMUM_CAPACITY: 1 << 30,
        DEFAULT_LOAD_FACTOR: 0.75,

        _hash: function (hash) {
            hash ^= (hash >>> 20) ^ (hash >>> 12);
            return hash ^ (hash >>> 7) ^ (hash >>> 4);
        },

        _indexFor: function (hashCode, length) {
            return hashCode & (length - 1);
        },

        Entry: qx.Class.define( 'jsava.util.HashMap.Entry', {
            extend: jsava.lang.Object,
            implement: [jsava.util.Map.Entry],

            construct: function (hash, key, value, nextEntry) {
                this._value = value;
                this._next = nextEntry;
                this._key = key;
                this._hash = hash;
            },

            members: {
                _key: null,
                _value: null,
                /** @type jsava.util.HashMap.Entry */
                _next: null,
                /** @type Number */
                _hash: 0,

                getKey: function () {
                    return this._key;
                },

                getValue: function () {
                    return this._value;
                },

                setValue: function (newValue) {
                    var oldValue = this._value;
                    this._value = newValue;
                    return oldValue;
                },

                equals: function (obj) {
                    if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.HashMap.Entry ) ) {
                        return false;
                    }

                    /** @type jsava.util.HashMap.Entry */
                    var entry = obj,
                        key1 = this.getKey(),
                        key2 = entry.getKey();
                    if( key1 === key2 || (key1 !== null && key1.equals( key2 )) ) {
                        var value1 = this.getValue(),
                            value2 = entry.getValue();
                        if( value1 === value2 || (value1 !== null && value1.equals( value2 )) ) {
                            return true;
                        }
                    }

                    return false;
                },

                hashCode: function () {
                    return (this._key === null ? 0 : this._key.hashCode()) ^
                        (this._value === null ? 0 : this._value.hashCode());
                },

                toString: function () {
                    return this.getKey() + '=' + this.getValue();
                },

                /**
                 * This method is invoked whenever the value in an entry is
                 * overwritten by an invocation of put(k,v) for a key k that's already
                 * in the HashMap.
                 */
                _recordAccess: function (map) {
                },

                /**
                 * This method is invoked whenever the entry is
                 * removed from the table.
                 */
                _recordRemoval: function (map) {
                }
            }
        } )
    },

    members: {
        /** @type jsava.util.HashMap.Entry[] */
        _table: null,
        /** @type Number */
        _size: 0,
        /** @type Number */
        _threshold: 0,
        /** @type Number */
        _loadFactor: 0,
        /** @type Number */
        _modCount: 0,
        /** @implements jsava.util.Set */
        __entrySet: null,

        /**
         * Initialization hook for subclasses. This method is called
         * in all constructors and pseudo-constructors (clone, readObject)
         * after HashMap has been initialized but before any entries have
         * been inserted.  (In the absence of this method, readObject would
         * require explicit knowledge of subclasses.)
         */
        _init: function () {
        },

        size: function () {
            return this._size;
        },

        isEmpty: function () {
            return this._size === 0;
        },

        get: function (key) {
            if( key === null ) {
                return this.__getForNullKey();
            }

            var hash = this.self( arguments )._hash( key.hashCode() );
            for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
                 entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash && ((k = entry._key) === key || key.equals( k )) ) {
                    return entry._value;
                }
            }

            return null;
        },

        __getForNullKey: function () {
            for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
                if( entry._key === null ) {
                    return entry._value;
                }
            }

            return null;
        },

        containsKey: function (key) {
            return this._getEntry( key ) !== null;
        },

        _getEntry: function (key) {
            var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() );
            for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
                 entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash
                    && ( ( k = entry._key ) === key || ( key !== null && key.equals( k ) ) ) ) {
                    return entry;
                }
            }

            return null;
        },

        put: function (key, value) {
            if( key === null ) {
                return this.__putForNullKey( value );
            }

            var hash = this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length );
            for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash && ( (k = entry._key) === key || key.equals( k ) ) ) {
                    var oldValue = entry._value;
                    entry._value = value;
                    entry._recordAccess( this );
                    return oldValue;
                }
            }

            this._modCount++;
            this._addEntry( hash, key, value, i );
            return null;
        },

        __putForNullKey: function (value) {
            for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
                if( entry._key === null ) {
                    var oldValue = entry._value;
                    entry._value = value;
                    entry._recordAccess( this );
                    return oldValue;
                }
            }

            this._modCount++;
            this._addEntry( 0, null, value, 0 );
            return null;
        },

        __putForCreate: function (key, value) {
            var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length );
            for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash
                    && ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
                    entry._value = value;
                    return;
                }
            }

            this._createEntry( hash, key, value, i );
        },

        __putAllForCreate: function (map) {
            var iterator = map.entrySet().iterator();
            while( iterator.hasNext() ) {
                var entry = iterator.next();
                this.__putForCreate( entry.getKey(), entry.getValue() );
            }
        },

        _resize: function (newCapacity) {
            var oldTable = this._table,
                oldCapacity = oldTable.length;
            if( oldCapacity === this.self( arguments ).MAXIMUM_CAPACITY ) {
                this._threshold = Number.MAX_VALUE;
                return;
            }

            var newTable = jsava.JsavaUtils.emptyArrayOfGivenSize( newCapacity, null );
            this._transfer( newTable );
            this._table = newTable;
            this._threshold = (newCapacity * this._loadFactor) | 0;
        },

        _transfer: function (newTable) {
            var src = this._table,
                newCapacity = newTable.length;
            for( var j = 0; j < src.length; j++ ) {
                var entry = src[j];
                if( entry !== null ) {
                    src[j] = null;
                    do {
                        var next = entry._next,
                            i = this.self( arguments )._indexFor( entry._hash, newCapacity );
                        entry._next = newTable[i];
                        newTable[i] = entry;
                        entry = next;
                    } while( entry !== null );
                }
            }
        },

        putAll: function (map) {
            var numKeyToBeAdded = map.size();
            if( numKeyToBeAdded === 0 ) {
                return;
            }

            if( numKeyToBeAdded > this._threshold ) {
                var targetCapacity = (numKeyToBeAdded / this._loadFactor + 1) | 0;
                if( targetCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
                    targetCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
                }

                var newCapacity = this._table.length;
                while( newCapacity < targetCapacity ) {
                    newCapacity <<= 1;
                }
                if( newCapacity > this._table.length ) {
                    this._resize( newCapacity );
                }
            }

            var iterator = map.entrySet().iterator();
            while( iterator.hasNext() ) {
                var entry = iterator.next();
                this.put( entry.getKey(), entry.getValue() );
            }
        },

        remove: function (key) {
            var entry = this._removeEntryForKey( key );
            return entry === null ? null : entry._value;
        },

        _removeEntryForKey: function (key) {
            var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length ),
                prev = this._table[i],
                entry = prev;

            while( entry !== null ) {
                var next = entry._next,
                    /** @type jsava.lang.Object */
                        k;
                if( entry._hash === hash
                    && ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
                    this._modCount++;
                    this._size--;
                    if( prev === entry ) {
                        this._table[i] = next;
                    } else {
                        prev._next = next;
                    }
                    entry._recordRemoval( this );
                    return entry;
                }
                prev = entry;
                entry = next;
            }

            return entry;
        },

        _removeMapping: function (obj) {
            if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
                return null;
            }

            /** @implements jsava.util.Map.Entry */
            var entry = obj,
                key = entry.getKey(),
                hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length ),
                prev = this._table[i],
                e = prev;

            while( e !== null ) {
                var next = e._next;
                if( e._hash === hash && e.equals( entry ) ) {
                    this._modCount++;
                    this._size--;
                    if( prev === e ) {
                        this._table[i] = next;
                    } else {
                        prev._next = next;
                    }
                    e._recordRemoval( this );
                    return e;
                }
                prev = e;
                e = next;
            }

            return e;
        },

        clear: function () {
            this._modCount++;
            var table = this._table;
            for( var i = 0; i < table.length; i++ ) {
                table[i] = null;
            }
            this._size = 0;
        },

        containsValue: function (value) {
            if( value === null ) {
                return this.__containsNullValue();
            }

            var table = this._table;
            for( var i = 0; i < table.length; i++ ) {
                for( var entry = table[i]; entry !== null; entry = entry._next ) {
                    if( value.equals( entry._value ) ) {
                        return true;
                    }
                }
            }

            return false;
        },

        __containsNullValue: function () {
            var table = this._table;
            for( var i = 0; i < table.length; i++ ) {
                for( var entry = table[i]; entry !== null; entry = entry._next ) {
                    if( entry._value === null ) {
                        return true;
                    }
                }
            }

            return false;
        },

        clone: function () {
            /** @type jsava.util.HashMap */
            var result = null;
            try {
                result = this.base( arguments );
            } catch( e ) {
                if( !qx.Class.isSubClassOf( e.constructor, jsava.lang.CloneNotSupportedException ) ) {
                    throw e;
                }
            }

            result._table = jsava.JsavaUtils.emptyArrayOfGivenSize( this._table.length, null );
            result.__entrySet = null;
            result._modCount = 0;
            result._size = 0;
            result._init();
            result.__putAllForCreate( this );

            return result;
        },

        _addEntry: function (hash, key, value, bucketIndex) {
            var entry = this._table[bucketIndex];
            this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
            if( this._size++ >= this._threshold ) {
                this._resize( 2 * this._table.length );
            }
        },

        _createEntry: function (hash, key, value, bucketIndex) {
            var entry = this._table[bucketIndex];
            this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
            this._size++;
        },

        keySet: function () {
            var keySet = this._keySet;
            return keySet !== null ? keySet : ( this._keySet = new this.KeySet( this ) );
        },

        values: function () {
            var values = this._values;
            return values !== null ? values : ( this._values = new this.Values( this ) );
        },

        entrySet: function () {
            return this.__entrySet0();
        },

        __entrySet0: function () {
            var entrySet = this.__entrySet;
            return entrySet !== null ? entrySet : ( this.__entrySet = new this.EntrySet( this ) );
        },

        /** @private */
        HashIterator: qx.Class.define( 'jsava.util.HashMap.HashIterator', {
            extend: jsava.lang.Object,
            implement: [jsava.util.Iterator],

            type: 'abstract',

            /** @protected */
            construct: function (thisHashMap) {
                this.__thisHashMap = thisHashMap;
                this._expectedModCount = this.__thisHashMap._modCount;
                if( this.__thisHashMap._size > 0 ) {
                    var table = this.__thisHashMap._table;
                    while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
                        // do nothing
                    }
                }
            },

            members: {
                __thisHashMap: null,

                /** @type jsava.util.HashMap.Entry */
                _next: null,
                /** @type Number */
                _expectedModCount: 0,
                /** @type Number */
                _index: 0,
                /** @type jsava.util.HashMap.Entry */
                _current: null,

                hasNext: function () {
                    return this._next !== null;
                },

                _nextEntry: function () {
                    if( this.__thisHashMap._modCount !== this._expectedModCount ) {
                        throw new jsava.lang.ConcurrentModificationException();
                    }

                    var entry = this._next;
                    if( entry === null ) {
                        throw new jsava.lang.NoSuchElementException();
                    }

                    if( (this._next = entry._next) === null ) {
                        var table = this.__thisHashMap._table;
                        while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
                            // do nothing
                        }
                    }

                    this._current = entry;
                    return entry;
                },

                remove: function () {
                    if( this._current === null ) {
                        throw new jsava.lang.IllegalStateException();
                    }

                    if( this.__thisHashMap._modCount !== this._expectedModCount ) {
                        throw new jsava.lang.ConcurrentModificationException();
                    }

                    var key = this._current._key;
                    this._current = null;
                    this.__thisHashMap._removeEntryForKey( key );
                    this._expectedModCount = this.__thisHashMap._modCount;
                }
            }
        } ),

        _newKeyIterator: function () {
            return new this.KeyIterator( this );
        },

        _newValueIterator: function () {
            return new this.ValueIterator( this );
        },

        _newEntryIterator: function () {
            return new this.EntryIterator( this );
        },

        /** @private */
        ValueIterator: qx.Class.define( 'jsava.util.HashMap.ValueIterator', {
            extend: jsava.util.HashMap.HashIterator,

            construct: function (thisHashMap) {
                this.base( arguments, thisHashMap );
            },

            members: {
                next: function () {
                    return this._nextEntry()._value;
                }
            }
        } ),

        /** @private */
        KeyIterator: qx.Class.define( 'jsava.util.HashMap.KeyIterator', {
            extend: jsava.util.HashMap.HashIterator,

            construct: function (thisHashMap) {
                this.base( arguments, thisHashMap );
            },

            members: {
                next: function () {
                    return this._nextEntry().getKey();
                }
            }
        } ),

        /** @private */
        EntryIterator: qx.Class.define( 'jsava.util.HashMap.EntryIterator', {
            extend: jsava.util.HashMap.HashIterator,

            construct: function (thisHashMap) {
                this.base( arguments, thisHashMap );
            },

            members: {
                next: function () {
                    return this._nextEntry();
                }
            }
        } ),

        /** @private */
        KeySet: qx.Class.define( 'jsava.util.HashMap.KeySet', {
            extend: jsava.util.AbstractSet,

            construct: function (thisHashMap) {
                this.base( arguments );
                this.__thisHashMap = thisHashMap;
            },

            members: {
                __thisHashMap: null,

                iterator: function () {
                    return this.__thisHashMap._newKeyIterator();
                },

                size: function () {
                    return this.__thisHashMap._size;
                },

                contains: function (obj) {
                    return this.__thisHashMap.containsKey( obj );
                },

                remove: function (obj) {
                    return this.__thisHashMap._removeEntryForKey( obj ) !== null;
                },

                clear: function () {
                    this.__thisHashMap.clear();
                }
            }
        } ),

        /** @private */
        Values: qx.Class.define( 'jsava.util.HashMap.Values', {
            extend: jsava.util.AbstractCollection,

            construct: function (thisHashMap) {
                this.base( arguments );
                this.__thisHashMap = thisHashMap;
            },

            members: {
                __thisHashMap: null,

                iterator: function () {
                    return this.__thisHashMap._newValueIterator();
                },

                size: function () {
                    return this.__thisHashMap._size;
                },

                contains: function (obj) {
                    return this.__thisHashMap.containsValue( obj );
                },

                clear: function () {
                    this.__thisHashMap.clear();
                }
            }
        } ),

        /** @private */
        EntrySet: qx.Class.define( 'jsava.util.HashMap.EntrySet', {
            extend: jsava.util.AbstractSet,

            construct: function (thisHashMap) {
                this.base( arguments );
                this.__thisHashMap = thisHashMap;
            },

            members: {
                __thisHashMap: null,

                iterator: function () {
                    return this.__thisHashMap._newEntryIterator();
                },

                size: function () {
                    return this.__thisHashMap._size;
                },

                contains: function (obj) {
                    if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
                        return false;
                    }

                    /** @implements jsava.util.Map.Entry */
                    var entry = obj,
                        candidate = this.__thisHashMap._getEntry( entry.getKey() );
                    return candidate !== null && candidate.equals( entry );
                },

                remove: function (obj) {
                    return this.__thisHashMap._removeMapping( obj ) !== null;
                },

                clear: function () {
                    this.__thisHashMap.clear();
                }
            }
        } )
    }
} );
1
Ingo Bürk

Noch eine Kartenimplementierung von mir. Mit Randomizer, 'Generics' und 'Iterator' =)

var HashMap = function (TKey, TValue) {
    var db = [];
    var keyType, valueType;

    (function () {
        keyType = TKey;
        valueType = TValue;
    })();

    var getIndexOfKey = function (key) {
        if (typeof key !== keyType)
            throw new Error('Type of key should be ' + keyType);
        for (var i = 0; i < db.length; i++) {
            if (db[i][0] == key)
                return i;
        }
        return -1;
    }

    this.add = function (key, value) {
        if (typeof key !== keyType) {
            throw new Error('Type of key should be ' + keyType);
        } else if (typeof value !== valueType) {
            throw new Error('Type of value should be ' + valueType);
        }
        var index = getIndexOfKey(key);
        if (index === -1)
            db.Push([key, value]);
        else
            db[index][1] = value;
        return this;
    }

    this.get = function (key) {
        if (typeof key !== keyType || db.length === 0)
            return null;
        for (var i = 0; i < db.length; i++) {
            if (db[i][0] == key)
                return db[i][1];
        }
        return null;
    }

    this.size = function () {
        return db.length;
    }

    this.keys = function () {
        if (db.length === 0)
            return [];
        var result = [];
        for (var i = 0; i < db.length; i++) {
            result.Push(db[i][0]);
        }
        return result;
    }

    this.values = function () {
        if (db.length === 0)
            return [];
        var result = [];
        for (var i = 0; i < db.length; i++) {
            result.Push(db[i][1]);
        }
        return result;
    }

    this.randomize = function () {
        if (db.length === 0)
            return this;
        var currentIndex = db.length, temporaryValue, randomIndex;
        while (0 !== currentIndex) {
            randomIndex = Math.floor(Math.random() * currentIndex);
            currentIndex--;
            temporaryValue = db[currentIndex];
            db[currentIndex] = db[randomIndex];
            db[randomIndex] = temporaryValue;
        }
        return this;
    }

    this.iterate = function (callback) {
        if (db.length === 0)
            return false;
        for (var i = 0; i < db.length; i++) {
            callback(db[i][0], db[i][1]);
        }
        return true;
    }
}

Beispiel:

var a = new HashMap("string", "number");
a.add('test', 1132)
 .add('test14', 666)
 .add('1421test14', 12312666)
 .iterate(function (key, value) {console.log('a['+key+']='+value)});
/*
a[test]=1132
a[test14]=666
a[1421test14]=12312666 
*/
a.randomize();
/*
a[1421test14]=12312666
a[test]=1132
a[test14]=666
*/
0
ovnia