Hashtable, HashMap, HashSet, concept de table de hachage dans le framework de collection Java
J'apprends le framework de collection Java et j'ai une compréhension modérée. Maintenant, quand je vais un peu plus loin, j'ai quelques doutes: HashMap, HashSet, Hashtable.
Le Javadoc pour HashMap dit:
Implémentation basée sur la table de hachage de l'interface de carte. Ce l'implémentation fournit toutes les opérations de carte facultatives, et autorise les valeurs null et la clé null.
Le Javadoc pour HashSet dit:
Cette classe implémente l'interface, soutenu par une table de hachage (en fait une instance HashMap). Il ne donne aucune garantie quant à l' itération afin de l'ensemble; en particulier, il ne garantit pas que la commande restera constante dans le temps.
Le Javadoc pour Hashtable dit:
Cette classe implémente une table de hachage, qui mappe les clés aux valeurs. Tout l'objet non nul peut être utilisé comme clé ou comme valeur.
Il est déroutant que tous mettent en œuvre le hash table. Mettent-ils en œuvre le concept de table de hachage?
Il semble que tous ces éléments soient liés les uns aux autres, mais je ne suis pas en mesure de le comprendre pleinement.
Quelqu'un Peut-il m'aider à comprendre ce concept dans un langage simple.
4 answers
Les interfaces Set et Map de Java spécifient deux types de collection très différents. Un Map est, conceptuellement, exactement ce que cela ressemble: un mappage d'un ensemble d'objets (les clés) à un autre ensemble (les valeurs). Un Set est aussi exactement ce que cela ressemble: une collection d'objets (sans autre structure). Hashtable et HashMap implémentent tous deux Map, HashSet implémente Set, et ils utilisent tous des codes de hachage pour les clés/objets contenus dans les collections pour améliorer les performances.
Hashtable et HashMap
Hashtable est une classe héritée qui devrait presque toujours être évitée en faveur de HashMap. Ils font essentiellement la même chose, sauf que la plupart des méthodes dans Hashtable sont synchronisées, ce qui rend les appels de méthode individuels thread-safe.1 Vous devez fournir votre propre synchronisation ou d'autres thread mécanisme de sécurité si vous utilisez plusieurs threads et HashMap.
Le problème avec Hashtable est que la synchronisation de chaque appel de méthode (qui est une opération non négligeable) est généralement la mauvaise chose. Vous n'avez pas du tout besoin de synchronisation ou, du point de vue de la logique de l'application, vous devez synchroniser des transactions couvrant plusieurs appels de méthode. Comme il était impossible de supprimer simplement la synchronisation au niveau de la méthode de Hashtable sans casser le code existant, les auteurs du framework Collections devaient créer une nouvelle classe; d'où HashMap. C'est aussi un meilleur nom, car il devient clair que c'est une sorte de Map.
Oh, si vous le faites besoin d'une synchronisation au niveau de la méthode, vous ne devriez toujours pas utiliser Hashtable. Au lieu de cela, vous pouvez appeler Collections.synchronizedMap() pour transformer n'importe quelle carte en une carte synchronisée. Alternativement, vous pouvez utiliser ConcurrentHashMap, qui, selon les docs: "obéit à la même spécification fonctionnelle que Hashtable" mais a de meilleures performances et des fonctionnalités supplémentaires (telles que putIfAbsent()).
1Il existe d'autres différences (moins significatives, à mon avis) telles que HashMap supportant null valeurs et touches.
HashSet
En termes de fonctionnalité, HashSet n'a rien à voir avec HashMap. Il arrive d'utiliser un HashMap en interne pour implémenter la fonctionnalité Set. Pour une raison quelconque, les développeurs du framework Collections ont pensé que ce serait une bonne idée de faire de ce détail d'implémentation interne une partie de la spécification publique de la classe. (C'était une erreur, à mon avis.)
Hashtable était une ancienne classe qui a été créée avant que Java n'ait des génériques. C'est seulement autour encore pour la rétrocompatibilité. Utilisez HashMap à la place.
Utilisez HashSet lorsque vous n'avez pas besoin de mapper des clés sur des valeurs. Il est construit sur le même algorithme que les tables de hachage, mais il est utilisé dans un but fondamentalement différent.
HashMap et HashTable héritent tous deux de l'interface de la carte.et ont presque le même travail et les propriétés.Mais les principales différences sont les suivantes:-
1.Hashmap est une carte non ordonnée de paires clé et valeur.Et nous pouvons avoir la clé nulle ou les paires de valeurs dans un hashmap.De plus, un hashmap n'est pas synchronisé(c'est-à-dire que plusieurs threads peuvent y accéder et le modifier en même temps.) Mais nous pouvons créer en externe un hashmap thread-safe.So si nous ne considérons pas les problèmes de synchronisation alors hashmap est préférable.
2.HashTable: - Un HashMap synchronisé(c'est-à-dire un hashmap sécurisé pour les threads).Mais les clés et les paires de valeurs dans ce cas ne le seront jamais null.In une table de hachage nous spécifions un objet qui est utilisé comme clé, et la valeur que nous voulons associer à cette clé. La clé est ensuite hachée et le code de hachage résultant est utilisé comme index auquel la valeur est stockée dans la table
3.HashSet: - Un hashset hérite de l'interface set et à la fin, il est également basé sur hashtable(ou nous pouvons dire profondément connecté à notre hashmap uniquement) mais dans ce cas, les paires de clés et de valeurs sont toujours uniques, aucune valeur en double n'est autorisée.mais les valeurs de clé null sont autorisées.Les objets sont insérés en fonction de leur code de hachage.
En conclusion, nous pouvons dire que les trois collections se sont connectées à l'interface de la carte sur et tous.
Hashtable est synchronisé mais HashMap ne l'est pas, mais vous pouvez synchroniser HashMap à l'aide de collections de méthodes.synchronizedMap (). Hashtable, HashMap et HashSet sont basés sur la structure de données de la table de hachage. Vous pouvez utiliser une clé null et le type de valeurs null que vous voulez pour HashMap mais Hashtable n'autorise pas la clé null ou les valeurs null. Fondamentalement, sous HashSet fonctionne HashMap où la valeur est un objet, donc les valeurs HashSet sont uniques car les clés HashMap sont uniques. Donc pour mettre la clé paire de valeurs dans Hashmap ou Hashtable ou mettre un élément à HashSet vous devez ovveride hashcode et equals méthodes de la classe Object pour corriger le fonctionnement de ces implémentations. En effet, sous cette implémentations fonctionnent algorithme de table de hachage et hashcode, equals est nécessaire pour mettre des valeurs dans le compartiment droit. Il est important de savoir que vous devez utiliser comme chaîne de clés ou toute autre classe wrapper telle que us Integer, c'est parce que ces objets sont immuables et ils peuvent être de bonnes clés pour cela implémentations ou vous pouvez créer votre propre classe immuable et l'utiliser comme clé. Utiliser des objets immuables comme clé est une bonne pratique car après la création, ils ne peuvent pas changer leur état, donc le hashcode est toujours le même.