Orden de iteración de HashSet

Question

Si cada objeto añadido a un java.util.HashSet implementa Object.equals() y Object.hashCode() de manera determinista, el orden de iteración sobre el HashSet garantiza que será idéntico para cada conjunto idéntico de elementos agregados, independientemente de del orden en el que se agregaron?

Pregunta de bonificación: ¿qué sucede si el orden de inserción es idéntico también?

(suponiendo Sun JDK6 con HashSet misma inicialización.)

Editar: Mi pregunta original no estaba claro. No se trata del contrato general de HashSet, sino de lo que la implementación de Sun de HashSet en JDK6 ofrece como garantía con respecto al determinismo. ¿Es intrínsecamente no determinista? ¿Qué influye en el orden utilizado por su iterador?

Answer 1

Absolutamente no.

El orden de inserción influye directamente en el orden de iteración cada vez que tenga un cubo de colisión:

Cuando dos elementos terminan en el mismo cubo, el primero que se insertó también será el primero regresó durante la iteración, por lo menos si la implementación del manejo de la colisión y la iteración es directa (y la que está en el java.util.HashMap de Sun)

Answer 2

No, esto no está garantizado.

En primer lugar, diferentes JVM pueden implementar el algoritmo HashSet de forma diferente (siempre que cumpla con la especificación HashSet) por lo que obtendrá diferentes resultados en diferentes JVM.

En segundo lugar, el algoritmo puede basarse en factores no deterministas cuando construye los diferentes segmentos (parte del algoritmo hash-table).

Answer 3

Según el javadoc:

Esta clase implementa la interfaz Conjunto , respaldado por una tabla hash (en realidad una instancia HashMap). Es no hace garantías en cuanto al orden de iteración del conjunto; en particular, no garantiza que la orden se mantendrá constante durante tiempo. [...] Los iteradores devueltos por el método iterador de esta clase son a prueba de rápida: si el conjunto está modificada en cualquier momento después de crear el iterador

Y el método iterator:

Devuelve un iterador sobre los elementos en este conjunto. Los elementos se devuelven sin ningún orden en particular.

Así que no creo que pueda hacer una suposición.

Answer 4

No hay garantía "oficial" para algo como esto. Yo diría que probablemente sea cierto para instancias de la misma implementación de HashSet, inicializadas de la misma manera. Pero he visto casos para el orden de iteración diferente entre Java 5 y 6, por ejemplo.

Además, puede ser diferente para las instancias de la misma implementación de HashSet, inicializada con diferente tamaño, debido a la repetición. Es decir. si tiene 100 elementos y dos conjuntos, uno inicializado con un tamaño superior a 100, el otro con un tamaño mucho más pequeño, el segundo se reasignará y sus elementos se repetirán varias veces mientras se llenan. Esto puede hacer que los elementos asignados al mismo contenedor se agreguen (y, por lo tanto, se repitan) en un orden diferente.

En Java4 y posterior, tiene LinkedHashSet que garantiza que el orden de iteración será el orden en que se insertaron sus elementos.

Answer 5

Estoy seguro de que los desarrolladores de Java quieren que suponer que la respuesta es "no". En particular, para las tablas hash, ¿por qué harían que sea más lento para todos los que no necesitan esta propiedad garantizar que los objetos cuyos hashes chocan (idéntico tamaño hashCode%) se observen en el mismo orden, independientemente del orden en el que estaban ¿meter en?

Answer 6

Tal suposición no puede hacerse. El javadoc dice que:

Esta clase implementa la interfaz Conjunto , respaldado por una tabla hash (en realidad una instancia HashMap). Es no hace garantías en cuanto al orden de iteración del conjunto; en particular, no garantiza que la orden se mantendrá constante durante tiempo.

Lo más cercano que puede obtener es usar un LinkedHashSet, que mantiene el orden de inserción.

Answer 7

Nunca haga suposiciones sobre el orden de iteración de cualquier cosa que ponga en un HashSet porque su contrato dice explícitamente que no puede contar con él de ninguna manera. Use LinkedHashSet si desea mantener el orden de inserción o TreeSet si desea mantener un orden de clasificación natural.

Answer 8

Quiero confirmar o canjear comentarios anteriores. En resumen, No confíe en la iteración HashSet en el orden consistente. Esto puede y va a introducir errores en su sistema.

simplemente Hemos encontrado y corregido un error en el orden de iteración era inconsistente en HashSet incluso con:

• orden de inserción idénticos.
• Objetos de una clase con un método válido equals() y hashCode().

Y lo arregló mediante el uso de LinkedHashSet.

Gracias a los carteles anteriores :)

Answer 9

El orden de los objetos aparecen dependerá del número final de cubos de la HashSet. Al cambiar el factor de carga y/o la capacidad inicial, puede cambiar el orden en que terminan los elementos.

En el siguiente ejemplo, puede ver estas confirmaciones cada resultado en un orden diferente.

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); 
} 

impresiones

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]