Comment est-ce que la bibliothèque standard Scala peut être réutilisée pour créer une variante de HashMap qui ne gère pas du tout les collisions?Scala: Quelle est la bonne façon de construire une variante HashMap sans listes chaînées?
Dans l'implémentation de HashMap dans Scala, je peux voir que les traits HashEntry, DefaultEntry et LinkedEntry sont liés, mais je ne suis pas sûr d'avoir un quelconque contrôle sur eux.
Vous pourrait faire en étendant HashMap (lire le code source de HashMap pour voir ce qui doit être modifié); En gros, vous devez remplacer put et += pour ne pas appeler findEntry, et vous devez remplacer addEntry (à partir de HashTable) pour simplement calculer le code de hachage et supprimer l'entrée en place. Ensuite, il ne traiterait pas du tout.
Mais ce n'est pas une bonne chose à faire puisque la structure HashEntry est spécifiquement conçue pour gérer les collisions - le pointeur next devient alors complètement superflu. Donc, si vous faites cela pour des raisons de performance, c'est un mauvais choix; vous avez des frais généraux parce que vous envelopper tout dans un Entry. Si vous ne voulez pas de vérification de collision, il vaut mieux simplement stocker les tuples (clé, valeur) dans un tableau plat, ou utiliser des tableaux de clés et de valeurs séparés. Gardez à l'esprit que vous allez maintenant souffrir des collisions dans la valeur de hachage, pas seulement dans la clé. Et, normalement, HashMap commence petit puis se développe, de sorte que vous allez d'abord détruire de façon destructive les choses qui auraient survécu si elle n'avait pas commencé petit. Vous pouvez outrepasser initialSize également si vous saviez combien vous ajouteriez pour que vous n'ayez jamais besoin de redimensionner. Mais, fondamentalement, si vous voulez écrire une carte de hachage dangereuse à grande vitesse, il est préférable de l'écrire de toutes pièces ou d'utiliser une autre bibliothèque. Si vous modifiez la version de la bibliothèque générique, vous obtiendrez toutes les incertitudes sans toute la vitesse. Si cela vaut la peine de jouer avec, il vaut la peine de refaire entièrement. (Par exemple, vous devez mettre en œuvre des filtres et de telle sorte que la carte f: (Key,Value) => Boolean au lieu de cartographier la (K,V) tuple -. De cette façon vous n'avez pas à envelopper et déballer tuples)
Je suppose que cela dépend ce que vous entendez par « ne fonctionne pas gérer les collisions du tout ". Une couche mince sur un MultiMap serait-elle suffisante pour vos besoins?
Très bonnes réponses, merci. Je veux réimplémenter à partir de zéro. Mais je ne veux pas mettre en place des dizaines de méthodes. Je veux réutiliser certaines implémentations de méthodes (comme foldLeft, exists, find, etc) basées sur des méthodes primitives. Quel est l'ensemble minimal de méthodes primitives que je dois implémenter et quels traits dois-je utiliser? –
@ Łukasz: Je pense que votre meilleur pari est de regarder le code source pour 'HashMap' et' HashTable' et de jouer avec jusqu'à ce que vous compreniez comment cela fonctionne. L'extension des 2,8 collections d'une manière agréable prend un travail raisonnable. Pour autant que je sache, le code lui-même est la seule documentation de l'arbre des dépendances; 'Iterable' requiert très peu, mais les sous-classes remplacent différentes parties de l'arbre pour les rendre plus efficaces et/ou ajouter des fonctionnalités. –