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

Question

En regardant la source de Java 6, HashSet<E> est en fait implémenté en utilisant HashMap<E,Object> , en utilisant une instance d'objet factice sur 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 gestion des codes?

Answer 1

En fait, ce n'est pas seulement HashSet. Toutes les implémentations de l' Set interface en Java 6 sont basés sur un sous-jacent Collection. Ce n'est pas une obligation, c'est juste la manière dont l'application est. Vous pouvez voir par vous-même en consultant la documentation pour les diverses implémentations d' Set.

Vos principales questions sont

Mais, pourquoi est-il encore utilisé? Est-il aucune raison pour l'utiliser en plus de rendre plus facile à maintenir les codes?

Je suppose que le code de la maintenance est un grand facteur de motivation. Donc est d'empêcher la duplication et le ballonnement.

Set et Map sont semblables interfaces, en ce que les éléments en double ne sont pas autorisés. (Je pense que la seule Set pas soutenu par un Map est CopyOnWriteArraySet, ce qui est une étonnante Collection, parce qu'il est immuable.)

Plus précisément:

À partir de la documentation de l' Set:

Une collection qui ne contient pas de les éléments en double. Plus formellement, les ensembles contiennent pas de paire d'éléments e1 et e2 tels que e1.equals(e2), et à plus un élément de valeur null. Comme le sous-entend son nom, cette interface les modèles de la ensemble mathématique de l'abstraction.

L'interface de places supplémentaires stipulations, au-delà de celles héritées à partir de l'interface de Collecte, sur le les contrats de tous les constructeurs et sur les contrats de l'ajouter, d'égal à égal et les méthodes hashCode. Déclarations pour d'autres les méthodes héritées sont également inclus ici pour plus de commodité. (Le spécifications de l'accompagnement de ces des déclarations ont été adaptées à la L'interface, mais ils ne contiennent pas de toutes les stipulations supplémentaires.)

La disposition additionnelle sur les constructeurs est, il n'est pas surprenant, que tous les constructeurs doivent créer un ensemble qui ne contient pas de doublons éléments (tel que défini ci-dessus).

Et à partir de Map:

Un objet que les cartes des clés à des valeurs. Une carte ne peut pas contenir des doubles de clés; chaque clé peut correspondre à au plus une valeur.

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

Si vous choisissez de mettre en œuvre un Set sans Map sauvegarde, vous devez dupliquer du code conçu pour empêcher les éléments en double. Ah, la délicieuse ironie.

Cela dit, rien ne vous empêche de mise en œuvre de votre Sets différemment.

Answer 2

Ma conjecture est que HashSet a été initialement mis en œuvre en termes de table de hachage afin de le faire rapidement et facilement. En termes de lignes de code, HashSet est une fraction de la table de hachage.

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

Toutefois, les déchets sont bien pire que vous le pensez. Sur les versions 32-bit et 64-bit, HashSet est 4x plus grande que nécessaire, et HashMap est 2x plus grande que nécessaire. HashMap pourraient être mises en œuvre avec un tableau avec les clés et les valeurs qu'il contient (en plus de chaînes pour les collisions). Cela signifie que deux pointeurs par entrée, ou 16 octets sur une version 64 bits de VM. En fait, la table de hachage contient une Entrée par entrée, qui ajoute 8 octets pour le pointeur à l'Entrée et 8 octets pour l'Entrée d'en-tête objet. HashSet utilise également 32 octets par élément, mais les déchets est de 4x au lieu de 2x, car il ne nécessite 8 octets par élément.

Answer 3

Je suppose que cela n'est jamais apparu comme un problème important pour les applications réelles ou les repères importants. Pourquoi compliquer le code sans aucun avantage réel?

Notez également que la taille des objets est arrondie dans de nombreuses implémentations JVM, il peut donc ne pas y avoir d'augmentation de taille (je ne sais pas pour cet exemple). Le code pour HashMap est également susceptible d'être compilé et mis en cache. Toutes choses étant égales par ailleurs, plus de code => plus de cache raté => moins de performances.

Answer 4

Oui, vous avez raison, une petite quantité de gaspillage est definetley là. Petite parce que, pour chaque entrée, il utilise le même objet, PRESENT(ce qui est déclaré définitif). Par conséquent, la seule gaspillage est pour chaque entrée de la valeur dans la table de hachage.

Surtout, je pense, ils ont adopté cette approche pour la maintenabilité et la réutilisabilité. (Le JCF les développeurs ont pensé, nous avons testé HashMap de toute façon, pourquoi ne pas réutiliser.)

Mais si vous avez de grandes collections, et vous êtes un mémoire freak, alors vous pouvez opter pour les meilleures solutions de rechange comme la Mine ou Google Collections.

Answer 5

J'ai regardé votre question et il m'a fallu un peu de temps pour réfléchir sur ce que vous avez dit. Voici donc mon avis sur le HashSet mise en œuvre.

Il est nécessaire d'avoir le mannequin exemple pour savoir si la valeur est ou n'est pas présent dans le jeu.

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 à le mettre valeur de retour

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

Si l' PRESENT objet est utilisée pour représenter l'ensemble contient la valeur de e. Je pense que vous avez demandé pourquoi ne pas utiliser null au lieu de PRESENT. Mais la, vous ne seriez pas en mesure de distinguer si l'entrée était déjà sur la carte, car map.put(key,value) serait toujours revenir null et vous n'auriez pas moyen de savoir si la clé existe.

---

Cela étant dit, on pourrait dire qu'ils auraient pu utiliser une application comme ceci

   public boolean add(E e) {

        if( map.containsKey(e) ) {
            return false;
        }

        map.put(e, null);

        return true;

}

Je suppose qu'ils déchets 4 octets pour éviter le calcul de la hashCode, comme il pourrait l'être cher, de la clé deux fois (si la clé va être ajoutée).

---

Si vous la question de pourquoi ils ont utilisé un HashMap qui feraient perdre 8 octets (en raison de l' Map.Entry) à la place 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 que vous avez mentionnées.