Comment une carte de hachage JavaScript est-elle implémentée?

Question 1

Je travaille actuellement avec OpenLayers et j'ai un énorme ensemble de données à dessiner dans une couche vectorielle (plus de 100000 vecteurs).

J'essaie maintenant de mettre tous ces vecteurs dans une carte de hachage JavaScript pour analyser les performances. Je veux savoir comment la carte de hachage en JavaScript est implémentée, est-ce une vraie fonction de hachage ou simplement une fonction enveloppée qui utilise une structure de données simple et un algorithme de recherche?

Question 2

chaque objet javascript est un simple hashmap qui accepte une chaîne ou un symbole comme clé, vous pouvez donc écrire votre code comme:

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

L'objet javascript est un véritable hashmap sur son implémentation, donc la complexité sur la recherche est O (1), mais il n'y a pas de hashcode()fonction dédiée pour les chaînes javascript, il est implémenté en interne par le moteur javascript (V8, SpiderMonkey, JScript.dll, etc. .)

Mise à jour 2020:

javascript prend aujourd'hui en charge d'autres types de données: Mapet WeakMap. Ils se comportent plus étroitement comme des cartes de hachage que des objets traditionnels.

Question 3

Les objets JavaScript ne peuvent pas être implémentés uniquement au-dessus des cartes de hachage.

Essayez ceci dans la console de votre navigateur:

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

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

... et vous les recevrez dans l'ordre d'insertion, ce qui est de facto un comportement standard .

Les cartes de hachage ne maintiennent pas l'ordre, donc les implémentations de JavaScript peuvent utiliser d'une manière ou d'une autre des cartes de hachage, mais si elles le font, cela nécessitera au moins un index séparé et une comptabilité supplémentaire pour les insertions.

Voici une vidéo de Lars Bak expliquant pourquoi la v8 n'utilise pas de cartes de hachage pour implémenter des objets .

Question 4

Voici un moyen simple et pratique d'utiliser quelque chose de similaire à la carte 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
    }

Et pour obtenir la valeur:

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

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

Question 5

Devriez-vous essayer ce cours 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"

Développer l'extrait

Remarque: la clé et la valeur peuvent être de n'importe quel type.

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

Question 6

Bien que les anciens objets JavaScript simples puissent être utilisés comme cartes, ils sont généralement implémentés de manière à préserver l'ordre d'insertion pour la compatibilité avec la plupart des navigateurs (voir la réponse de Craig Barnes) et ne sont donc pas de simples cartes de hachage.

ES6 introduit les cartes appropriées (voir la carte JavaScript MDN ) dont la norme dit :

L'objet de carte doit être implémenté à l'aide de tables de hachage ou d'autres mécanismes qui, en moyenne, fournissent des temps d'accès sous-linéaires sur le nombre d'éléments de la collection.

Question 7

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

Question 8

Je rencontrais le problème où j'avais le json avec des clés communes. Je voulais regrouper toutes les valeurs ayant la même clé. Après un peu de surf, j'ai trouvé le package hashmap . Ce qui est vraiment utile.

Pour regrouper l'élément avec la même clé, j'ai utilisé multi(key:*, value:*, key2:*, value2:*, ...).

Ce package est un peu similaire à la collection Java Hashmap, mais pas aussi puissant que Java Hashmap.

Answer 1

88

Je travaille actuellement avec OpenLayers et j'ai un énorme ensemble de données à dessiner dans une couche vectorielle (plus de 100000 vecteurs).

J'essaie maintenant de mettre tous ces vecteurs dans une carte de hachage JavaScript pour analyser les performances. Je veux savoir comment la carte de hachage en JavaScript est implémentée, est-ce une vraie fonction de hachage ou simplement une fonction enveloppée qui utilise une structure de données simple et un algorithme de recherche?

javascript hash hashmap Patrick Hillert
la source

2

Il n'y a pas qu'une seule implémentation JS, il n'y a donc aucun moyen de répondre à cela. ECMAScript ne spécifie pas la structure de données à utiliser pour les objets, ni ne spécifie de restrictions sur le temps d'accès. Les hachages sont typiques, mais des arbres équilibrés peuvent être utilisés.

sortie le

1

ES6 a des cartes pures. Le lien décrit les différences entre l'objet simple et la carte, les détails clés, etc.: MDN JavaScript Map

Den Roman

Answer 2

2

Il n'y a pas qu'une seule implémentation JS, il n'y a donc aucun moyen de répondre à cela. ECMAScript ne spécifie pas la structure de données à utiliser pour les objets, ni ne spécifie de restrictions sur le temps d'accès. Les hachages sont typiques, mais des arbres équilibrés peuvent être utilisés.

sortie le

Answer 3

1

ES6 a des cartes pures. Le lien décrit les différences entre l'objet simple et la carte, les détails clés, etc.: MDN JavaScript Map

Den Roman

Answer 4

193

chaque objet javascript est un simple hashmap qui accepte une chaîne ou un symbole comme clé, vous pouvez donc écrire votre code comme:

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

L'objet javascript est un véritable hashmap sur son implémentation, donc la complexité sur la recherche est O (1), mais il n'y a pas de hashcode()fonction dédiée pour les chaînes javascript, il est implémenté en interne par le moteur javascript (V8, SpiderMonkey, JScript.dll, etc. .)

Mise à jour 2020:

javascript prend aujourd'hui en charge d'autres types de données: Mapet WeakMap. Ils se comportent plus étroitement comme des cartes de hachage que des objets traditionnels.

otakustay
la source

Parfait. J'utilisais $ ('div # someDiv'). Data (clé, valeur) avant et celui-ci est beaucoup plus simple et a probablement un meilleur support pour les navigateurs plus anciens. Merci

Swaroop

existe-t-il un moyen de trouver la longueur de la carte?

Rolling Stone

2

@Sridhar utilise Object.keys (map) .length

otakustay

1

Notez que vous pouvez utiliser un nombre comme clé, map[2] = 'foo'mais il est converti en chaîne en interne> map = { '2': 'foo' }

Harry Moreno

@otakustay c'était une fonctionnalité super cool que j'ai appris à connaître aujourd'hui :) Vraiment, j'ai besoin d'apprendre le Javascript de près.

Pankaj Prakash

Answer 5

Parfait. J'utilisais $ ('div # someDiv'). Data (clé, valeur) avant et celui-ci est beaucoup plus simple et a probablement un meilleur support pour les navigateurs plus anciens. Merci

Swaroop

Answer 6

existe-t-il un moyen de trouver la longueur de la carte?

Rolling Stone

Answer 7

2

@Sridhar utilise Object.keys (map) .length

otakustay

Answer 8

1

Notez que vous pouvez utiliser un nombre comme clé, map[2] = 'foo'mais il est converti en chaîne en interne> map = { '2': 'foo' }

Harry Moreno

Answer 9

@otakustay c'était une fonctionnalité super cool que j'ai appris à connaître aujourd'hui :) Vraiment, j'ai besoin d'apprendre le Javascript de près.

Pankaj Prakash

Answer 10

31

Les objets JavaScript ne peuvent pas être implémentés uniquement au-dessus des cartes de hachage.

Essayez ceci dans la console de votre navigateur:

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

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

... et vous les recevrez dans l'ordre d'insertion, ce qui est de facto un comportement standard .

Les cartes de hachage ne maintiennent pas l'ordre, donc les implémentations de JavaScript peuvent utiliser d'une manière ou d'une autre des cartes de hachage, mais si elles le font, cela nécessitera au moins un index séparé et une comptabilité supplémentaire pour les insertions.

Voici une vidéo de Lars Bak expliquant pourquoi la v8 n'utilise pas de cartes de hachage pour implémenter des objets .

Craig Barnes
la source

3

"otakustay est techniquement faux, le pire genre de mal." C'est un peu dur. Ce n'est peut-être pas 1: 1, mais dans le but d'utiliser un hachage comme un dictionnaire, cela fonctionne de la même manière.

probablement le

1

Je veux juste préciser que cela peut être vrai pour certaines implémentations de JavaScript (comme la plupart des navigateurs) mais pas nécessairement toujours vrai. L'ordre d'itération sur les clés n'est pas défini par les normes ECMAScript et peut être n'importe quel ordre et être toujours une implémentation JS valide.

TheZ

Answer 11

3

"otakustay est techniquement faux, le pire genre de mal." C'est un peu dur. Ce n'est peut-être pas 1: 1, mais dans le but d'utiliser un hachage comme un dictionnaire, cela fonctionne de la même manière.

probablement le

Answer 12

1

Je veux juste préciser que cela peut être vrai pour certaines implémentations de JavaScript (comme la plupart des navigateurs) mais pas nécessairement toujours vrai. L'ordre d'itération sur les clés n'est pas défini par les normes ECMAScript et peut être n'importe quel ordre et être toujours une implémentation JS valide.

TheZ

Answer 13

Voici un moyen simple et pratique d'utiliser quelque chose de similaire à la carte 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
    }

Et pour obtenir la valeur:

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

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

Answer 14

Devriez-vous essayer ce cours 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"

Développer l'extrait

Remarque: la clé et la valeur peuvent être de n'importe quel type.

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

Answer 15

Bien que les anciens objets JavaScript simples puissent être utilisés comme cartes, ils sont généralement implémentés de manière à préserver l'ordre d'insertion pour la compatibilité avec la plupart des navigateurs (voir la réponse de Craig Barnes) et ne sont donc pas de simples cartes de hachage.

ES6 introduit les cartes appropriées (voir la carte JavaScript MDN ) dont la norme dit :

L'objet de carte doit être implémenté à l'aide de tables de hachage ou d'autres mécanismes qui, en moyenne, fournissent des temps d'accès sous-linéaires sur le nombre d'éléments de la collection.

Answer 16

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

Answer 17

Je rencontrais le problème où j'avais le json avec des clés communes. Je voulais regrouper toutes les valeurs ayant la même clé. Après un peu de surf, j'ai trouvé le package hashmap . Ce qui est vraiment utile.

Pour regrouper l'élément avec la même clé, j'ai utilisé multi(key:*, value:*, key2:*, value2:*, ...).

Ce package est un peu similaire à la collection Java Hashmap, mais pas aussi puissant que Java Hashmap.

Comment une carte de hachage JavaScript est-elle implémentée?

Réponses: