Ordre d'itération de HashSet

Si chaque objet ajouté à java.util.HashSet implémente l'Objet.equals() et de l'Objet.hashCode() dans une manière déterministe, est l'itération de l'ordre sur le HashSet la garantie d'être identique pour tous identiques ensemble d'éléments ajoutés, indépendamment de l'ordre dans lequel ils ont été ajoutés?

Question Bonus: que faire si l'ordre d'insertion est identique?

(En supposant que le Soleil JDK6 avec le même HashSet d'initialisation.)

Edit: Ma question d'origine n'était pas claire. Il n'est pas sur le contrat de HashSet, mais ce Soleil est de la mise en œuvre de HashSet dans JDK6 offre que des garanties concernant le déterminisme. Est-il intrinsèquement non-déterministe? Ce qui influence l'ordre utilisé par son Itérateur?

source d'informationauteur eljenso

  1. 15

    Absolument pas.

    L'ordre d'insertion, influe directement sur l'itération de l'ordre chaque fois que vous avez un seau de collision:

    Lorsque deux éléments se retrouvent dans la même seau, le premier qui a été inséré sera également la première, un seul est revenu au cours d'une itération, au moins si la mise en œuvre de la collision de la manipulation et de l'itération est simple (et celui du Soleil java.util.HashMap est)

  2. 12

    Il n'est pas "officiel" garantie pour quelque chose comme cela. Je dirais que c'est probablement vrai pour les instances de la même HashSet mise en œuvre, initialisés de la même manière. Mais j'ai vu des cas pour l'itération afin d'être différents entre Java 5 et 6, par exemple.

    Aussi, il peut être différent pour les instances de la même HashSet mise en œuvre, initialisé avec la taille différente, en raison de ressasser. I. e. si vous disposez de 100 éléments et de deux ensembles, l'un initialisé avec une taille supérieure à 100, l'autre avec une taille beaucoup plus petite, la seconde pour obtenir réaffectées et de ses éléments rabâchage plusieurs fois pendant le remplissage. Cela peut entraîner des éléments cartographiés à la même seau ajoutée (et donc itéré) dans un ordre différent.

    Dans Java4 et plus tard, vous avez LinkedHashSet qui garantit que l'itération de l'ordre sera à l'ordre dans lequel ses éléments ont été insérés.

  3. 7

    Que par la javadoc:

    Cette classe implémente l'Ensemble
    interface, soutenu par une table de hachage
    (en fait, un HashMap exemple). Il
    ne garantit pas l'
    itération afin de l'ensemble; dans
    en particulier, il ne garantit pas que
    l'ordre demeure constante au cours du
    temps.
    [...]
    Les itérateurs retourné par cette classe iterator de méthode sont fail-fast: si la valeur est modifiée à tout moment après l'itérateur est créé

    Et la méthode iterator:

    Renvoie un itérateur sur les éléments
    dans cet ensemble. Les éléments sont retournés
    dans aucun ordre particulier.

    Donc je ne pense pas que vous pouvez faire une telle hypothèse.

  4. 6

    Voulu confirmer /upvote observations antérieures. En bref, Ne Comptez Pas sur HashSet itération en cohérence. Cela peut et va introduire des bugs dans votre système.

    Que nous venons de trouver et correction d'un bug où l'itération de l'ordre a été incohérent dans HashSet même avec:

    • Identiques ordre d'insertion.
    • Les objets d'une classe avec un valide equals() et hashCode() de la méthode.

    Et il fixe en utilisant LinkedHashSet.

    Grâce à la plus tôt affiches 🙂

  5. 1

    Non, ce n'est pas garanti.

    Tout d'abord, les différentes JVM peut mettre en œuvre le HashSet algorithme différemment (tant qu'il respecte le HashSet spécification) de sorte que vous obtiendrez des résultats différents sur différentes machines virtuelles java.

    Deuxièmement, l'algorithme peut s'appuyer sur la non-déterministe facteurs lorsqu'il construit les compartiments différents (une partie de la table de hachage de l'algorithme).

  6. 1

    Jamais de faire des hypothèses sur l'itération de l'ordre de quelque chose que vous mettez dans un HashSet parce que son contrat explicitement dit que vous ne pouvez pas compter sur elle en quelque sorte. Utilisation LinkedHashSet si vous voulez maintenir l'ordre d'insertion ou TreeSet si vous voulez maintenir un tri naturel de l'ordre.

  7. 1

    L'ordre d'apparition des objets dépend de la finale nombre de compartiments de la HashSet. En changeant le facteur de charge et/ou de la capacité initiale, vous pouvez modifier l'ordre des éléments de la fin.

    Dans l'exemple suivant, vous pouvez voir ces confirguations chaque résultat dans un ordre différent.

    public static void main(String...args) throws IOException {
    printOrdersFor(8, 2);
    printOrdersFor(8, 1);
    printOrdersFor(8, 0.5f);
    printOrdersFor(32, 1f);
    printOrdersFor(64, 1f);
    printOrdersFor(128, 1f);
}

public static void printOrdersFor(int size, float loadFactor) {
    Set<Integer> set = new HashSet<Integer>(size, loadFactor);
    for(int i=0;i<=100;i+=10) set.add(i);
    System.out.println("new HashSet<Integer>("+size+", "+loadFactor+") adding 0,10, ... 100 => "+set);
}

    imprime

    new HashSet<Integer>(8, 2.0) adding 0,10, ... 100 => [0, 50, 100, 70, 40, 10, 80, 20, 90, 60, 30]
new HashSet<Integer>(8, 1.0) adding 0,10, ... 100 => [0, 50, 100, 70, 20, 80, 10, 40, 90, 30, 60]
new HashSet<Integer>(8, 0.5) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 20, 80, 90, 30, 60]
new HashSet<Integer>(32, 1.0) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 80, 20, 90, 60, 30]
new HashSet<Integer>(64, 1.0) adding 0,10, ... 100 => [0, 70, 10, 80, 20, 90, 30, 100, 40, 50, 60]
new HashSet<Integer>(128, 1.0) adding 0,10, ... 100 => [0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
  8. 0

    Je suis sûr que les développeurs Java, voulez-vous de supposer que la réponse est "non". En particulier, pour les tables de hachage, pourquoi auraient-ils le rendre plus lent pour tout le monde qui n'a pas besoin de cette propriété afin de garantir que les objets dont les hachages de choc (identique hashCode % de la taille) sont observées dans le même ordre quel que soit l'ordre dans lequel ils ont été mis en?

  9. 0

    Une telle hypothèse ne peut être faite. La javadoc dit que:

    Cette classe implémente l'Ensemble
    interface, soutenu par une table de hachage
    (en fait, un HashMap exemple). Il
    ne garantit pas l'
    itération afin de l'ensemble; dans
    en particulier, il ne garantit pas que
    l'ordre demeure constante au cours du
    temps.

    Le plus proche que vous pouvez obtenir est d'utiliser un LinkedHashSetqui maintient l'ordre d'insertion.