Wie wird eine JavaScript-Hash-Map implementiert?

87

Ich arbeite derzeit mit OpenLayers und habe einen riesigen Datensatz, den ich in eine Vektorebene zeichnen kann (mehr als 100000 Vektoren).

Ich versuche jetzt, alle diese Vektoren in eine JavaScript-Hash-Map einzufügen, um die Leistung zu analysieren. Ich möchte wissen, wie die Hash-Map in JavaScript implementiert ist. Ist es eine echte Hash-Funktion oder nur eine umschlossene Funktion, die eine einfache Datenstruktur und einen Suchalgorithmus verwendet?

javascript hash hashmap Patrick Hillert
quelle
2
Es gibt nicht nur eine JS-Implementierung, daher gibt es keine Möglichkeit, dies zu beantworten. ECMAScript gibt weder an, welche Datenstruktur für Objekte verwendet werden soll, noch legt es Einschränkungen bei der Zugriffszeit fest. Hashes sind typisch, aber es könnten ausgewogene Bäume verwendet werden.
Outis
1
ES6 haben reine Karten. Der Link beschreibt Unterschiede zwischen einfachem Objekt und Karte, wichtige Details usw .: MDN JavaScript Map
Den Roman

Antworten:

189

Jedes Javascript-Objekt ist eine einfache Hashmap, die nur den Zeichenfolgenwert als Schlüssel akzeptiert. Sie können Ihren Code also wie folgt schreiben:

var map = {};
// add a item
map[key1] = value1;
// or remove it
delete map[key1];
// or determine whether a key exists
key1 in map;

Das Javascript-Objekt ist eine echte Hashmap für seine Implementierung, daher ist die Komplexität bei der Suche O (1), es gibt jedoch keine dedizierte hashcode()Funktion für Javascript-Zeichenfolgen. Es wird intern von der Javascript-Engine (V8, SpiderMonkey, JScript.dll usw.) implementiert. .)

Javascript unterstützt heute jedoch keinen anderen Datentyp außer String als Schlüssel. ECMAv6 (Harmony) würde eine WeakMap-Klasse einführen, die jedes Objekt als Schlüssel akzeptiert, aber es würde lange dauern ...

otakustay
quelle
Perfekt. Ich habe zuvor $ ('div # someDiv'). Data (Schlüssel, Wert) verwendet und diese ist viel einfacher und unterstützt wahrscheinlich auch ältere Browser besser. Vielen Dank
Swaroop
Gibt es eine Möglichkeit, die Länge der Karte zu ermitteln?
Rolling Stone
2
@Sridhar verwenden Object.keys (Karte) .length
otakustay
1
Beachten Sie, dass Sie eine Zahl als Schlüssel verwenden können map[2] = 'foo', diese jedoch intern in eine Zeichenfolge umgewandelt wird> map = { '2': 'foo' }
Harry Moreno,
@otakustay das war eine super coole Funktion, die ich heute kennengelernt habe :) Wirklich, ich muss Javascript genau lernen.
Pankaj Prakash
31

JavaScript-Objekte können nicht nur über Hash-Maps implementiert werden.

Versuchen Sie dies in Ihrer Browserkonsole:

var foo = {
    a: true,
    b: true,
    z: true,
    c: true
}

for (var i in foo) {
    console.log(i);
}

... und Sie erhalten sie in der Einfügereihenfolge zurück, was de facto Standardverhalten ist .

Hash - Karten von Natur aus nicht - Reihenfolge beibehalten, so dass JavaScript - Implementierungen können verwenden Hash - Karten irgendwie, aber wenn sie es tun, wird es zumindest erfordert einen separaten Index und einige zusätzliche Buchhaltung für Einfügungen.

Hier ist ein Video von Lars Bak, in dem erklärt wird, warum v8 keine Hash-Maps zum Implementieren von Objekten verwendet .

Craig Barnes
quelle
3
"otakustay ist technisch falsch, die schlimmste Art von falsch." Das ist ein bisschen hart. Es ist möglicherweise nicht 1: 1, aber für die Zwecke und Zwecke der Verwendung eines Hash wie eines Wörterbuchs funktioniert es auf die gleiche Weise.
wahrscheinlich bis
1
Ich möchte nur klarstellen, dass dies für einige Implementierungen von JavaScript (wie die meisten Browser) gilt, aber nicht unbedingt immer. Die Reihenfolge der Iteration über Schlüssel wird nicht durch die ECMAScript-Standards definiert und kann eine beliebige Reihenfolge sein und dennoch eine gültige JS-Implementierung sein.
TheZ
19

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

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

Und um den Wert zu erhalten:

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

......  etc  .....
Miloš
quelle
11

Sollten Sie diese Klasse versuchen Map:

var myMap = new Map();

// setting the values
myMap.set("1", 'value1');
myMap.set("2", 'value2');
myMap.set("3", 'value3');

myMap.size; // 3

// getting the values
myMap.get("1");    // "value associated with "value1"
myMap.get("2");       // "value associated with "value1"
myMap.get("3");      // "value associated with "value3"
Erweitern Sie das Snippet

Hinweis: Schlüssel und Wert können beliebig sein.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

Nguyen Tan Dat
quelle
2

Während einfache alte JavaScript-Objekte als Karten verwendet werden können, werden sie normalerweise so implementiert, dass die Einfügereihenfolge für die Kompatibilität mit den meisten Browsern erhalten bleibt (siehe Antwort von Craig Barnes) und sind daher keine einfachen Hash-Karten.

ES6 führt die richtigen Karten ein (siehe MDN JavaScript Map ), von denen der Standard sagt :

Das Kartenobjekt muss entweder mithilfe von Hash-Tabellen oder anderen Mechanismen implementiert werden, die im Durchschnitt Zugriffszeiten bereitstellen, die sublinear zur Anzahl der Elemente in der Sammlung sind.

mb21
quelle
1 
<html>
<head>
<script type="text/javascript">
function test(){
var map= {'m1': 12,'m2': 13,'m3': 14,'m4': 15}
     alert(map['m3']);
}
</script>
</head>
<body>
<input type="button" value="click" onclick="test()"/>
</body>
</html>
Rajendra Kumar
quelle
0

Ich hatte das Problem, dass ich den JSON mit einigen gemeinsamen Schlüsseln hatte. Ich wollte alle Werte mit demselben Schlüssel gruppieren. Nach einigem Surfen habe ich ein Hashmap-Paket gefunden . Welches ist wirklich hilfreich.

Um das Element mit demselben Schlüssel zu gruppieren, habe ich verwendet multi(key:*, value:*, key2:*, value2:*, ...).

Dieses Paket ähnelt der Java Hashmap-Sammlung, ist jedoch nicht so leistungsfähig wie Java Hashmap.

dd619
quelle