El marco de colecciones de Java es un conjunto de clases e interfaces que implementan estructuras de datos de colecciones comúnmente reutilizables . [1]
Aunque se le conoce como marco , funciona como una biblioteca . El marco de colecciones proporciona interfaces que definen varias colecciones y clases que las implementan.
CollectionLos s y las matrices son similares en que ambos contienen referencias a objetos y pueden administrarse como un grupo. Sin embargo, a diferencia de las matrices, Collectionno es necesario asignar a s una determinada capacidad cuando se crean instancias. CollectionLos mensajes de texto pueden crecer y reducirse de tamaño automáticamente cuando se agregan o eliminan objetos.
Collections no puede contener tipos de datos primitivos como int, longo double. [2] En cambio, Collections puede contener clases contenedoras como java.lang.Integer, java.lang.Longo java.lang.Double. [3]
CollectionLos s son genéricos y, por tanto, invariantes, pero los arreglos son covariantes . Esto puede considerarse una ventaja de los objetos genéricos, como Collectionen comparación con las matrices, porque, en determinadas circunstancias, el uso de genéricos Collectionen lugar de una matriz evita excepciones en tiempo de ejecución al generar en su lugar una excepción en tiempo de compilación para informar al desarrollador que corrija el código. Por ejemplo, si un desarrollador declara un Object[]objeto y asigna el Object[]objeto al valor devuelto por una nueva Long[]instancia con una determinada capacidad, no se generará ninguna excepción en tiempo de compilación. Si el desarrollador intenta agregar un Stringa este Long[]objeto, el programa Java generará un archivo ArrayStoreException. Por otro lado, si el desarrollador declaró una nueva instancia de a Collection<Object>as ArrayList<Long>, el compilador de Java generará (correctamente) una excepción en tiempo de compilación para indicar que el código está escrito con un tipo incompatible e incorrecto, evitando así cualquier posible error en tiempo de ejecución. excepciones. El desarrollador puede corregir el código creando instancias Collection<Object>como un ArrayList<Object>objeto. Si el código utiliza Java SE7 o versiones posteriores, el desarrollador puede crear una instancia Collection<Object>como un ArrayList<>objeto utilizando el operador de diamante [2]
CollectionLos s son genéricos y, por tanto, cosificados , pero los arrays no están cosificados. [2]
CollectionLas implementaciones en versiones anteriores a JDK 1.2 de la plataforma Java incluían pocas clases de estructura de datos, pero no contenían un marco de colecciones. [4] Los métodos estándar para agrupar objetos Java eran a través de la matriz, el Vectory las Hashtableclases, que desafortunadamente no eran fáciles de extender y no implementaban una interfaz de miembro estándar. [5] [ se necesita una mejor fuente ]
Para abordar la necesidad de estructuras de datos de colección reutilizables , se desarrollaron varios marcos independientes, [4] siendo el más utilizado el paquete Collections de Doug Lea , [6] y la Biblioteca de colecciones genéricas ObjectSpace (JGL), [7] cuyo principal objetivo era la coherencia. con la biblioteca de plantillas estándar (STL) de C++ . [8] [ se necesita una mejor fuente ]
El marco de colecciones fue diseñado y desarrollado principalmente por Joshua Bloch y se introdujo en JDK 1.2 . Reutilizó muchas ideas y clases del paquete Colecciones de Doug Lea , que como resultado quedó obsoleto. [6] Sun Microsystems optó por no utilizar las ideas de JGL porque querían un marco compacto y la coherencia con C++ no era uno de sus objetivos. [9] [ se necesita una mejor fuente ]
Posteriormente, Doug Lea desarrolló un paquete de concurrencia que comprende nuevas clases relacionadas con la Colección. [10] Se incluyó una versión actualizada de estas utilidades de concurrencia en JDK 5.0 a partir de JSR 166 .
Casi todas las colecciones en Java se derivan de la java.util.Collectioninterfaz. CollectionDefine las partes básicas de todas las colecciones.
La interfaz tiene los métodos add(E e)y remove(E e)para agregar y eliminar respectivamente Collection. También tiene el toArray()método que convierte Collectionen una matriz de Objects en Collection(con tipo de retorno de Object[]). [11] Finalmente, el contains(E e)método verifica si un elemento específico existe en el archivo Collection.
La Collectioninterfaz es una subinterfaz de java.lang.Iterable, por lo que cualquiera Collectionpuede ser el destino de una declaración for-each . (La Iterableinterfaz proporciona el iterator()método utilizado por las declaraciones for-each). Todos Collectionlos s tienen un java.util.Iteratorque recorre todos los elementos del Collection.
Collectiones genérico. Cualquiera Collectionpuede almacenar cualquiera Object. Por ejemplo, cualquier implementación de Collection<String>contiene Stringobjetos. No se requiere conversión cuando se utilizan Stringobjetos de una implementación de Collection<String>. [12] Tenga en cuenta que los corchetes angulares < >pueden contener un argumento de tipo que especifica qué tipo Collectionse mantiene. [13]
Existen varios tipos genéricos de Collection: Colas , mapas , listas y conjuntos .
Las colas permiten al programador insertar elementos en un orden determinado y recuperarlos en el mismo orden. Un ejemplo es una lista de espera. Las interfaces básicas para las colas se denominan Queue.
Los diccionarios/mapas almacenan referencias a objetos con una clave de búsqueda para acceder a los valores del objeto. Un ejemplo de clave es una tarjeta de identificación. La interfaz base para diccionarios/mapas se llama Map.
Las listas son colecciones finitas donde se puede almacenar el mismo valor varias veces.
Los conjuntos son colecciones desordenadas que se pueden iterar y contienen cada elemento como máximo una vez. La interfaz base para conjuntos se llama Set. [3]
Las listas se implementan en el marco de colecciones a través de la java.util.Listinterfaz. Define una lista como esencialmente una versión más flexible de una matriz. Los elementos tienen un orden específico y se permiten elementos duplicados. Los elementos se pueden colocar en una posición específica. También se pueden buscar dentro de la lista.
Hay varias clases concretas que implementan List, incluidas AbstractListtodas sus subclases correspondientes, así como CopyOnWriteArrayList.
Las subclases directas de AbstractListclase incluyen AbstractSequentialListy ArrayList.Vector
AbstractListes un ejemplo de implementación esquelética , que aprovecha y combina las ventajas de las interfaces y las clases abstractas al facilitar al desarrollador el desarrollo de su propia implementación para la interfaz determinada. [14]
La java.util.ArrayListclase implementa Listcomo una matriz. Siempre que se requieren funciones específicas de a List, la clase mueve los elementos dentro de la matriz para poder hacerlo.
La java.util.LinkedListclase almacena los elementos en nodos y cada uno tiene un puntero al nodo anterior y siguiente en el archivo List. Se Listpuede recorrer siguiendo los punteros, y se pueden agregar o eliminar elementos simplemente cambiando los punteros para colocar el nodo en su lugar adecuado. [15]
La Vectorclase tiene Stackcomo subclase directa. Este es un ejemplo de una violación del principio de composición sobre herencia en las bibliotecas de la plataforma Java, ya que en informática , un vector generalmente no es una pila . [16] La composición habría sido más apropiada en este escenario. [dieciséis]
La clase Stack extendscon java.util.Vectorcinco operaciones que permiten que a Vectorsea tratado como un Stack. Las pilas se crean usando java.util.Stack. Ofrece Stackmétodos para colocar un nuevo objeto en Stack(método push(E e)) y obtener objetos del Stack(método pop()). A Stackdevuelve el objeto según el último en entrar, primero en salir (LIFO), por ejemplo, el objeto que se colocó más tarde en Stackse devuelve primero. java.util.Stackes una implementación estándar de una pila proporcionada por Java.
La Stackclase representa una pila de objetos de último en entrar, primero en salir (LIFO). La clase Stack tiene cinco operaciones adicionales que permiten Vectortratar a a como un archivo Stack. Se proporcionan las operaciones habituales push(E e)y pop(), así como un método ( peek()) para echar un vistazo al elemento superior de Stack, un método para comprobar si Stackestá vacío ( empty()) y un método para buscar Stackun elemento y descubrir qué tan lejos está. desde la parte superior ( search(Object o)). Cuando Stackse crea a por primera vez, no contiene elementos.
Extiende CopyOnWriteArrayListla Objectclase y no extiende ninguna otra clase. CopyOnWriteArrayListpermite la seguridad de subprocesos sin realizar una sincronización excesiva. [17]
En algunos escenarios, la sincronización es obligatoria. Por ejemplo, si un método modifica un campo estático y varios subprocesos deben llamar al método, entonces la sincronización es obligatoria y CopyOnWriteArrayListno se deben utilizar utilidades de concurrencia como. [17]
Sin embargo, la sincronización puede generar una sobrecarga de rendimiento. Para escenarios donde la sincronización no es obligatoria, entonces es CopyOnWriteArrayListuna alternativa viable y segura para subprocesos a la sincronización que aprovecha los procesadores multinúcleo y da como resultado una mayor utilización de la CPU . [17]
La java.util.Queueinterfaz define la estructura de datos de la cola, que almacena los elementos en el orden en que se insertan. Las nuevas incorporaciones van al final de la línea y los elementos se eliminan del frente. Crea un sistema de primero en entrar, primero en salir . Esta interfaz está implementada por java.util.LinkedList, java.util.ArrayDequey java.util.PriorityQueue.
Las subclases directas de clase AbstractQueueincluyen ArrayBlockingQueue, ConcurrentLinkedQueue, DelayeQueue, LinkedBlockingDeque. y .LinkedBlockingQueueLinkedTransferQueuePriorityBlockingQueue
Tenga en cuenta que ArrayDequey ConcurrentLinkedDequeambos extienden, AbstractCollectionpero no extienden, ninguna otra clase abstracta como AbstractQueue.
AbstractQueuees un ejemplo de implementación esquelética .
La java.util.PriorityQueueclase lo implementa java.util.Queue, pero también lo modifica. [18] PriorityQueue tiene un comparator()método adicional. [18] En lugar de ordenar los elementos en el orden en que se insertan, se ordenan por prioridad. El método utilizado para determinar la prioridad es el java.lang.Comparable#compareTo(T)método de los elementos o un método proporcionado en el constructor. La clase crea esto usando un montón para mantener los elementos ordenados. [19]
La java.util.concurrent.ConcurrentLinkedQueueclase se extiende . implementa la interfaz. [20]java.util.AbstractQueueConcurrentLinkedQueuejava.util.Queue
La ConcurrentLinkedQueueclase es una colección segura para subprocesos, ya que para cualquier elemento colocado dentro de ConcurrentLinkedQueue, la biblioteca de colecciones de Java garantiza que el elemento se publique de forma segura al permitir que cualquier subproceso obtenga el elemento de la colección. [21] Se dice que un objeto se publica de forma segura si el estado del objeto se hace visible para todos los demás subprocesos en el mismo momento. [21] La publicación segura generalmente requiere la sincronización de los hilos de publicación y consumo. [21]
La java.util.concurrent.BlockingQueueinterfaz se extiende Queue. [20]
La BlockingQueueinterfaz tiene las siguientes subinterfaces directas: BlockingDequey TransferQueue. BlockingQueueFunciona como un archivo Queue, pero las adiciones y eliminaciones del mismo BlockingQueueestán bloqueando. [22] Si remove(Object o)se llama en un archivo vacío BlockingQueue, se puede configurar para que espere un tiempo específico o indefinidamente para que aparezca un elemento en el archivo BlockingQueue. De manera similar, agregar un elemento usando el método add(Object o)está sujeto a una restricción de capacidad opcional en BlockingQueue, y el método puede esperar a que haya espacio disponible antes BlockingQueuede regresar. BlockingQueueLa interfaz introduce un método take()que elimina y obtiene el encabezado de BlockingQueue, y espera hasta que BlockingQueueya no esté vacío si es necesario. [23] [24]
La Dequeinterfaz amplía la Queueinterfaz. [25] Deque crea una cola de dos extremos. Mientras que un regular Queuesolo permite inserciones en la parte trasera y extracciones en la parte delantera, Dequepermite que las inserciones o extracciones se realicen tanto en la parte delantera como en la trasera. A Dequees como a Queueque se puede usar hacia adelante o hacia atrás, o ambos a la vez. Además, se puede generar un iterador tanto hacia adelante como hacia atrás. La Dequeinterfaz está implementada por java.util.ArrayDequey java.util.LinkedList. [26]
LinkedList, por supuesto, también implementa la Listinterfaz y también se puede utilizar como tal. Pero también tiene los Queuemétodos. LinkedListimplementa la java.util.Dequeinterfaz, dándole más flexibilidad. [27]
ArrayDequeimplementa el Queuecomo una matriz. Similar a LinkedList, ArrayDequetambién implementa la java.util.Dequeinterfaz. [27]
La java.util.concurrent.BlockingDequeinterfaz se extiende java.util.concurrent.BlockingQueue. [25] BlockingDeque es similar a BlockingQueue. Proporciona los mismos métodos de inserción y extracción con límites de tiempo de espera para que la inserción o extracción sea posible. Sin embargo, la interfaz también proporciona la flexibilidad de un archivo Deque. Las inserciones y extracciones pueden realizarse en ambos extremos. La función de bloqueo se combina con la Dequefunción. [28]
La interfaz de Java java.util.Setdefine el Set. A Setno puede tener elementos duplicados. Además, Setno tiene un orden establecido. Como tal, los elementos no se pueden encontrar por índice. Setes implementado por java.util.HashSet, java.util.LinkedHashSety java.util.TreeSet.
Hay varias implementaciones de la interfaz Set, incluidas AbstractSetsus subclases y la clase interna estática final (donde y son parámetros de tipo formal).ConcurrentHashMap.KeySetView<K,V>KV
AbstractSetes una implementación esquelética de la Setinterfaz. [14]
Subclases directas de AbstractSetinclude ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSety HashSet.TreeSet
La EnumSetclase se extiende AbstractSet. La EnumSetclase no tiene constructores públicos y solo contiene métodos de fábrica estáticos. [29]
EnumSetContiene el método de fábrica estático . [30] Este método es un método de agregación. [29] Toma varios parámetros, tiene en cuenta el tipo de parámetros y luego devuelve una instancia con el tipo apropiado. [29] A partir de 2018, en Java SE8, la implementación OpenJDK utiliza dos implementaciones que son invisibles para el cliente, que son y . [29] Si ya no proporciona ningún beneficio de rendimiento para tipos de enumeración pequeños, podría eliminarse de la biblioteca sin afectar negativamente a la biblioteca de la colección Java. [29]EnumSet.of()EnumSetRegularEnumSetJumboEnumSetRegularEnumSet
EnumSetEs un buen reemplazo para los campos de bits , que es un tipo de conjunto, como se describe a continuación. [30]
Tradicionalmente, siempre que los desarrolladores encontraban elementos de un tipo enumerado que debían colocarse en un conjunto, el desarrollador usaba el patrón de enumeración int en el que a cada constante se le asigna una potencia diferente de 2. [30] Esta representación de bits permite al desarrollador usar la operación OR bit a bit, de modo que las constantes se puedan combinar en un conjunto, también conocido como campo de bits . Esta representación de campo de bits permite al desarrollador realizar operaciones eficientes basadas en conjuntos y aritmética bit a bit, como intersecciones y uniones. [30]
Sin embargo, existen muchos problemas con el enfoque de representación de campos de bits . Un campo de bits es menos legible que una constante de enumeración interna. [30] Además, si los elementos están representados por campos de bits, es imposible iterar a través de todos estos elementos. [30]
Un enfoque alternativo recomendado es utilizar un EnumSet, donde se utiliza una enumeración int en lugar de un campo de bits . [30] Este enfoque utiliza un EnumSetpara representar el conjunto de valores que pertenecen al mismo Enumtipo. [30] Dado que EnumSetimplementa la Setinterfaz y ya no requiere el uso de operaciones bit a bit, este enfoque es más seguro para los tipos. [30] Además, hay muchas fábricas estáticas que permiten la creación de instancias de objetos, como el método método . [30]EnumSet.of()
Después de la introducción de EnumSet, el enfoque de representación de campos de bits se considera obsoleto. [30]
HashSetutiliza una tabla hash. Más específicamente, utiliza a java.util.LinkedHashMappara almacenar los hashes y elementos y para evitar duplicados.
La java.util.LinkedHashSetclase se extiende HashSetcreando una lista doblemente enlazada que vincula todos los elementos por su orden de inserción. Esto garantiza que el orden de iteración Setsea predecible.
CopyOnWriteArraySetes un reemplazo concurrente de un archivo sincronizado Set. Proporciona una concurrencia mejorada en muchas situaciones al eliminar la necesidad de realizar una sincronización o hacer una copia del objeto durante la iteración, de forma similar a cómo CopyOnWriteArrayListactúa como reemplazo concurrente de un objeto sincronizado List. [31]
Por otro lado, similar a CopyOnWriteArrayList, CopyOnWriteArraySetno debe usarse cuando la sincronización es obligatoria.
La java.util.SortedSetinterfaz amplía la java.util.Setinterfaz. A diferencia de un Set, los elementos de a SortedSetse ordenan, ya sea por el método del elemento compareTo(T o)o por un método proporcionado al constructor de SortedSet. El primer y último elemento de SortedSetse pueden recuperar utilizando los métodos first()y last()respectivamente, y los subconjuntos se pueden crear mediante valores mínimos y máximos, así como comenzando o terminando al principio o al final de SortedSet. La java.util.TreeSetclase implementa la SortedSetinterfaz. [32]
La java.util.NavigableSetinterfaz amplía la java.util.SortedSetinterfaz y tiene algunos métodos adicionales. Los métodos floor(E e), ceiling(E e), lower(E e)y higher(E e)encuentran un elemento en el conjunto que esté cerca del parámetro. Además, Setse proporciona un iterador descendente sobre los elementos del . Al igual que con SortedSetlos java.util.TreeSetimplementos NavigableSet. [33]
java.util.TreeSetutiliza un árbol rojo-negro implementado por java.util.TreeMap. El árbol rojo-negro garantiza que no haya duplicados. Además, permite TreeSetimplementar java.util.SortedSet. [34]
ConcurrentSkipListSetactúa como un reemplazo concurrente para las implementaciones de un archivo sincronizado SortedSet. Por ejemplo, reemplaza a TreeSetque ha sido envuelto por el synchronizedMapmétodo. [35]
Los mapas están definidos por la java.util.Mapinterfaz en Java.
Los mapas son estructuras de datos que asocian una clave con un elemento. Esto permite que el mapa sea muy flexible. Si la clave es el código hash del elemento, Mapes esencialmente un archivo Set. Si es sólo un número creciente, se convierte en una lista.
Ejemplos de Mapimplementaciones incluyen java.util.HashMap, java.util.LinkedHashMapy java.util.TreeMap.
AbstractMapes un ejemplo de implementación esquelética . [14]
Las subclases directas de clase AbstractMapincluyen ConcurrentSkipListMap, EnumMap, HashMap, IdentityHashMapy TreeMap.WeakHashMap
EnumMapse extiende AbstractMap. EnumMaptiene una velocidad comparable con una matriz indexada ordinal. [36] Esto se debe a que EnumMapinternamente utiliza una matriz, con detalles de implementación completamente ocultos para el desarrollador. [36] Por lo tanto, EnumMap obtiene la seguridad de tipo de un Maptiempo y las ventajas de rendimiento de una matriz. [36]
HashMaputiliza una tabla hash . Los hashes de las claves se utilizan para encontrar los elementos en varios depósitos. Es HashMapuna colección basada en hash. [37]
LinkedHashMapse extiende HashMapcreando una lista doblemente enlazada entre los elementos, permitiendo acceder a ellos en el orden en que fueron insertados en el mapa. LinkedHashMapcontiene un protected removeEldestEntrymétodo que es llamado por el putmétodo cada vez que se agrega una nueva clave al archivo Map. [38] Elimina Mapsu entrada más antigua cada vez que removeEldestEntrydevuelve verdadero. [38] El removeEldestEntrymétodo se puede anular. [38]
TreeMap, a diferencia de HashMapy LinkedHashMap, utiliza un árbol rojo-negro. Las claves se utilizan como valores para los nodos del árbol, y los nodos apuntan a los elementos del archivo Map. [39]
ConcurrentHashMapes similar HashMapy también es una colección basada en hash. [37] Sin embargo, existen una serie de diferencias, como las diferencias en la estrategia de bloqueo que utilizan.
Utiliza ConcurrentHashMapuna estrategia de bloqueo completamente diferente para proporcionar escalabilidad y simultaneidad mejoradas. [37] ConcurrentHashMap no sincroniza todos los métodos usando el mismo bloqueo. [37] En su lugar, ConcurrentHashMaputilice un mecanismo conocido como franjas de bloqueo . [37] Este mecanismo proporciona un mecanismo de bloqueo más fino. [37] También permite un mayor grado de acceso compartido. [37]
ConcurrentSkipListMapactúa como un reemplazo concurrente para las implementaciones de un archivo sincronizado SortedMap. ConcurrentSkipListMapes muy similar a ConcurrentSkipListSet, ya que ConcurrentSkipListMapreemplaza a TreeMapque ha sido envuelto por el synchronizedMapmétodo. [35]
La java.util.SortedMapinterfaz amplía la java.util.Mapinterfaz. Esta interfaz define una Mapque está ordenada por las claves proporcionadas. Utilizando, una vez más, el compareTo()método o un método proporcionado en el constructor del SortedMap, los pares clave-elemento se ordenan por claves. La primera y la última clave Mapse pueden llamar utilizando los métodos firstKey()y lastKey()respectivamente. Además, se pueden crear submapas a partir de claves mínimas y máximas utilizando el subMap(K fromKey, K toKey)método. SortedMapes implementado por java.util.TreeMap. [40]
La java.util.NavigableMapinterfaz se extiende java.util.SortedMapde varias maneras. Se pueden llamar métodos que encuentren la clave o la entrada del mapa más cercana a la clave dada en cualquier dirección. El mapa también se puede invertir y a partir de él se puede generar un iterador en orden inverso. Está implementado por java.util.TreeMap. [41]
La java.util.concurrent.ConcurrentMapinterfaz amplía la java.util.Mapinterfaz. Esta interfaz es una Mapinterfaz segura para subprocesos, introducida a partir de la versión 1.5 del marco de colecciones Java del lenguaje de programación Java . [20]
El marco de colecciones de Java se amplía con la biblioteca Apache Commons Collections, que agrega tipos de colecciones como una bolsa y un mapa bidireccional, así como utilidades para crear uniones e intersecciones. [42]
Google ha lanzado sus propias bibliotecas de colecciones como parte de las bibliotecas de guayaba .
Antes de que Collections hiciera su debut más bienvenido, los métodos estándar para agrupar objetos Java eran a través de la matriz, el Vector y la Hashtable. Estas tres colecciones tienen diferentes métodos y sintaxis para acceder a los miembros: las matrices usan los símbolos de corchetes ([]), Vector usa el método elementAt y Hashtable usa
y
métodos.
getput
El Sun Java Development Kit JDK1.2 finalmente incluye un conjunto estándar de clases de colección. Si bien existen algunas diferencias de diseño e implementación, el paquete JDK1.2 contiene la mayoría de las mismas abstracciones, estructura y funcionalidad básicas que este paquete. Por este motivo, este paquete de colecciones NO se actualizará más.
Al igual que el propio Java, la biblioteca genérica de Java se basa en gran medida en el campo de C++: toma lo mejor del STL de C++, dejando atrás los defectos de C++. La mayoría de los programadores de C++ actuales conocen su STL, pero pocos logran explotar su potencial.
Comparar JGL de ObjectSpace Inc. y Collections Framework de Sun resulta ser como comparar manzanas y kiwis. A primera vista, los dos marcos parecen competir por los mismos desarrolladores, pero después de una inspección más cercana queda claro que los dos no se pueden comparar de manera justa sin reconocer primero que los dos marcos tienen objetivos diferentes. Si, como dice la documentación de Sun, Colecciones va a homogeneizar las propias API de Sun (API principal, extensiones, etc.), entonces claramente Colecciones tiene que ser una gran noticia, y algo bueno, incluso para el adicto a JGL más fanático. Siempre que Sun no incumpla su promesa en esta área, estaré feliz de invertir mis recursos en adoptar Colecciones en serio.
Nota: Tras el lanzamiento de J2SE 5.0, este paquete ingresa al modo de mantenimiento: solo se publicarán las correcciones esenciales. El paquete J2SE5 java.util.concurrent incluye versiones estandarizadas, más eficientes y mejoradas de los componentes principales de este paquete.
