Comme indiqué clairement dans la mise à jour 3 sur cette réponse , cette notation:
var hash = {};
hash[X]
ne hache pas réellement l'objet X
; en fait, il se convertit simplement X
en chaîne (via .toString()
s'il s'agit d'un objet ou d'autres conversions intégrées pour divers types primitifs), puis recherche cette chaîne, sans la hacher, dans " hash
". L'égalité des objets n'est pas non plus vérifiée - si deux objets différents ont la même conversion de chaîne, ils se remplaceront simplement.
Compte tenu de cela - existe-t-il des implémentations efficaces de hashmaps en javascript? (Par exemple, le deuxième résultat de Google javascript hashmap
donne une implémentation qui est O (n) pour toute opération. Divers autres résultats ignorent le fait que différents objets avec des représentations de chaînes équivalentes se remplacent.
Réponses:
Pourquoi ne pas hacher vous-même vos objets manuellement et utiliser les chaînes résultantes comme clés pour un dictionnaire JavaScript normal? Après tout, vous êtes le mieux placé pour savoir ce qui rend vos objets uniques. C'est ce que je fais.
Exemple:
De cette façon, vous pouvez contrôler l'indexation effectuée par JavaScript sans soulever lourdement l'allocation de mémoire et la gestion des débordements.
Bien sûr, si vous voulez vraiment la "solution de qualité industrielle", vous pouvez construire une classe paramétrée par la fonction clé, et avec toutes les API nécessaires du conteneur, mais ... nous utilisons JavaScript, et essayant d'être simple et léger, donc cette solution fonctionnelle est simple et rapide.
La fonction de clé peut être aussi simple que de sélectionner les bons attributs de l'objet, par exemple, une clé ou un ensemble de clés, qui sont déjà uniques, une combinaison de clés, qui sont uniques ensemble, ou aussi complexe que d'utiliser des hachages cryptographiques comme dans DojoX Encoding ou DojoX UUID . Bien que ces dernières solutions puissent produire des clés uniques, personnellement, j'essaie de les éviter à tout prix, surtout si je sais ce qui rend mes objets uniques.
Mise à jour en 2014: Répondue en 2008, cette solution simple nécessite encore plus d'explications. Permettez-moi de clarifier l'idée sous forme de questions / réponses.
Votre solution n'a pas de vrai hachage. Où est-ce???
JavaScript est un langage de haut niveau. Sa primitive de base ( Object ) comprend une table de hachage pour conserver les propriétés. Cette table de hachage est généralement écrite dans un langage de bas niveau pour plus d'efficacité. En utilisant un objet simple avec des clés de chaîne, nous utilisons une table de hachage efficacement implémentée sans aucun effort de notre part.
Comment savez-vous qu'ils utilisent du hachage?
Il existe trois façons principales de conserver une collection d'objets adressables par une clé:
De toute évidence, les objets JavaScript utilisent des tables de hachage sous une forme ou une autre pour gérer les cas généraux.
Les fournisseurs de navigateurs utilisent-ils vraiment les tables de hachage ???
Vraiment.
Gèrent-ils les collisions?
Oui. Voir au dessus. Si vous avez trouvé une collision sur des chaînes inégales, n'hésitez pas à déposer un bug auprès d'un vendeur.
Alors quelle est votre idée?
Si vous voulez hacher un objet, trouvez ce qui le rend unique et utilisez-le comme clé. N'essayez pas de calculer le vrai hachage ou d'émuler des tables de hachage - il est déjà géré efficacement par l'objet JavaScript sous-jacent.
Utilisez cette clé avec JavaScript
Object
pour tirer parti de sa table de hachage intégrée tout en évitant les conflits possibles avec les propriétés par défaut.Exemples pour vous aider à démarrer:
J'ai utilisé votre suggestion et mis en cache tous les objets en utilisant un nom d'utilisateur. Mais un sage est nommé "toString", qui est une propriété intégrée! Qu'est-ce que je devrais faire maintenant?
De toute évidence, s'il est même possible à distance que la clé résultante soit exclusivement composée de caractères latins, vous devriez faire quelque chose. Par exemple, ajoutez tout caractère Unicode non latin que vous aimez au début ou à la fin pour annuler le conflit avec les propriétés par défaut: "#toString", "#MarySmith". Si une clé composite est utilisée, séparez les composants clés en utilisant une sorte de délimiteur non latin: "nom, ville, état".
En général, c'est l'endroit où nous devons être créatifs et sélectionner les clés les plus faciles avec des limitations données (unicité, conflits potentiels avec des propriétés par défaut).
Remarque: les clés uniques ne s'affrontent pas par définition, tandis que les conflits de hachage potentiels seront gérés par le sous-jacent
Object
.Pourquoi n'aimez-vous pas les solutions industrielles?
À mon humble avis, le meilleur code n'est pas du tout un code: il ne contient aucune erreur, ne nécessite aucune maintenance, est facile à comprendre et s'exécute instantanément. Toutes les "tables de hachage en JavaScript" que j'ai vues étaient> 100 lignes de code et impliquaient plusieurs objets. Comparez avec:
dict[key] = value
.Autre point: est-il même possible de battre une performance d'un objet primordial écrit dans un langage de bas niveau, en utilisant JavaScript et les mêmes objets primordiaux pour implémenter ce qui est déjà implémenté?
Je veux toujours hacher mes objets sans aucune clé!
Nous avons de la chance: ECMAScript 6 (prévu pour la version mi-2015, donner ou prendre 1-2 ans après pour se généraliser) définit la carte et le set .
À en juger par la définition, ils peuvent utiliser l'adresse de l'objet comme clé, ce qui rend les objets instantanément distincts sans clés artificielles. OTOH, deux objets différents, mais identiques, seront mappés comme distincts.
Ventilation de comparaison de MDN :
la source
Description du problème
JavaScript n'a pas de type de carte général intégré (parfois appelé tableau associatif ou dictionnaire ) qui permet d'accéder à des valeurs arbitraires par des clés arbitraires. La structure de données fondamentale de JavaScript est l' objet , un type spécial de carte qui n'accepte que les chaînes comme clés et possède une sémantique spéciale comme l'héritage prototypique, les getters et setters et quelques autres vaudous.
Lorsque vous utilisez des objets comme cartes, vous devez vous rappeler que la clé sera convertie en une valeur de chaîne via
toString()
, ce qui entraîne un mappage5
et'5'
la même valeur et tous les objets qui n'écrasent pas latoString()
méthode à la valeur indexée par'[object Object]'
. Vous pouvez également accéder involontairement à ses propriétés héritées si vous ne cochez pashasOwnProperty()
.Le type de tableau intégré de JavaScript n'aide pas du tout: les tableaux JavaScript ne sont pas des tableaux associatifs, mais seulement des objets avec quelques propriétés supplémentaires. Si vous voulez savoir pourquoi elles ne peuvent pas être utilisées comme cartes, regardez ici .
La solution d'Eugène
Eugene Lazutkin a déjà décrit l'idée de base d'utiliser une fonction de hachage personnalisée pour générer des chaînes uniques qui peuvent être utilisées pour rechercher les valeurs associées en tant que propriétés d'un objet dictionnaire. Ce sera probablement la solution la plus rapide, car les objets sont implémentés en interne sous forme de tables de hachage .
Afin d'obtenir une valeur de hachage unique pour des objets arbitraires, une possibilité consiste à utiliser un compteur global et à mettre en cache la valeur de hachage dans l'objet lui-même (par exemple dans une propriété nommée
__hash
).Une fonction de hachage qui fait cela est et fonctionne pour les valeurs primitives et les objets est:
Cette fonction peut être utilisée comme décrit par Eugene. Pour plus de commodité, nous allons envelopper davantage dans une
Map
classe.Ma
Map
mise en œuvreL'implémentation suivante stockera en outre les paires clé-valeur dans une liste doublement liée afin de permettre une itération rapide sur les clés et les valeurs. Pour fournir votre propre fonction de hachage, vous pouvez remplacer la
hash()
méthode de l'instance après sa création.Exemple
Le script suivant
génère cette sortie:
Considérations supplémentaires
PEZ a suggéré d'écraser la
toString()
méthode, probablement avec notre fonction de hachage. Ce n'est pas faisable car cela ne fonctionne pas pour les valeurs primitives (changertoString()
pour les primitives est une très mauvaise idée). Si nous voulonstoString()
renvoyer des valeurs significatives pour des objets arbitraires, nous devrons les modifierObject.prototype
, ce que certaines personnes (moi non compris) considèrent comme verboten .Edit: La version actuelle de mon
Map
implémentation ainsi que d'autres goodies JavaScript peuvent être obtenus à partir d'ici .la source
Map._counter = 0
, et dans le constructeur de carte, faitesthis._hash = 'object ' + Map._counter++
. Puis hash () devientreturn (value && value._hash) || (typeof(value) + ' ' + String(value));
Je sais que cette question est assez ancienne, mais il existe aujourd'hui de très bonnes solutions avec des bibliothèques externes.
JavaScript dispose également de son langage
Map
.la source
Voici un moyen simple et pratique d'utiliser quelque chose de similaire à la carte java:
Et pour obtenir la valeur:
la source
Selon ECMAScript 2015 (ES6), le javascript standard a une implémentation de carte. Plus d'informations sur ce qui peut être trouvé ici
Utilisation de base:
la source
Vous pouvez utiliser ES6
WeakMap
ouMap
:Sachez que ni l'un ni l'autre n'est largement pris en charge, mais vous pouvez utiliser ES6 Shim (nécessite natif ES5 ou ES5 Shim ) pour le prendre en charge
Map
, mais pasWeakMap
( voir pourquoi ).la source
Vous devez stocker dans certains couplets d'état interne des paires objet / valeur
Et utilisez-le comme tel:
Bien sûr, cette implémentation se situe également quelque part dans le sens de O (n). Les exemples d'Eugène ci-dessus sont le seul moyen d'obtenir un hachage qui fonctionne avec n'importe quelle vitesse que vous attendez d'un vrai hachage.
Mise à jour:
Une autre approche, dans le sens de la réponse d'Eugène, consiste à attacher en quelque sorte un ID unique à tous les objets. L'une de mes approches préférées consiste à prendre l'une des méthodes intégrées héritées de la superclasse Object, à la remplacer par un passage de fonction personnalisé et à attacher des propriétés à cet objet fonction. Si vous deviez réécrire ma méthode HashMap pour ce faire, cela ressemblerait à:
Cette version ne semble être que légèrement plus rapide, mais en théorie, elle sera considérablement plus rapide pour les grands ensembles de données.
la source
Malheureusement, aucune des réponses ci-dessus n'était bonne pour mon cas: différents objets clés peuvent avoir le même code de hachage. Par conséquent, j'ai écrit une version HashMap simple de type Java:
Remarque: les objets clés doivent "implémenter" les méthodes hashCode () et equals ().
la source
new Array()
plus[]
est d'assurer la ressemblance Java absolue de votre code? :)J'ai implémenté un HashMap JavaScript dont le code peut être obtenu à partir de http://github.com/lambder/HashMapJS/tree/master
Voici le code:
la source
HashMap
s.Dans ECMA6, vous pouvez utiliser WeakMap
Exemple:
Mais:
la source
Javascript ne construit pas Map / hashmap. Il doit être appelé tableau associatif .
hash["X"]
est égal àhash.X
, mais autorise "X" comme variable de chaîne. En d'autres termes,hash[x]
est fonctionnellement égal àeval("hash."+x.toString())
Il est plus similaire à object.properties qu'à un mappage de valeurs-clés. Si vous cherchez un meilleur mappage clé / valeur en Javascript, veuillez utiliser l'objet Map que vous pouvez trouver sur le web.
la source
Essayez ma mise en œuvre de table de hachage JavaScript: http://www.timdown.co.uk/jshashtable
Il recherche une méthode hashCode () des objets clés, ou vous pouvez fournir une fonction de hachage lors de la création d'un objet Hashtable.
la source
Cela ressemble à une solution assez robuste: https://github.com/flesler/hashmap . Cela fonctionnera même bien pour les fonctions et les objets qui semblent identiques. Le seul hack qu'il utilise consiste à ajouter un membre obscur à un objet pour l'identifier. Si votre programme n'écrase pas cette variable obscure (c'est quelque chose comme hashid ), vous êtes en or.
la source
Si les performances ne sont pas critiques (par exemple , la quantité de clés est relativement faible) et vous ne voulez pas polluer votre (ou peut - être pas votre) des objets avec des champs supplémentaires comme
_hash
,_id
, etc., vous pourrez utiliser le fait queArray.prototype.indexOf
emploie égalité stricte. Voici une implémentation simple:Exemple d'utilisation:
Par rapport à ES6 WeakMap, il a deux problèmes: le temps de recherche O (n) et la non-faiblesse (c'est-à-dire qu'il provoquera une fuite de mémoire si vous n'utilisez pas
delete
ou neclear
relâchez pas les clés).la source
My Map Implementation, dérivé de l'exemple de Christoph:
Exemple d'utilisation:
la source
Ajout d'une autre solution:
HashMap
c'est à peu près la première classe que j'ai portée de Java vers Javascript. On pourrait dire qu'il y a beaucoup de surcharge, mais l'implémentation est presque 100% égale à l'implémentation de Java et inclut toutes les interfaces et sous-classes.Le projet peut être trouvé ici: https://github.com/Airblader/jsava Je vais également attacher le code source (actuel) pour la classe HashMap, mais comme indiqué, cela dépend aussi de la super classe, etc. Le cadre OOP utilisé est qooxdoo.
Edit: Veuillez noter que ce code est déjà obsolète et se référer au projet github pour le travail en cours. Au moment de la rédaction de ce document, il existe également une
ArrayList
implémentation.la source
Encore une autre implémentation de carte par moi. Avec randomiseur, 'génériques' et 'itérateur' =)
Exemple:
la source