Jak wyjaśniono w aktualizacji 3 tej odpowiedzi , notacja ta:

var hash = {};
hash[X]

tak naprawdę nie haszy obiektu X; w rzeczywistości po prostu konwertuje Xna ciąg (poprzez, .toString()jeśli jest to obiekt lub inne wbudowane konwersje dla różnych typów pierwotnych), a następnie wyszukuje ten ciąg, bez mieszania go, w „ hash”. Równość obiektów również nie jest sprawdzana - jeśli dwa różne obiekty mają taką samą konwersję łańcucha, po prostu się nawzajem zastąpią.

Biorąc to pod uwagę - czy są jakieś wydajne implementacje skrótów w javascript? (Na przykład drugi wynik Google javascript hashmapdaje implementację, która jest O (n) dla każdej operacji. Różne inne wyniki ignorują fakt, że różne obiekty z równoważnymi reprezentacjami ciągu zastępują się nawzajem.

Dlaczego nie haszować obiektów samodzielnie i używać wynikowych ciągów jako kluczy do zwykłego słownika JavaScript? W końcu jesteś w najlepszej pozycji, aby wiedzieć, co czyni twoje obiekty wyjątkowymi. To jest to co robię.

Przykład:

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;

W ten sposób możesz kontrolować indeksowanie wykonywane przez JavaScript bez nadmiernego zwiększania alokacji pamięci i obsługi przepełnienia.

Oczywiście, jeśli naprawdę chcesz „rozwiązania klasy przemysłowej”, możesz zbudować klasę sparametryzowaną kluczową funkcją i wszystkimi niezbędnymi interfejsami API kontenera, ale… używamy JavaScript i staramy się być proste i lekkie, więc to funkcjonalne rozwiązanie jest proste i szybkie.

Funkcja klucza może być tak prosta, jak wybranie odpowiednich atrybutów obiektu, np. Klucza lub zestawu kluczy, które są już unikalne, kombinacji kluczy, które są unikalne razem, lub tak złożonej, jak użycie niektórych skrótów kryptograficznych, takich jak w Kodowaniu DojoX lub UUID DojoX . Podczas gdy te ostatnie rozwiązania mogą wytwarzać unikalne klucze, osobiście staram się ich unikać za wszelką cenę, zwłaszcza jeśli wiem, co czyni moje obiekty wyjątkowymi.

Aktualizacja w 2014 roku: Odpowiedzi w 2008 roku to proste rozwiązanie wciąż wymaga dodatkowych wyjaśnień. Pozwól, że wyjaśnię ten pomysł w formie pytań i odpowiedzi.

Twoje rozwiązanie nie ma prawdziwego skrótu. Gdzie to jest???

JavaScript jest językiem wysokiego poziomu. Jego podstawowa operacja podstawowa ( Obiekt ) zawiera tablicę skrótów, aby zachować właściwości. Ta tablica skrótów jest zwykle napisana w języku niskiego poziomu w celu zwiększenia wydajności. Używając prostego obiektu z kluczami łańcuchowymi, używamy wydajnie zaimplementowanej tabeli skrótów bez żadnego wysiłku z naszej strony.

Skąd wiesz, że używają skrótu?

Istnieją trzy główne sposoby utrzymywania kolekcji obiektów możliwych do adresowania za pomocą klucza:

• Niezamówiony. W tym przypadku, aby pobrać obiekt po jego kluczu, musimy przejrzeć wszystkie klucze, zatrzymując się, gdy go znajdziemy. Średnio zajmie to n / 2 porównań.
• Zamówione
  • Przykład 1: posortowana tablica - podczas wyszukiwania binarnego nasz klucz znajdziemy średnio po ~ ~ log2 (n) porównaniach. Dużo lepiej.
  • Przykład 2: drzewo. Ponownie będą to ~ log (n) próby.
• Stół Hash. Średnio wymaga to stałego czasu. Porównaj: O (n) vs. O (log n) vs. O (1). Bum.

Oczywiście obiekty JavaScript używają tabel skrótów w jakiejś formie do obsługi ogólnych przypadków.

Czy dostawcy przeglądarek naprawdę używają tabel skrótów?

Naprawdę.

• Chrome / node.js / V8 : JSObject . Poszukaj NameDictionary i NameDictionaryShape ze stosownymi szczegółami w objects.cc i objects-inl.h .
• Firefox / Gecko : JSObject , NativeObject i PlainObject ze stosownymi szczegółami w plikach jsobj.cpp i vm / NativeObject.cpp .

Czy radzą sobie z kolizjami?

Tak. Patrz wyżej. Jeśli znalazłeś kolizję na nierównych ciągach, nie wahaj się zgłosić błędu do dostawcy.

Jaki masz pomysł?

Jeśli chcesz zaszyfrować obiekt, znajdź jego wyjątkowość i użyj go jako klucza. Nie próbuj obliczać rzeczywistego skrótu ani emulować tabel skrótów - jest już skutecznie obsługiwany przez podstawowy obiekt JavaScript.

Użyj tego klucza w JavaScript, Objectaby wykorzystać wbudowaną tabelę skrótów, jednocześnie unikając możliwych kolizji z domyślnymi właściwościami.

Przykłady na początek:

• Jeśli twoje obiekty zawierają unikalną nazwę użytkownika - użyj jej jako klucza.
• Jeśli zawiera unikalny numer klienta - użyj go jako klucza.
  • Jeśli zawiera unikalne numery nadane przez rząd, takie jak SSN lub numer paszportu, a twój system nie zezwala na duplikaty - użyj go jako klucza.
• Jeśli kombinacja pól jest unikalna - użyj jej jako klucza.
  • Skrót państwowy + numer prawa jazdy stanowi doskonały klucz.
  • Skrót kraju + numer paszportu to również doskonały klucz.
• Niektóre funkcje pól lub całego obiektu mogą zwrócić unikalną wartość - użyj jej jako klucza.

Wykorzystałem twoją sugestię i zbuforowałem wszystkie obiekty przy użyciu nazwy użytkownika. Ale jakiś mądry facet nazywa się „toString”, co jest wbudowaną właściwością! Co mam teraz zrobić?

Oczywiście, jeśli jest nawet możliwe, że wynikowy klucz będzie składał się wyłącznie ze znaków łacińskich, powinieneś coś z tym zrobić. Na przykład dodaj dowolny znak spoza alfabetu łacińskiego, który lubisz na początku lub na końcu, aby usunąć niezgodność z domyślnymi właściwościami: „#toString”, „#MarySmith”. Jeśli używany jest klucz złożony, należy oddzielić komponenty klucza za pomocą pewnego rodzaju niełacińskiego separatora: „nazwa, miasto, stan”.

Ogólnie jest to miejsce, w którym musimy być kreatywni i wybierać najłatwiejsze klucze z podanymi ograniczeniami (unikalność, potencjalne kolizje z domyślnymi właściwościami).

Uwaga: unikalne klucze nie kolidują z definicji, podczas gdy potencjalne konflikty skrótów będą obsługiwane przez instrument bazowy Object.

Dlaczego nie lubisz rozwiązań przemysłowych?

IMHO, najlepszy kod w ogóle nie jest kodem: nie zawiera błędów, nie wymaga konserwacji, jest łatwy do zrozumienia i wykonuje się natychmiast. Wszystkie „tabele skrótów w JavaScript”, które widziałem, zawierały> 100 wierszy kodu i obejmowały wiele obiektów. Porównaj go z: dict[key] = value.

Kolejna kwestia: czy w ogóle można pokonać wydajność pierwotnego obiektu napisanego w języku niskiego poziomu, używając JavaScript i tych samych pierwotnych obiektów, aby zaimplementować to, co już zostało zaimplementowane?

Nadal chcę mieszać moje obiekty bez żadnych kluczy!

Mamy szczęście: ECMAScript 6 (zaplanowany na wydanie w połowie 2015 r., Upowszechnienie lub potrwa 1-2 lata) definiuje mapę i zestaw .

Sądząc po definicji, mogą używać adresu obiektu jako klucza, dzięki czemu obiekty są natychmiast odróżniane bez sztucznych kluczy. OTOH, dwa różne, ale identyczne obiekty, zostaną zamapowane jako odrębne.

Zestawienie porównawcze z MDN :

Obiekty są podobne do Map, ponieważ oba umożliwiają ustawianie kluczy na wartości, pobieranie tych wartości, usuwanie kluczy i wykrywanie, czy coś jest przechowywane pod kluczem. Z tego powodu (i ponieważ nie było wbudowanych alternatyw) Obiekty były historycznie używane jako Mapy; istnieją jednak ważne różnice, które sprawiają, że korzystanie z mapy jest lepsze w niektórych przypadkach:

• Kluczami obiektu są ciągi znaków i symbole, natomiast mogą mieć dowolną wartość dla mapy, w tym funkcje, obiekty i dowolne elementy prymitywne.
• Klucze w Mapie są uporządkowane, a klucze dodane do obiektu nie są. Zatem podczas iteracji nad nim obiekt Map zwraca klucze w kolejności wstawiania.
• Rozmiar mapy można łatwo uzyskać za pomocą właściwości size, a liczbę właściwości w obiekcie należy ustalić ręcznie.
• Mapa jest iterowalna i dlatego może być bezpośrednio iterowana, podczas gdy iteracja nad Obiektem wymaga uzyskania kluczy w pewien sposób i iteracji nad nimi.
• Obiekt ma prototyp, więc na mapie znajdują się domyślne klucze, które mogą kolidować z kluczami, jeśli nie będziesz ostrożny. Od wersji ES5 można to obejść, używając map = Object.create (null), ale rzadko tak się dzieje.
• Mapa może działać lepiej w scenariuszach obejmujących częste dodawanie i usuwanie kluczowych par.

Opis problemu

JavaScript nie ma wbudowanego ogólnego typu mapy (zwanego czasem tablicą asocjacyjną lub słownikiem ), który umożliwia dostęp do dowolnych wartości za pomocą dowolnych kluczy. Podstawową strukturą danych JavaScript jest obiekt , specjalny typ mapy, która akceptuje tylko ciągi jako klucze i ma specjalną semantykę, taką jak dziedziczenie prototypowe, metody pobierające i ustawiające oraz kilka innych voodoo.

Kiedy używasz obiektów jako map, musisz pamiętać, że klucz zostanie przekonwertowany na wartość ciągu poprzez toString(), co spowoduje mapowanie 5i '5'na tę samą wartość oraz wszystkie obiekty, które nie nadpisują toString()metody na wartość indeksowaną przez '[object Object]'. Możesz również nieświadomie uzyskać dostęp do jego odziedziczonych właściwości, jeśli nie zaznaczysz hasOwnProperty().

Wbudowane funkcje Javascript w tablicy typu nie pomaga ani trochę: tablice JavaScript nie są asocjacyjnych, ale tylko obiekty z kilkoma właściwościami bardziej wyjątkowym. Jeśli chcesz wiedzieć, dlaczego nie można ich używać jako map, spójrz tutaj .

Rozwiązanie Eugene'a

Eugene Lazutkin już opisał podstawową ideę używania niestandardowej funkcji skrótu do generowania unikatowych ciągów, których można użyć do wyszukiwania powiązanych wartości jako właściwości obiektu słownika. Najprawdopodobniej będzie to najszybsze rozwiązanie, ponieważ obiekty są wewnętrznie implementowane jako tabele skrótów .

• Uwaga: tabele skrótów (czasami nazywane mapami skrótów) ) są szczególną implementacją koncepcji mapy przy użyciu tablicy pomocniczej i wyszukiwania za pomocą liczbowych wartości skrótu. Środowisko wykonawcze może wykorzystywać inne struktury (takie jak drzewa wyszukiwania lub listy pominięć ) do implementacji obiektów JavaScript, ale ponieważ obiekty są podstawową strukturą danych, należy je odpowiednio zoptymalizować.

Aby uzyskać unikalną wartość skrótu dla dowolnych obiektów, jedną z możliwości jest użycie globalnego licznika i buforowanie wartości skrótu w samym obiekcie (np. W nazwie o nazwie __hash).

Funkcja skrótu, która to robi i działa zarówno dla pierwotnych wartości, jak i obiektów, to:

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

hash.current = 0;

Z tej funkcji można korzystać zgodnie z opisem Eugene'a. Dla wygody dodatkowo zawiniemy go w Mapklasę.

Mój Map realizacja

Poniższa implementacja będzie dodatkowo przechowywać pary klucz-wartość na podwójnie połączonej liście, aby umożliwić szybką iterację zarówno kluczy, jak i wartości. Aby podać własną funkcję skrótu, możesz zastąpić hash()metodę instancji po utworzeniu.

// 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;
};

Przykład

Poniższy skrypt

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

generuje ten wynik:

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

Dalsze uwagi

PEZ zaproponował zastąpienie toString()metody, prawdopodobnie za pomocą naszej funkcji skrótu. Nie jest to możliwe, ponieważ nie działa dla prymitywnych wartości (zmiana toString()na prymitywy to bardzo zły pomysł). Jeśli chcemy toString()zwrócić znaczące wartości dla dowolnych obiektów, musielibyśmy zmodyfikować Object.prototype, co niektórzy ludzie (ja nie wliczając) uważają za dosłowne .

Edycja: bieżącą wersję mojej Mapimplementacji, a także inne dodatki JavaScript można uzyskać tutaj .

Wiem, że to pytanie jest dość stare, ale istnieją obecnie naprawdę świetne rozwiązania z bibliotekami zewnętrznymi.

• collections.js
• niezmienny

JavaScript ma również swój język Map.

• Mapa

Oto prosty i wygodny sposób korzystania z czegoś podobnego do mapy Java:

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
        }

Aby uzyskać wartość:

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

......  etc  .....

Według ECMAScript 2015 (ES6) standardowy javascript ma implementację mapy. Więcej o tym można znaleźć tutaj

Podstawowe użycie:

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"

Możesz użyć ES6 WeakMaplub Map:

• WeakMaps to mapy kluczy / wartości, w których klucze są obiektami.

• Mapobiekty są prostymi mapami klucz / wartość. Każda wartość (zarówno obiekty, jak i wartości pierwotne) może być używana jako klucz lub wartość.

Pamiętaj, że żadna z nich nie jest szeroko obsługiwana, ale możesz używać ES6 Shim (wymaga natywnego ES5 lub ES5 Shim ) do obsługi Map, ale nie WeakMap( zobacz dlaczego ).

Będziesz musiał przechowywać w parach wewnętrznych par par obiekt / wartość

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];
  }
}

I użyj go jako takiego:

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

Oczywiście, ta implementacja jest również gdzieś na linii O (n). Powyższe przykłady Eugene'a to jedyny sposób na uzyskanie skrótu, który działa z dowolną prędkością, jakiej można oczekiwać od prawdziwego skrótu.

Aktualizacja:

Innym podejściem, zgodnym z odpowiedzią Eugene'a, jest jakoś dołączyć unikalny identyfikator do wszystkich obiektów. Jednym z moich ulubionych podejść jest pobranie jednej z wbudowanych metod odziedziczonych po nadklasie Object, zastąpienie jej funkcją przejścia niestandardowego i dołączenie właściwości do tego obiektu funkcji. Jeśli miałbyś przepisać moją metodę HashMap, aby to zrobić, wyglądałoby to tak:

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];
}

Ta wersja wydaje się być tylko nieco szybsza, ale teoretycznie będzie znacznie szybsza w przypadku dużych zestawów danych.

Niestety, żadna z powyższych odpowiedzi nie była dobra w moim przypadku: różne kluczowe obiekty mogą mieć ten sam kod skrótu. Dlatego napisałem prostą wersję HashMap w stylu Java:

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

Uwaga: kluczowe obiekty muszą „implementować” metody hashCode () i equals ().

Zaimplementowałem JavaScript HashMap, którego kod można uzyskać ze strony http://github.com/lambder/HashMapJS/tree/master

Oto kod:

/*
 =====================================================================
 @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")
}

W ECMA6 możesz użyć WeakMap

Przykład:

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

Ale:

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

JavaScript nie buduje mapy / mapy skrótów. Powinien być nazywany tablicą asocjacyjną .

hash["X"]jest równa hash.X, ale pozwala „X” jako zmienną łańcuchową. Innymi słowy, hash[x]jest funkcjonalnie równaeval("hash."+x.toString())

Jest bardziej podobny do object.properties niż do mapowania klucz-wartość. Jeśli szukasz lepszego mapowania Klucz / wartość w JavaScript, użyj obiektu Map, który możesz znaleźć w Internecie.

Wypróbuj moją implementację tabeli skrótów JavaScript: http://www.timdown.co.uk/jshashtable

Wyszukuje metodę hashCode () kluczowych obiektów lub można podać funkcję haszującą podczas tworzenia obiektu Hashtable.

Wygląda to na całkiem solidne rozwiązanie: https://github.com/flesler/hashmap . Będzie nawet działał dobrze dla funkcji i obiektów, które wyglądają identycznie. Jedynym włamaniem, jakiego używa, jest dodanie do obiektu niejasnego elementu członkowskiego w celu jego identyfikacji. Jeśli twój program nie zastąpi tej niejasnej zmiennej (jej czegoś w rodzaju hashid ), jesteś złoty.

Jeżeli wydajność nie jest krytyczna (np ilość klawiszy jest stosunkowo niewielka) i nie chcesz, aby zanieczyścić (lub może nie swojej) obiektów z dodatkowych pól, takich jak _hash, _iditp, to można skorzystać z faktu, że Array.prototype.indexOfzatrudnia ścisła równość. Oto prosta implementacja:

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

Przykład użycia:

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.

W porównaniu do ES6 WeakMap ma dwa problemy: O (n) czas wyszukiwania i brak słabości (tj. Spowoduje wyciek pamięci, jeśli nie użyjesz deletelub clearnie zwolnisz klawiszy).

Implementacja mojej mapy, pochodząca z przykładu Christopha:

Przykładowe użycie:

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

Dodanie kolejnego rozwiązania: HashMap to właściwie pierwsza klasa, którą przeniosłem z Javy na JavaScript. Można powiedzieć, że istnieje duży narzut, ale implementacja jest prawie w 100% równa implementacji Java i obejmuje wszystkie interfejsy i podklasy.

Projekt można znaleźć tutaj: https://github.com/Airblader/jsava Dołączę również (aktualny) kod źródłowy dla klasy HashMap, ale jak już wspomniano, zależy to również od superklasy itp. Użyty framework OOP jest qooxdoo.

Edycja: Pamiętaj, że ten kod jest już przestarzały i zapoznaj się z projektem github dla bieżącej pracy. W chwili pisania tego jest również ArrayListimplementacja.

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