¿Por qué la implementación de HashSet en Sun Java usa HashMap como respaldo?

Al ver la fuente de Java 6, HashSet se implementa realmente usando HashMap , usando la instancia de objeto ficticio en cada entrada del conjunto.

Creo que desperdicia 4 bytes (en máquinas de 32 bits) para el tamaño de la entrada en sí.

Pero, ¿por qué todavía se usa? ¿Hay alguna razón para usarlo además de facilitar el mantenimiento de los códigos?

En realidad, no es solo HashSet . Todas las implementaciones de la interfaz Set en Java 6 se basan en un Map subyacente. Esto no es un requisito; es solo la forma en que la implementación es. Puede verlo usted mismo revisando la documentación de las diversas implementaciones de Set .

Tus preguntas principales son

Pero, ¿por qué todavía se usa? ¿Hay alguna razón para usarlo además de facilitar el mantenimiento de los códigos?

Supongo que el mantenimiento del código es un gran factor de motivación. Por lo tanto, evita la duplicación y la hinchazón.

Set y Map son interfaces similares, ya que los elementos duplicados no están permitidos. (Creo que el único Set no respaldado por un Map es CopyOnWriteArraySet , que es una Colección inusual, porque es inmutable).

Específicamente:

De la documentación de Set :

Una colección que no contiene elementos duplicados. Más formalmente, los conjuntos no contienen ningún par de elementos e1 y e2 tales como e1.equals (e2), y como máximo un elemento nulo. Tal como lo implica su nombre, esta interfaz modela la abstracción del conjunto matemático.

La interfaz Set establece estipulaciones adicionales, más allá de las heredadas de la interfaz Collection, en los contratos de todos los constructores y en los contratos de los métodos add, equals y hashCode. Las declaraciones para otros métodos heredados también se incluyen aquí por conveniencia. (Las especificaciones que acompañan a estas declaraciones se han adaptado a la interfaz Set, pero no contienen ninguna estipulación adicional).

La estipulación adicional en los constructores es, como es lógico, que todos los constructores deben crear un conjunto que no contenga elementos duplicados (como se definió anteriormente).

Y desde el Map :

Un objeto que asigna claves a valores. Un mapa no puede contener claves duplicadas; cada tecla se puede asignar a un máximo de un valor.

Si puede implementar su Set utilizando el código existente, cualquier beneficio (velocidad, por ejemplo) que pueda obtener del código existente también se acumula en su Set .

Si elige implementar un Set sin un respaldo de Map , debe duplicar el código diseñado para evitar elementos duplicados. Ah, la deliciosa ironía.

Dicho eso, no hay nada que te impida implementar tus Set diferente.

Supongo que nunca ha aparecido como un problema importante para aplicaciones reales o puntos de referencia importantes. ¿Por qué complicar el código sin ningún beneficio real?

También tenga en cuenta que los tamaños de los objetos se redondean en muchas implementaciones de JVM, por lo que es probable que no haya un aumento en el tamaño (no sé para este ejemplo). Además, es probable que el código para HashMap esté comstackdo y en caché. En igualdad de condiciones, más código => más falta de memoria => menor rendimiento.

Mi suposición es que HashSet se implementó originalmente en términos de HashMap para hacerlo de manera rápida y fácil. En términos de líneas de código, HashSet es una fracción de HashMap.

Supongo que la razón por la que todavía no se ha optimizado es el miedo al cambio.

Sin embargo, el desperdicio es mucho peor de lo que piensas. Tanto en 32 bits como en 64 bits, HashSet es 4 veces más grande de lo necesario, y HashMap es 2 veces más grande de lo necesario. HashMap podría implementarse con una matriz con claves y valores (más cadenas para colisiones). Eso significa dos punteros por entrada, o 16 bytes en una máquina virtual de 64 bits. De hecho, HashMap contiene un objeto de entrada por entrada, que agrega 8 bytes para el puntero a la entrada y 8 bytes para el encabezado del objeto de entrada. HashSet también usa 32 bytes por elemento, pero el desperdicio es 4x en lugar de 2x ya que solo requiere 8 bytes por elemento.

Sí, tienes razón, una pequeña cantidad de desperdicio definitivamente está ahí. Pequeño porque, para cada entrada, utiliza el mismo objeto PRESENT (que se declara final). Por lo tanto, el único desperdicio es para el valor de cada entrada en HashMap.

Sobre todo, creo, tomaron este enfoque para su mantenimiento y reutilización. (Los desarrolladores de JCF habrían pensado, hemos probado HashMap de todos modos, ¿por qué no reutilizarlo?)

Pero si tiene grandes colecciones y es un fanático de la memoria, puede optar por mejores alternativas como Trove o Google Collections .

Miré tu pregunta y me tomó un tiempo pensar en lo que dijiste. Así que aquí está mi opinión sobre la implementación de HashSet .

Es necesario tener la instancia ficticia para saber si el valor está o no presente en el conjunto.

Eche un vistazo al método de agregar

 public boolean add(E e) { return map.put(e, PRESENT)==null; } 

Abd ahora echemos un vistazo al valor de retorno puesto

@regresa el valor anterior asociado con la clave, o nulo si no hubo una asignación para la clave. (Un retorno nulo también puede indicar que el mapa asociaba previamente nulo con la clave).

Entonces, el objeto PRESENT se usa para representar que el conjunto contiene el valor e. Creo que preguntaste por qué no usar null lugar de PRESENT . Pero, no podrá distinguir si la entrada estaba previamente en el mapa porque map.put(key,value) siempre devolverá null y no tendría manera de saber si la clave existía.


Dicho esto, podría argumentar que podrían haber utilizado una implementación como esta

  public boolean add(E e) { if( map.containsKey(e) ) { return false; } map.put(e, null); return true; } 

Supongo que desperdician 4 bytes para evitar el cálculo del hashCode, ya que podría ser costoso, de la clave dos veces (si se va a agregar la clave).


Si su pregunta se refiere a por qué usaron un HashMap que desperdiciará 8 bytes (debido a Map.Entry ) en lugar de otra estructura de datos usando una Entrada similar de solo 4, entonces sí, yo diría que lo hicieron por las razones que usted mencionado.

Después de buscar en páginas como esta preguntándose por qué la implementación estándar levemente ineficiente, encontró com.carrotsearch.hppc.IntOpenHashSet

Tu pregunta: Creo que desperdicia 4 bytes (en máquinas de 32 bits) para el tamaño de la entrada en sí.

Solo se crea una variable de Objeto para toda la estructura de datos de hashset, y al hacer esto se evitará volver a escribir todo el tipo de código hashMap.

private static final Object PRESENT = new Object();

Todas las teclas tienen un valor, es decir, el objeto PRESENTE.