Pourquoi l’implémentation de HashSet dans Sun Java utilise-t-elle HashMap comme support?

En regardant la source de Java 6, HashSet est réellement implémenté en utilisant HashMap , en utilisant une instance d’object factice à chaque entrée de l’ensemble.

Je pense que cela gaspille 4 octets (sur les machines 32 bits) pour la taille de l’entrée elle-même.

Mais pourquoi est-il toujours utilisé? Y a-t-il une raison de l’utiliser en plus de faciliter la maintenance des codes?

En fait, ce n’est pas juste HashSet . Toutes les implémentations de l’interface Set dans Java 6 sont basées sur une Map sous-jacente. Ce n’est pas une exigence c’est juste la façon dont la mise en œuvre est. Vous pouvez voir par vous-même en consultant la documentation des différentes implémentations de Set .

Vos principales questions sont

Mais pourquoi est-il toujours utilisé? Y a-t-il une raison de l’utiliser en plus de faciliter la maintenance des codes?

Je suppose que la maintenance du code est un facteur de motivation important. Donc, empêche la duplication et le gonflement.

Set et Map sont des interfaces similaires, dans la mesure où les éléments en double ne sont pas autorisés. (Je pense que le seul Set non soutenu par une Map est CopyOnWriteArraySet , qui est une collection inhabituelle, car elle est immuable.)

Plus précisément:

De la documentation de Set :

Une collection qui ne contient aucun élément en double. Plus formellement, les ensembles ne contiennent aucune paire d’éléments e1 et e2 tels que e1.equals (e2) et au plus un élément nul. Comme son nom l’indique, cette interface modélise l’abstraction d’ensemble mathématique.

L’interface Set place des stipulations supplémentaires, outre celles héritées de l’interface Collection, sur les contrats de tous les constructeurs et sur les contrats des méthodes add, equals et hashCode. Les déclarations pour les autres méthodes héritées sont également incluses ici pour plus de commodité. (Les spécifications accompagnant ces déclarations ont été adaptées à l’interface Set, mais elles ne contiennent aucune stipulation supplémentaire.)

La disposition supplémentaire sur les constructeurs est, sans surprise, que tous les constructeurs doivent créer un ensemble qui ne contient aucun élément en double (tel que défini ci-dessus).

Et de la Map :

Un object qui mappe des clés à des valeurs. Une carte ne peut pas contenir de clés en double; chaque touche peut correspondre à au plus une valeur.

Si vous pouvez implémenter votre Set utilisant le code existant, tous les avantages (vitesse, par exemple) que vous pouvez réaliser à partir du code existant s’accumulent également dans votre Set .

Si vous choisissez d’implémenter un Set sans support de Map , vous devez dupliquer le code conçu pour éviter les éléments en double. Ah, la délicieuse ironie.

Cela dit, rien ne vous empêche d’implémenter votre Set différemment.

Je suppose que cela n’a jamais été un problème important pour des applications réelles ou des repères importants. Pourquoi compliquer le code sans réel bénéfice?

Notez également que les tailles d’object sont arrondies dans de nombreuses implémentations de la JVM. Par conséquent, la taille ne peut pas augmenter (je ne sais pas pour cet exemple). De plus, le code pour HashMap est susceptible d’être compilé et en cache. Toutes choses égales par ailleurs, plus de code => plus de cache manque => moins de performance.

Je suppose que HashSet a été initialement implémenté en termes de HashMap afin de le faire rapidement et facilement. En termes de lignes de code, HashSet est une fraction de HashMap.

Je devine que la raison pour laquelle il n’a toujours pas été optimisé est la peur du changement.

Cependant, les déchets sont bien pires que vous ne le pensez. Sur 32 et 64 bits, HashSet est 4 fois plus grand que nécessaire et HashMap est 2 fois plus grand que nécessaire. HashMap pourrait être implémenté avec un tableau avec des clés et des valeurs (plus des chaînes pour les collisions). Cela signifie deux pointeurs par entrée, ou 16 octets sur une machine virtuelle 64 bits. En fait, HashMap contient un object Entrée par entrée, qui ajoute 8 octets pour le pointeur à l’entrée et 8 octets pour l’en-tête de l’object Entrée. HashSet utilise également 32 octets par élément, mais le gaspillage est de 4x au lieu de 2x car il ne nécessite que 8 octets par élément.

Oui, vous avez raison, une petite quantité de gaspillage est définitivement là. Small car, pour chaque entrée, il utilise le même object PRESENT (qui est déclaré final). Par conséquent, le seul gaspillage concerne la valeur de chaque entrée dans HashMap.

Je pense que la plupart du temps, ils ont adopté cette approche pour la maintenabilité et la réutilisation. (Les développeurs JCF auraient pensé, nous avons testé HashMap quand même, pourquoi ne pas le réutiliser.)

Mais si vous avez des collections énormes et que vous êtes un maniaque de la mémoire, vous pouvez choisir de choisir de meilleures alternatives comme Trove ou Google Collections .

J’ai regardé votre question et il m’a fallu du temps pour réfléchir à ce que vous avez dit. Donc, voici mon opinion concernant l’implémentation de HashSet .

Il est nécessaire que l’instance factice sache si la valeur est ou n’est pas présente dans l’ensemble.

Jetez un oeil à la méthode add

 public boolean add(E e) { return map.put(e, PRESENT)==null; } 

Abd maintenant regardons la valeur de retour put

@retourne la valeur précédente associée à la clé ou null s’il n’y avait pas de mappage pour la clé. (Un retour nul peut également indiquer que la carte associée précédemment à null avec la clé.)

Ainsi, l’object PRESENT est simplement utilisé pour représenter que l’ensemble contient la valeur e. Je pense que vous avez demandé pourquoi ne pas utiliser null au lieu de PRESENT . Mais, vous ne seriez pas en mesure de distinguer si l’entrée était précédemment sur la carte car map.put(key,value) renverrait toujours null et que vous n’auriez pas moyen de savoir si la clé existait.


Cela étant dit, vous pourriez prétendre qu’ils auraient pu utiliser une telle implémentation

  public boolean add(E e) { if( map.containsKey(e) ) { return false; } map.put(e, null); return true; } 

Je suppose qu’ils gaspillent 4 octets pour éviter de calculer le hashCode, car il pourrait être coûteux, de la clé deux fois (si la clé va être ajoutée).


Si vous vous interrogez sur la raison pour laquelle ils ont utilisé une HashMap qui gaspillerait 8 octets (à cause de Map.Entry ) au lieu d’une autre structure de données utilisant une entrée similaire de 4 seulement, alors oui, je dirais qu’ils l’ont fait pour les raisons mentionné.

Après avoir parcouru des pages comme celle-ci en se demandant pourquoi l’implémentation standard légèrement inefficace, a trouvé com.carrotsearch.hppc.IntOpenHashSet

Votre question: je pense que cela gaspille 4 octets (sur les machines 32 bits) pour la taille de l’entrée elle-même.

Une seule variable d’object est créée pour l’ensemble de la structure de données du hashset et cela vous évitera de réécrire l’intégralité du type de code hashMap.

private static final Object PRESENT = new Object();

Toutes les clés ont une valeur, c’est-à-dire object PRESENT.