Ordine di iterazione di HashSet

Se ogni object aggiunto a un java.util.HashSet implementa Object.equals () e Object.hashCode () in modo deterministico, è l’ordine di iterazione su HashSet garantito per essere identico per ogni insieme identico di elementi aggiunti, indipendentemente dal ordine in cui sono stati aggiunti?

Domanda bonus: cosa succede se l’ordine di inserimento è identico?

(Supponendo Sun JDK6 con la stessa inizializzazione di HashSet.)

Modifica: la mia domanda originale non era chiara. Non si tratta del contratto generale di HashSet, ma di quello che l’implementazione di Sun di HashSet in JDK6 offre come garanzia riguardo al determinismo. È intrinsecamente non deterministico? Cosa influenza l’ordine utilizzato dal suo Iterator?

Assolutamente no.

L’ordine di inserzione influenza direttamente l’ordine di iterazione ogni volta che si verifica una collisione con benna:

Quando due elementi finiscono nello stesso bucket, il primo che è stato inserito sarà anche il primo restituito durante l’iterazione, almeno se l’implementazione della gestione e dell’iterazione della collisione è semplice (e quella di java.util.HashMap è java.util.HashMap )

Non esiste una garanzia “ufficiale” per qualcosa di simile. Direi che probabilmente è vero per le istanze della stessa implementazione di HashSet, inizializzate allo stesso modo. Ma ho visto casi in cui l’ordine di iterazione è diverso tra Java 5 e 6, per esempio.

Inoltre, potrebbe essere diverso per le istanze della stessa implementazione di HashSet, inizializzate con dimensioni diverse, a causa del rehashing. Cioè se avete 100 elementi e due set, uno inizializzato con una dimensione maggiore di 100, l’altro con una dimensione molto più piccola, il secondo verrà riallocato e i suoi elementi ridisegnati più volte durante il riempimento. Ciò potrebbe comportare l’aggiunta di elementi mappati allo stesso bucket (e quindi ripetuti) in un ordine diverso.

In Java4 e versioni successive, hai LinkedHashSet che garantisce che l’ordine di iterazione sarà l’ordine in cui sono stati inseriti i suoi elementi.

Come per la javadoc:

Questa class implementa l’interfaccia Set, supportata da una tabella hash (in realtà un’istanza di HashMap). Non fornisce garanzie sull’ordine di iterazione del set; in particolare, non garantisce che l’ordine rimanga costante nel tempo. […] Gli iteratori restituiti dal metodo iteratore di questa class sono veloci: se il set viene modificato in qualsiasi momento dopo la creazione dell’iteratore

E il metodo iterator :

Restituisce un iteratore sugli elementi in questo set. Gli elementi vengono restituiti in nessun ordine particolare.

Quindi non penso che tu possa fare una simile ipotesi.

Volevo confermare / aggiornare i commenti precedenti. In breve, non eseguire l’iterazione HashSet in ordine coerente . Questo può e introdurrà bug nel tuo sistema.

Abbiamo appena trovato e corretto un bug in cui l’ordine di iterazione era incoerente in HashSet anche con:

  • Ordine di inserzione identico.
  • Oggetti di una class con un metodo valido equals () e hashCode ().

E riparato usando LinkedHashSet.

Grazie ai poster precedenti 🙂

No, questo non è garantito.

Innanzitutto, la JVM diversa può implementare l’algoritmo HashSet in modo diverso (purché sia ​​conforms alle specifiche HashSet) in modo da ottenere risultati diversi su JVM diversi.

In secondo luogo, l’algoritmo può basarsi su fattori non deterministici quando costruisce i diversi bucket (parte dell’algoritmo della tabella hash).

Mai e poi mai fare assunzioni sull’ordine di iterazione di qualcosa che hai inserito in un HashSet perché il suo contratto dice esplicitamente che non puoi contare su di esso in alcun modo. Utilizzare LinkedHashSet se si desidera mantenere l’ordine di inserimento o TreeSet se si desidera mantenere un ordinamento naturale.

Gli oggetti ordine visualizzati dipendono dal numero finale di bucket di HashSet. Modificando il fattore di carico e / o la capacità iniziale è ansible modificare l’ordine in cui gli elementi finiscono.

Nell’esempio seguente, è ansible visualizzare queste conferme ogni risultato in un ordine diverso.

 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 set = new HashSet(size, loadFactor); for(int i=0;i<=100;i+=10) set.add(i); System.out.println("new HashSet("+size+", "+loadFactor+") adding 0,10, ... 100 => "+set); } 

stampe

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

Sono sicuro che gli sviluppatori Java vogliono che tu pensi che la risposta sia “no”. In particolare, per le tabelle hash, perché renderebbero più lento per tutti gli altri che non hanno bisogno di questa proprietà per garantire che gli oggetti il ​​cui hash si scontrino (identici dimensioni hashCode%) vengano osservati nello stesso ordine indipendentemente dall’ordine in cui erano mettere in?

Tale ipotesi non può essere fatta. Il javadoc dice che:

Questa class implementa l’interfaccia Set, supportata da una tabella hash (in realtà un’istanza di HashMap). Non fornisce garanzie sull’ordine di iterazione del set; in particolare, non garantisce che l’ordine rimanga costante nel tempo.

Il più vicino è ansible utilizzare un LinkedHashSet , che mantiene l’ordine di inserimento.