La norme ECMAScript 2015 , connu sous le nom ES6, il y a beaucoup de nouveaux-collections telles que JavaScript
Map, Set, WeakMapet WeakSet. Ils semblent être un excellent ajout aux capacités JavaScript standard. Ils sont largement utilisés dans diverses bibliothèques, dans les applications, au cœur de Node.js. Aujourd'hui, nous allons parler de la collection Map, essayer de comprendre les spécificités de sa mise en œuvre dans V8 et tirer des conclusions pratiques basées sur les connaissances acquises.
La norme ES6 ne fournit pas une indication claire de l'approche à adopter pour mettre en œuvre la prise en charge de la structure de données
Map. Il ne donne que quelques indications sur les moyens possibles de l'implémenter. Il contient également des informations sur leMapmétriques de performance: l'
objet Map doit être implémenté à l'aide de tables de hachage ou d'autres mécanismes qui, en moyenne, fournissent un accès sous-linéaire aux éléments de la collection. Les structures de données utilisées dans la spécification Map sont uniquement destinées à décrire la sémantique observable des objets Map. Ils n'ont pas été conçus comme un véritable modèle de mise en œuvre de ces objets.
Comme vous pouvez le voir, la spécification donne beaucoup de liberté à ceux qui créent des moteurs JS. Mais en même temps, il n'y a pas de directives spécifiques concernant l'approche spécifique utilisée pour l'implémentation
Map, ses performances et les caractéristiques de consommation de mémoire. Si des structures de données sont utilisées dans une partie critique de votre applicationMapet si vous écrivez de grandes quantités d'informations dans de telles structures de données, une solide connaissance de l'implémentation vous Mapsera certainement très utile.
J'ai de l'expérience en développement Java, je suis habitué aux collections Java, où vous pouvez choisir entre différentes implémentations de l'interface
Mapet même affiner l'implémentation sélectionnée si la classe correspondante la prend en charge. De plus, en Java, vous pouvez toujours lire le code open source de n'importe quelle classe de la bibliothèque standard et vous familiariser avec son implémentation (cela, bien sûr, peut changer dans les nouvelles versions, mais uniquement dans le sens d'une efficacité accrue). C'est pourquoi je n'ai pas pu résister à l'apprentissage du fonctionnement des objets Mapdans V8.
Avant de commencer, je tiens à noter que ce qui sera discuté ci-dessous se réfère au moteur V8 8.4, qui est intégré à la nouvelle version de développement de Node.js (plus précisément, nous parlons de commit 238104c). Vous n'avez pas besoin de vous attendre à quoi que ce soit en dehors des spécifications.
Algorithme sous-jacent à l'implémentation de la carte
Tout d'abord, je dirai que les structures de données sont
Mapbasées sur des tables de hachage. Ci-dessous, je suppose que vous savez comment fonctionnent les tables de hachage. Si vous n'êtes pas familiarisé avec les tables de hachage, vous devez d'abord les lire ( ici , par exemple), puis continuer à lire cet article.
Si vous avez une expérience significative avec les objets
Map, vous avez peut-être déjà remarqué une contradiction. À savoir, les tables de hachage ne sont pas garanties de renvoyer les éléments dans un ordre constant lors de leur itération. Et la spécification ES6 précise que pour implémenter un objet, Mapil est nécessaire, lors de sa traversée, de renvoyer les éléments dans l'ordre dans lequel ils y ont été ajoutés. En conséquence, l'algorithme "classique" pour l'implémentationMapNe convient pas. Mais il y a un sentiment qu'il, avec quelques modifications, peut encore être utilisé.
V8 utilise les soi-disant « tables de hachage déterministes » proposées par Tyler Close. Le pseudocode suivant, basé sur TypeScript, illustre les structures de données de base utilisées pour implémenter ces tables de hachage:
interface Entry {
key: any;
value: any;
chain: number;
}
interface CloseTable {
hashTable: number[];
dataTable: Entry[];
nextSlot: number;
size: number;
}
Ici, l'interface
CloseTablereprésente une table de hachage. Il contient un tableau hashTabledont la taille est équivalente au nombre de conteneurs de hachage. L'élément de tableau avec l'index Ncorrespond au N-th conteneur de hachage et stocke l'index de son élément head qui se trouve dans le tableau dataTable. Et ce tableau contient les enregistrements de la table dans l'ordre où ils y ont été insérés. Les entrées sont présentées par l'interface Entry. Enfin, chaque entrée a une propriété chainqui pointe vers l'entrée suivante dans la chaîne d'entrées dans le conteneur de hachage (ou, plus précisément, dans une liste liée individuellement).
Chaque fois qu'un nouvel enregistrement est inséré dans la table, il est stocké dans l'élément de tableau
dataTableavec l'indexnextSlot... Ce processus nécessite également la mise à jour des données dans le conteneur de hachage correspondant, ce qui fait que l'enregistrement inséré devient le nouveau dernier élément de la liste liée individuellement.
Lorsqu'un enregistrement est supprimé d'une table, il est supprimé de
dataTable(par exemple, en écrivant dans ses propriétés keyet valuevaleurs undefined). Ensuite, l'entrée qui la précède et l'entrée qui la suit sont directement liées l'une à l'autre. Comme vous l'avez peut-être remarqué, cela signifie que toutes les entrées supprimées continuent à occuper de l'espace dans le dataTable.
Maintenant, pour la dernière pièce de notre puzzle. Lorsqu'une table est pleine d'enregistrements (à la fois en cours et supprimés), elle doit être remaniée (reconstruite) avec une augmentation de sa taille. La taille de la table peut être modifiée vers le bas.
Avec cette approche, parcourir la structure de données
Mapéquivaut à parcourir un tableau dataTable. Cela garantit que l'ordre dans lequel les enregistrements sont insérés dans la table est conservé et que la norme est respectée. Dans cet esprit, je m'attendrais à ce que la plupart des moteurs JS (sinon tous) utilisent des tables de hachage déterministes comme l'un des mécanismes de mise en œuvre sous-jacents Map.
Recherche pratique de l'algorithme
Jetons un coup d'œil à quelques exemples pour nous aider à explorer l'algorithme en pratique. Supposons que nous ayons
CloseTable2 conteneurs de hachage ( hastTable.length), dont la capacité totale est de 4 éléments ( dataTable.length). Ce tableau contient le contenu suivant:
// , -,
// , , function hashCode(n) { return n; }
table.set(0, 'a'); // => - 0 (0 % 2)
table.set(1, 'b'); // => - 1 (1 % 2)
table.set(2, 'c'); // => - 0 (2 % 2)
La représentation interne de la table obtenue dans cet exemple pourrait ressembler à ceci:
const tableInternals = {
hashTable: [0, 1],
dataTable: [
{
key: 0,
value: 'a',
chain: 2 // <2, 'c'>
},
{
key: 1,
value: 'b',
chain: -1 // -1
},
{
key: 2,
value: 'c',
chain: -1
},
//
],
nextSlot: 3, //
size: 3
}
Si vous supprimez un enregistrement à l'aide de la méthode
table.delete(0), la table de hachage ressemblera à ce qui suit:
const tableInternals = {
hashTable: [0, 1],
dataTable: [
{
key: undefined, //
value: undefined,
chain: 2
},
{
key: 1,
value: 'b',
chain: -1
},
{
key: 2,
value: 'c',
chain: -1
},
//
],
nextSlot: 3,
size: 2 //
}
Si nous ajoutons quelques enregistrements supplémentaires à la table, il devra être haché. Nous discuterons de ce processus en détail ci-dessous.
La même approche peut être appliquée lors de la mise en œuvre de structures de données
Set. La seule différence est que ces structures de données n'ont pas besoin de propriété value.
Maintenant que nous avons compris ce qui se cache derrière les objets
Mapdans V8, nous sommes prêts à passer à autre chose.
Détails d'implémentation
L'implémentation de la structure de données
Mapdans V8 est écrite en C ++, après quoi le code JS a accès aux mécanismes correspondants. La plupart du code lié à se Maptrouve dans les classes OrderedHashTableet OrderedHashMap. Nous savons déjà comment fonctionnent ces classes. Si vous souhaitez consulter vous-même leur code, vous pouvez le trouver ici , ici et ici .
Puisque nous sommes particulièrement intéressés par les détails pratiques de l'implémentation
Mapen V8, nous devons d'abord comprendre comment la capacité de la table est définie.
Capacité de la table
En V8, la capacité de la table de hachage (structure de données
Map) est toujours une puissance de deux. Si nous parlons du taux d'utilisation des conteneurs de hachage, alors il est toujours représenté par le nombre 2. Autrement dit, la capacité maximale de la table 2 * number_of_bucketsest de 2 fois le nombre de conteneurs de hachage. Lors de la création d'un objet vide, Mapil y a 2 conteneurs de hachage dans sa table de hachage interne. En conséquence, la capacité d'un tel objet est égale à 4 enregistrements.
Il existe une limitation de la capacité maximale des objets
Map. Sur les systèmes 64 bits, ce sera environ 16,7 millions d'enregistrements. Cette limitation est due aux particularités de la représentation des structures de données Mapdans le tas. Nous en reparlerons plus tard.
Et enfin, le facteur d'augmentation ou de diminution de la table est également toujours représenté par la multiplication d'un certain nombre par 2. Cela signifie qu'après l'ajout de 4 enregistrements à la table décrite, la prochaine opération d'insertion entraînera la nécessité de remanier la table, au cours de laquelle la taille de la table augmentera de deux fois. Avec une diminution de la taille de la table, celle-ci peut respectivement devenir 2 fois plus petite.
Afin de m'assurer que ce que j'ai vu dans le code source fonctionne exactement comme je l'ai compris, j'ai modifié le code du moteur V8 intégré à Node.js, en faisant en sorte qu'une
Mapnouvelle propriété bucketscontenant informations sur le nombre de conteneurs de hachage. Vous pouvez trouver les résultats de cette modification ici... Dans cet assemblage spécial de Node.js, le script suivant peut être exécuté:
const map = new Map();
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
if (prevBuckets !== map.buckets) {
console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
map.set({}, {});
}
Ce script insère simplement
Map100 enregistrements dans la structure de données . Voici ce qui s'affiche dans la console après son lancement:
$ ./node /home/puzpuzpuz/map-grow-capacity.js
size: 0, buckets: 2, capacity: 4
size: 5, buckets: 4, capacity: 8
size: 9, buckets: 8, capacity: 16
size: 17, buckets: 16, capacity: 32
size: 33, buckets: 32, capacity: 64
size: 65, buckets: 64, capacity: 128
Comme vous pouvez le voir, lorsque le tableau est rempli, à chaque changement de taille, il double. Essayons maintenant de réduire le tableau en supprimant des éléments:
const map = new Map();
for (let i = 0; i < 100; i++) {
map.set(i, i);
}
console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
map.delete(i);
if (prevBuckets !== map.buckets) {
console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
}
Voici ce que ce script affichera:
$ ./node /home/puzpuzpuz/map-shrink-capacity.js
initial size: 100, buckets: 64, capacity: 128
size: 99, buckets: 64, capacity: 128
size: 31, buckets: 32, capacity: 64
size: 15, buckets: 16, capacity: 32
size: 7, buckets: 8, capacity: 16
size: 3, buckets: 4, capacity: 8
size: 1, buckets: 2, capacity: 4
Ici encore, vous pouvez voir que la taille du tableau est réduite à chaque fois qu'il contient moins d'
number_of_buckets / 2éléments.
Fonction de hachage
Jusqu'à présent, nous n'avons pas abordé la question de savoir comment V8 calcule les codes de hachage pour les clés stockées dans les objets
Map. Et c'est une question importante.
Pour les valeurs qui peuvent être classées comme numériques, une fonction de hachage bien connue avec une faible probabilité de collision est utilisée.
Pour les valeurs de chaîne, un code de hachage est calculé en fonction des valeurs elles-mêmes. Après cela, ce code est mis en cache dans l'en-tête interne.
Et enfin, pour les objets, les hachages sont calculés en fonction d'un nombre aléatoire, et ce qui se passe est ensuite mis en cache dans l'en-tête interne.
Complexité temporelle des opérations avec les objets Map
La plupart des opérations effectuées sur des structures de données
Map, telles que setou delete, nécessitent une recherche dans ces structures de données. Comme dans le cas des tables de hachage "classiques", la complexité temporelle de la recherche dans notre cas est O(1).
Imaginez le pire des cas, lorsque la table est pleine, c'est-à-dire occupée
Ndepuis les Nsièges. Dans ce cas, tous les enregistrements appartiennent à un seul conteneur de hachage et l'enregistrement requis est situé à la toute fin de la chaîne d'enregistrements. Dans un scénario comme celui-ci, vous devrez prendre des mesures pour trouver cette entrée N.
D'un autre côté, dans le meilleur scénario, lorsque la table est pleine et qu'il n'y a que 2 enregistrements dans chaque conteneur de hachage, la recherche d'un enregistrement ne nécessitera que 2 étapes.
Certaines opérations dans les tables de hachage sont très rapides, mais ce n'est pas le cas des opérations de hachage. La complexité temporelle de l'opération de hachage est de
O(N). Il nécessite une nouvelle table de hachage à allouer sur le tas. De plus, le rehachage est effectué au besoin, dans le cadre des opérations d'insertion ou de suppression d'éléments de la table. Par conséquent, par exemple, l'appel map.set()peut s'avérer être beaucoup plus "cher" que prévu. Heureusement, l'opération de hachage est rarement effectuée.
Consommation de mémoire
Bien sûr, la table de hachage sous-jacente doit
Mapêtre stockée sur le tas. Il est stocké dans ce qu'on appelle un "stockage auxiliaire". Et ici un autre fait intéressant nous attend. La table entière (et, par conséquent, tout ce qui y est placé Map) est stockée dans un seul tableau de longueur fixe. La structure de ce tableau est illustrée dans la figure suivante.
Tableau utilisé pour stocker les structures de données de la carte en mémoire Les
différentes parties du tableau ont les objectifs suivants:
- En-tête: contient des informations générales, telles que le nombre de conteneurs de hachage ou le nombre d'éléments supprimés
Map. - Détails du conteneur de hachage: c'est ici que nous stockons les données sur les conteneurs qui correspondent au tableau
hashTablede notre exemple. - Entrées de la table de hachage: c'est là que les données correspondant au tableau sont stockées
dataTable. À savoir, il contient des informations sur les entrées de table de hachage. Les informations sur chaque enregistrement occupent trois cellules du tableau. L'un stocke la clé, le second stocke la valeur et le troisième stocke le "pointeur" vers l'enregistrement suivant dans la chaîne.
Si nous parlons de la taille du tableau, elle peut être approximativement estimée comme
N * 3,5. Voici Nla capacité de la table. Afin de comprendre ce que cela signifie en termes de consommation de mémoire, imaginons que nous avons un système 64 bits et que la fonction de compression du pointeur du V8 est désactivée . Dans ce cas, 8 octets sont nécessaires pour stocker chaque élément du tableau. Par conséquent Map, 29 Mo de mémoire de tas sont nécessaires pour stocker une structure de données contenant environ 1 million d'enregistrements.
Résultat
Dans cet article, nous avons couvert beaucoup de choses liées à la structure de données
Mapen JavaScript. Résumons:
- V8
Maputilise des tables de hachage déterministes pour l'implémentation . Il est très probable que cette structure de données soit également implémentée dans d'autres moteurs JS. - Les mécanismes qui prennent en charge le travail
Mapsont implémentés en C ++, après quoi ils sont présentés comme une API accessible à partir de JavaScript. - Si nous parlons de la complexité temporelle des opérations effectuées avec des objets
Map, alors celles-ci, ainsi que lorsque vous travaillez avec des tables de hachage "classiques", sont complexesO(1). Dans ce cas, la complexité temporelle de l'opération de hachage estO(N). - 64-
Map1 29 , . - , ,
Set.
Map JavaScript-?
