Pourquoi la mise en œuvre HashSet dans Sun Java utilisent HashMap comme son soutien?

StackOverflow https://stackoverflow.com/questions/2235546

  •  19-09-2019
  •  | 
  •  

Question

En regardant la source de Java 6, HashSet<E> est effectivement mis en œuvre à l'aide HashMap<E,Object>, en utilisant instance d'objet factice sur chaque entrée du Set.

Je pense que les déchets 4 octet (sur les machines 32 bits) pour la taille de l'entrée elle-même.

Mais, pourquoi est-il toujours utilisé? Y at-il raison de l'utiliser en plus de rendre plus facile de maintenir les codes?

Était-ce utile?

La solution

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

Vos questions principales sont

  

Mais, pourquoi est-il toujours utilisé? Y a-t-il   aucune raison de l'utiliser en plus de faire ce   plus facile de maintenir les codes?

Je suppose que la maintenance du code est un grand facteur de motivation. Donc, ce qui empêche la duplication et le ballonnement.

Set et Map sont des interfaces similaires, que les éléments en double ne sont pas autorisés. (Je pense que le seul Set pas soutenu par un Map est CopyOnWriteArraySet, qui est une collection rare, parce qu'il est immuable.)

Plus précisément:

De la documentation Set :

  

Une collection qui ne contient pas de   dupliquer des éléments. Plus formellement,   ensembles ne contiennent aucune paire d'éléments e1   et e2 de telle sorte que e1.equals (e2), et   plus un élément nul. Comme le laisse entendre par   son nom, ce modèle d'interface les   abstraction mathématique jeu.

     

L'interface Set SupplémentairesEndroits   stipulations, au-delà de celles héritées   de l'interface de collecte, sur la   contrats de tous les constructeurs et sur   les contrats du complément, égaux et   méthodes hashCode. déclarations pour   d'autres méthodes héritées sont également   inclus ici pour plus de commodité. (Le   cahier des charges accompagnant ces   Des déclarations ont été adaptées à la   Paramétrage de l'interface, mais ils ne contiennent pas   tout stipulations supplémentaires.)

     

La stipulation supplémentaire   constructeurs est, sans surprise,   que tous les constructeurs doivent créer un   ensemble qui ne contient pas de double   des éléments (tel que défini ci-dessus).

Et de Map :

  

Un objet qui liste les variables.   Une carte ne peut pas contenir les clés en double; chaque touche peut mapper au plus une valeur.

Si vous pouvez mettre en œuvre votre Sets en utilisant le code existant, tout avantage (vitesse, par exemple), vous pouvez réaliser à partir du code existant revient à votre Set ainsi.

Si vous choisissez de mettre en œuvre un Set sans support Map, vous devez dupliquer du code conçu pour éviter les doublons. Ah, l'ironie délicieuse.

Cela dit, il n'y a rien qui vous empêche de mettre en œuvre vos Sets différemment.

Autres conseils

Je suppose qu'il n'a jamais tourné comme un problème important pour des applications ou des repères importants réels. Pourquoi compliquer le code pour aucun avantage réel?

A noter également, que la taille des objets sont rassemblés dans de nombreux implémentation JVM, donc il ne peut pas réellement être une augmentation de la taille (je ne sais pas pour cet exemple). De plus, le code de HashMap est susceptible d'être compilé et dans le cache. D'autres choses étant égales par ailleurs, plus de code => plus misses cache => faible performance.

Je pense que HashSet a été mis en œuvre en termes de HashMap pour pour le faire rapidement et facilement. En termes de lignes de code, HashSet est une fraction de HashMap.

Je suppose que la raison pour laquelle il n'a pas encore été optimisé est la peur du changement.

Cependant, les déchets est bien pire que vous pensez. Sur les deux 32 bits et 64 bits, HashSet est 4 fois plus grande que nécessaire, et HashMap est 2x plus grande que nécessaire. HashMap pourrait être mis en œuvre avec un tableau avec les clés et les valeurs qu'il contient (plus les chaînes de collisions). Cela signifie que deux pointeurs par entrée ou 16 octets sur une machine virtuelle 64 bits. En fait, HashMap contient un objet d'entrée par entrée, ce qui ajoute 8 octets pour le pointeur sur l'entrée et 8 octets pour l'en-tête d'objet d'entrée. HashSet utilise également 32 octets par élément, mais les déchets est 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 definetley là. Petit parce que, pour chaque entrée, il utilise le même objet PRESENT (qui est déclarée finale). D'où le seul gaspillage est pour la valeur de chaque entrée dans la table de hachage.

La plupart du temps, je pense, ils ont pris cette approche pour la maintenabilité et réutilisabilité. (Les développeurs JCF aurait pensé, nous avons testé HashMap, pourquoi ne pas le réutiliser.)

Mais si vous avez des collections énormes, et vous êtes un monstre de mémoire, alors vous pouvez opter pour de meilleures alternatives comme Trove ou Google Collections.

Je regardais votre question et il m'a fallu un certain temps pour réfléchir à ce que vous avez dit. Voici donc mon avis sur la mise en œuvre de HashSet.

Il est nécessaire d'avoir l'instance factice pour savoir si la valeur est ou non présent dans l'ensemble.

Jetez un oeil à la méthode add 

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

Abd maintenant nous allons jeter un oeil à la valeur de retour de vente

  

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

l'objet PRESENT est juste 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 auparavant sur la carte, car map.put(key,value) retournerait toujours null et vous ne serait pas moyen de savoir si la clé existait.

Cela dit on pourrait dire qu'ils auraient pu utiliser une mise en œuvre comme celui-ci 

   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 le calcul du hashCode, car il pourrait être coûteux, des deux fois sur la touche (si la clé va être ajoutée).

Si vous question posée de savoir pourquoi ils ont utilisé un HashMap qui gaspillez 8 octets (à cause du Map.Entry) au lieu d'une autre structure de données à l'aide d'une entrée similaire de seulement 4, alors oui, je dirais qu'ils l'ont fait pour les raisons vous avez mentionné.

Après la recherche des pages comme celle-ci se demandent pourquoi l'implémentation standard légèrement inefficace, trouvé com.carrotsearch.hppc.IntOpenHashSet

Votre question: Je pense que les déchets 4 octet (sur les machines 32 bits) pour la taille de l'entrée elle-même.

Juste une variable d'objet est créé pour l'ensemble de HashSet et structure de données qui fait vous sauver de réécrire à nouveau l'ensemble de hashmap sorte de code.

private static final Object PRESENT = new Object();

Toutes les touches sont ayant une valeur i.e. objet présent.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top