En cuanto a la fuente de Java 6, HashSet<E> se implementa realmente utilizando HashMap<E,Object>, utilizando la instancia de objeto ficticio en cada entrada del conjunto.¿Por qué la implementación de HashSet en Sun Java usa HashMap como respaldo?
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.
Sus principales preguntas son
Pero, ¿por qué todavía se utilizan? ¿Existe alguna razón para usar además de hacer que sea más fácil de mantener 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, en que los elementos duplicados no están permitidos. (Creo que la única Setno respaldado por una Map es CopyOnWriteArraySet, que es una colección inusual, porque es inmutable.)
Específicamente:
Desde el documentation of Set:
Una colección que no contiene elementos duplicados. Más formalmente, los conjuntos no contienen ningún par de elementos e1 y e2 tal que e1.equals (e2), y en la mayoría de un elemento nulo. Según lo implícito en su nombre, esta interfaz modela la abstracción del conjunto matemático .
La interfaz Conjunto coloca estipulaciones adicionales, más allá de las heredadas desde la interfaz de la recogida en el contratos de todos los constructores y en los contratos del complemento, es igual y métodos hashCode. Las declaraciones para otros métodos heredados también son incluidos aquí para mayor comodidad. (Los especificaciones que acompañan a estas declaraciones se han adaptado a la interfaz Set, pero que no contienen las estipulaciones adicionales.)
La estipulación adicional sobre constructores se ofrecen, como es lógico, que todos los constructores deben crear una conjunto que no contiene elementos duplicados (como se define anteriormente).
Y desde Map:
Un objeto que se asigna a los valores claves. Un mapa no puede contener claves duplicadas; cada tecla se puede asignar a un máximo de un valor.
Si se puede poner en práctica sus Set s utilizando el código existente, ningún beneficio (velocidad, por ejemplo), puede darse cuenta de código existente se acumula a su Set también.
Si elige implementar un Set sin un respaldo Map, debe duplicar el código diseñado para evitar la duplicación de elementos. Ah, la deliciosa ironía.
Dicho esto, no hay nada que le impida implementar su Set de manera diferente.
"Todas las implementaciones de la interfaz' Set' en Java 6 se basan en una 'Colección' subyacente." (Supongo que te refieres a 'Mapa' en lugar de' Colección'.) Existe al menos un ejemplo de contador (que no sean subconjuntos y similares). 'EnumSet' no se basa en un' Mapa'. –
Hay una posibilidad más: podría haberse implementado como Map
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). También es probable que el código para HashMap esté compilado y en caché. En igualdad de condiciones, más código => más falta de memoria => menor rendimiento.
Sí, tiene razón, una pequeña cantidad de desperdicio definitivamente está allí. Pequeño porque, para cada entrada, usa el mismo objeto PRESENT (que se declara como final). Por lo tanto, el único desperdicio es para el valor de cada entrada en HashMap.
Principalmente creo que adoptaron 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 tienes grandes colecciones, y eres un fanático de la memoria, entonces puedes optar por mejores alternativas como Trove o Google Collections.
Residuo adicional es tener que almacenar una referencia a la clave, que puede ser grande si tiene millones de entradas en el conjunto.8bytes * 1M objetos = 8MB de residuos –
Miré su pregunta y me tomó un tiempo pensar en lo que dijo. Así que aquí está mi opinión con respecto a la implementación HashSet.
Es necesario tener la instancia ficticia para saber si el valor está o no presente en el conjunto.
Tome un vistazo al método add
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
Abd ahora vamos a echar un vistazo al valor de retorno de venta
@returns el valor previo asociado con llave, o null si no hubo mapeo de clave. (Un retorno nulo también puede indicar que el mapa asociado previamente con la tecla nula.)
Por lo tanto el objeto PRESENT sólo se utiliza para representar que el conjunto contiene el valor e. Creo que preguntaste por qué no usar null en 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 forma de saber si la clave existía.
Dicho esto se podría argumentar que se podría haber utilizado una aplicación como esta
public boolean add(E e) {
if(map.containsKey(e)) {
return false;
}
map.put(e, null);
return true;
}
supongo que los residuos 4 bytes para evitar calcular el código hash, ya que podría ser costoso, de la llave dos veces (si se va a agregar la llave).
Si cuestión planteada por qué utilizaron un HashMap que sería una pérdida de 8 bytes (debido a la Map.Entry) en lugar de alguna otra estructura de datos utilizando una entrada similar de sólo el 4, entonces sí, yo diría que lo hicieron por las razones que mencionaste
Supongo que HashSet se implementó originalmente en términos de HashMap para hacerlo de forma 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.
Tu pregunta es: 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 nuevamente.
private static final Object PRESENT = new Object();
Todas las teclas están teniendo un valor es decir objeto presente.
Después de buscar a través de páginas como esta preguntándose por qué la implementación estándar ligeramente ineficientes, encontró com.carrotsearch.hppc.IntOpenHashSet
@yuku: el nivel de residuos en las colecciones de Java por defecto se mindboggling. Los peores delincuentes ocurren cuando manipulas primitivos. ¿Crees que un HashSet
@yuku: para continuar en mi comentario ... Lo que quiero decir es: o bien perfs y memoria importan y luego tienes que encontrar una alternativa porque el nivel de desperdicio en las colecciones predeterminadas de Java es demasiado alto o no necesitas Las perforaciones y la memoria no importan, ya que utilizará una pequeña cantidad de elementos y las colecciones predeterminadas de Java son correctas (es probable que haya una mejor alternativa como las colecciones de Google, etc.) – SyntaxT3rr0r
@WizardOfOdds: son muchas afirmaciones audaces con poca evidencia para respaldarlos. – skaffman