MegaHash - Une table de hachage rapide pour Node.js développée en C++

• Remplace les Maps ES6 limitées à 16 millions d’entrées : peut stocker plus d’un milliard de clés

• Développée en C++ et inclut un wrapper pour Node.js

→ Peut lire/écrire 500 000 clés par seconde

→ Faible surcharge mémoire

→ N’est pas stockée dans le heap V8

→ Prend en charge les buffers, chaînes de caractères, nombres, booléens et objets

• Compatible en grande partie avec l’API ES6 Map : get, set, has, ddelete, clear, length

• Utilise en interne la technique du separate chaining : index + liste chaînée

[kbumsik]

Ouh là, y a-t-il vraiment une raison d’utiliser une Map aussi grande ?

[xguru]

En pratique, dans Node.JS, si l’on met plus de 2^24 clés dans une Map, une erreur de heap se produit.

Ce n’est pas un bug, mais une limite définie par l’implémentation, et une réponse d’un développeur V8 à ce sujet se trouve sur StackOverflow.

https://stackoverflow.com/a/54466812/166418

• Le FixedArray qui stocke la Map a une taille maximale de 1 Go

• Sur un système 64 bits, 1 Go / 8 o = 2^30 / 2^3 = 2^27 ~= 134 M, donc un FixedArray peut stocker au maximum 134 millions d’éléments

• Une Map nécessite 3 éléments par entrée (Key, value, next bucket link), et le facteur de charge maximal est limité à 50 % pour éviter les collisions de buckets.

→ Comme la capacité doit être une puissance de deux, en partant du calcul 2^27 / (3 * 2) et en arrondissant à la puissance de deux inférieure, 2^24 est la valeur maximale