Pourquoi ne HashSet mise en œuvre dans Sun Java utiliser HashMap que sa sauvegarde?

En fait, ce n'est pas seulement HashSet. Tous les implémentations de la Set interface en Java 6 sont basés sur un sous-jacent Map. 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 de 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 similaires interfaces, en ce que les éléments en double ne sont pas autorisés. (Je pense que la seule Set pas soutenu par une Map est CopyOnWriteArraySet, qui est une étonnante Collection, parce qu'il est immuable.)

Spécifiquement:

De la la documentation de 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'Ensemble de 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
supplémentaires stipulations.)

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 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 la 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.

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.

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.

Prendre un coup d'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é).

De sorte que le 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 parce que 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 la 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.

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

Juste une variable Objet est créé pour l'ensemble de la discbased de hashset et de faire qui permettrait de sauver de la ré-écriture de l'ensemble de la table de hachage type de code à nouveau.

private static final Object PRESENT = new Object();

Toutes les touches sont ayant une valeur que j'ai.e objet.