Marco de colecciones de Java

El marco de colecciones de Java es un conjunto de clases e interfaces que implementan estructuras de datos de colección comúnmente reutilizables . ^[1]

Aunque se lo conoce como un 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 el sentido de que ambos contienen referencias a objetos y se pueden administrar como un grupo. Sin embargo, a diferencia de las matrices, Collectionno es necesario asignarles a los s una capacidad determinada cuando se instancian. CollectionLos s pueden aumentar o disminuir de tamaño automáticamente cuando se agregan o eliminan objetos.

Collections no puede contener tipos de datos primitivos como int, long, o double. ^[2] En cambio, Collections puede contener clases contenedoras como java.lang.Integer, java.lang.Long, o java.lang.Double. ^[3]

CollectionLos objetos genéricos son genéricos y, por lo tanto, invariantes, pero los arreglos son covariantes . Esto puede considerarse una ventaja de los objetos genéricos, como Collectioncuando se comparan con los arreglos, porque, en determinadas circunstancias, el uso del genérico Collectionen lugar de un arreglo evita excepciones en tiempo de ejecución al lanzar en su lugar una excepción en tiempo de compilación para informar al desarrollador que arregle 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 cierta capacidad, no se lanzará ninguna excepción en tiempo de compilación. Si el desarrollador intenta agregar un Stringa este Long[]objeto, el programa Java lanzará un ArrayStoreException. Por otro lado, si el desarrollador en cambio declaró una nueva instancia de un Collection<Object>como ArrayList<Long>, el compilador Java lanzará (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 excepción en tiempo de ejecución. El desarrollador puede arreglar el código al crear una instancia Collection<Object>como un ArrayList<Object>objeto. Si el código usa Java SE7 o versiones posteriores, el desarrollador puede crear una instancia Collection<Object>como un ArrayList<>objeto usando el operador de diamante ^[2]

CollectionLos s son genéricos y, por lo tanto, están cosificados , pero las matrices no están cosificadas. ^[2]

CollectionLas implementaciones en versiones anteriores a JDK 1.2 de la plataforma Java incluían pocas clases de estructuras 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, la Vectory las Hashtableclases, que lamentablemente 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 los más utilizados el paquete Collections de Doug Lea , ^[6] y ObjectSpace Generic Collection Library (JGL), ^[7] cuyo objetivo principal era la coherencia con la biblioteca de plantillas estándar de C++ (STL). ^{[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 Collections de Doug Lea , que quedó obsoleto como resultado. ^[6] Sun Microsystems decidió 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 comprendía nuevas clases relacionadas con Collection. ^[10] Una versión actualizada de estas utilidades de concurrencia se incluyó 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 quitar de un Collectionrespectivamente. También tiene el toArray()método , que convierte el Collectionen una matriz de Objects en el Collection(con tipo de retorno de Object[]). ^[11] Finalmente, el contains(E e)método verifica si un elemento especificado existe en el Collection.

La Collectioninterfaz es una subinterfaz de java.lang.Iterable, por lo que cualquier Collectionpuede ser el objetivo 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 pasa por todos los elementos en el Collection.

Collectiones genérico. Cualquiera Collectionpuede almacenar cualquier Object. Por ejemplo, cualquier implementación de Collection<String>contiene Stringobjetos. No se requiere conversión cuando se utilizan los 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 Collectioncontiene . ^[13]

Hay 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 y 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 de los diccionarios y mapas se denomina 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 que contienen cada elemento como máximo una vez. La interfaz base para los conjuntos se denomina Set. ^[3]

Las listas se implementan en el marco de colecciones a través de la java.util.Listinterfaz. Define una lista como 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 AbstractListy todas sus subclases correspondientes, así como CopyOnWriteArrayList.

Las subclases directas de AbstractListla clase incluyen AbstractSequentialList, ArrayListy Vector.

AbstractListes un ejemplo de una 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 dada. ^[14]

La java.util.ArrayListclase implementa a Listcomo una matriz. Siempre que se requieren funciones específicas de a List, la clase mueve los elementos dentro de la matriz para hacerlo.

La java.util.LinkedListclase almacena los elementos en nodos que tienen cada uno un puntero al nodo anterior y al siguiente en el List. ListSe puede recorrer el nodo siguiendo los punteros, y se pueden agregar o quitar elementos simplemente cambiando los punteros para colocar el nodo en su lugar apropiado. ^[15]

La Vectorclase tiene Stackcomo subclase directa. Este es un ejemplo de violación del principio de composición sobre herencia en las bibliotecas de la plataforma Java, ya que en informática , un vector no es generalmente una pila . ^[16] La composición hubiera sido más apropiada en este escenario. ^[16]

extendsLa clase Stack java.util.Vectorcon cinco operaciones que permiten que a Vectorsea tratado como un Stack. Las pilas se crean usando java.util.Stack. La Stackofrece métodos para colocar un nuevo objeto en el Stack(método push(E e)) y para obtener objetos del Stack(método pop()). A Stackdevuelve el objeto según el método LIFO ( último en entrar, primero en salirStack ), por ejemplo, el objeto que se colocó más tarde en el se devuelve primero. java.util.Stackes una implementación estándar de una pila proporcionada por Java.

La Stackclase representa una pila de objetos de tipo último en entrar, primero en salir (LIFO). La clase Stack tiene cinco operaciones adicionales que permiten que a Vectorse trate como un Stack. Se proporcionan las operaciones push(E e)y habituales 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 en y descubrir qué tan lejos está de 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 seguridad de subprocesos sin realizar una sincronización excesiva. ^[17]

CopyOnWriteArrayListEn 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 no se deben utilizar utilidades de concurrencia como ^{[17] .}

Sin embargo, la sincronización puede generar una sobrecarga de rendimiento. Para los escenarios en los que la sincronización no es obligatoria, existe 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 desde el principio. Crea un sistema de primero en entrar, primero en salir . Esta interfaz se implementa mediante java.util.LinkedList, java.util.ArrayDeque, y java.util.PriorityQueue.

Las subclases directas de AbstractQueuela clase incluyen ArrayBlockingQueue, ConcurrentLinkedQueue, DelayeQueue, LinkedBlockingDeque, LinkedBlockingQueue. LinkedTransferQueuey PriorityBlockingQueue.

Tenga en cuenta que tanto . ArrayDequecomo ConcurrentLinkedDeque. se extienden AbstractCollection, pero no extienden ninguna otra clase abstracta como AbstractQueue.

AbstractQueuees un ejemplo de una implementación esquelética .

La java.util.PriorityQueueclase 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 en los elementos o un método dado en el constructor. La clase crea esto utilizando un montón para mantener los elementos ordenados. ^[19]

La java.util.concurrent.ConcurrentLinkedQueueclase extiende e 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 una 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 subprocesos 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 . normal Queue, pero las adiciones y eliminaciones del . BlockingQueueson bloqueantes. ^[22] Si remove(Object o)se llama en un . vacío BlockingQueue, se puede configurar para que espere un tiempo especificado o indefinidamente hasta que aparezca un elemento en el BlockingQueue. De manera similar, agregar un elemento usando el método add(Object o)está sujeto a una restricción de capacidad opcional en el BlockingQueue. y el método puede esperar a que haya espacio disponible en el . BlockingQueueantes de regresar. BlockingQueueLa interfaz introduce un método take()que elimina y obtiene la cabecera del BlockingQueue. y espera hasta que el . BlockingQueueya no esté vacío si es necesario. ^{[23] [24]}

La Dequeinterfaz extiende la Queueinterfaz. ^[25] Deque crea una cola de doble extremo. Mientras que una normal Queuesolo permite inserciones en la parte posterior y eliminaciones en la parte delantera, la Dequepermite que las inserciones o eliminaciones se realicen tanto en la parte delantera como en la posterior. A Dequees como a Queueque se puede utilizar hacia adelante o hacia atrás, o ambos a la vez. Además, se pueden generar iteradores hacia adelante y hacia atrás. La Dequeinterfaz se implementa mediante 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, lo que le da más flexibilidad. ^[27]

ArrayDequeImplementa Queuecomo una matriz. De manera similar a LinkedList, ArrayDequetambién implementa la java.util.Dequeinterfaz. ^[27]

La java.util.concurrent.BlockingDequeinterfaz extiende java.util.concurrent.BlockingQueue. ^[25] BlockingDeque es similar a BlockingQueue. Proporciona los mismos métodos de inserción y eliminación con límites de tiempo para esperar a que la inserción o eliminación sea posible. Sin embargo, la interfaz también proporciona la flexibilidad de un Deque. Las inserciones y eliminaciones pueden tener lugar 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 ningún elemento duplicado. Además, Setno tiene un orden establecido. Por lo tanto, no se pueden encontrar elementos por índice. Setse implementa mediante java.util.HashSet, java.util.LinkedHashSety java.util.TreeSet.

Hay varias implementaciones de la interfaz Set, incluidas AbstractSety sus subclases, y la clase interna estática final (donde y son parámetros de tipo formales). ConcurrentHashMap.KeySetView<K,V>KV

AbstractSetes una implementación esquelética de la Setinterfaz. ^[14]

Subclases directas de AbstractSetinclude ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSety TreeSet.

La EnumSetclase 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 los parámetros y luego devuelve una instancia con el tipo apropiado. ^[29] A partir de 2018, en la implementación de Java SE8 OpenJDK se utilizan dos implementaciones de las cuales son invisibles para el cliente, que son y . ^[29] Si ya no proporcionara 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 colecciones de 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 necesitaban ser colocados en un conjunto, el desarrollador usaba el patrón int enum 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 basadas en conjuntos eficientes 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 int. ^[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 un int enum 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 el EnumSetimplementa la Setinterfaz y ya no requiere el uso de operaciones bit a bit, este enfoque es más seguro en cuanto a tipos. ^[30] Además, hay muchas fábricas estáticas que permiten la instanciación de objetos, como el método method . ^[30]EnumSet.of()

Después de la introducción del EnumSet, el enfoque de representación del campo de bits se considera obsoleto. ^[30]

HashSetUtiliza una tabla hash. Más específicamente, utiliza una 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 para un 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 manera similar a cómo CopyOnWriteArrayListactúa como reemplazo concurrente para un sincronizado List. ^[31] Por otro lado, similar a CopyOnWriteArrayList, CopyOnWriteArraySetno se debe utilizar cuando la sincronización es obligatoria.

La java.util.SortedSetinterfaz extiende la java.util.Setinterfaz. A diferencia de un Set, los elementos de a SortedSetse ordenan, ya sea por el compareTo(T o)método del elemento o por un método proporcionado al constructor de SortedSet. El primer y el último elemento de SortedSetse pueden recuperar utilizando los métodos first()y last()respectivamente, y se pueden crear subconjuntos a través de 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 extiende la java.util.SortedSetinterfaz y tiene algunos métodos adicionales. Los métodos floor(E e), ceiling(E e), lower(E e)y encuentran un elemento en el conjunto que esté cerca del parámetro. Además, se proporciona higher(E e)un iterador descendente sobre los elementos en . Al igual que con , implementa . ^[33]SetSortedSetjava.util.TreeSetNavigableSet

java.util.TreeSetutiliza un árbol rojo-negro implementado por un java.util.TreeMap. El árbol rojo-negro asegura que no haya duplicados. Además, permite TreeSetimplementar java.util.SortedSet. ^[34]

ConcurrentSkipListSetactúa como un reemplazo concurrente para las implementaciones de un sincronizado SortedSet. Por ejemplo, reemplaza un TreeSetque ha sido envuelto por el synchronizedMapmétodo. ^[35]

Los mapas se definen mediante 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 Set. Si es solo un número creciente, se convierte en una lista.

Los ejemplos de Mapimplementaciones incluyen java.util.HashMap, java.util.LinkedHashMap, y java.util.TreeMap.

AbstractMapes un ejemplo de una implementación esquelética . ^[14]

Las subclases directas de la AbstractMapclase incluyen ConcurrentSkipListMap, EnumMap, HashMap, y . IdentityHashMapTreeMapWeakHashMap

EnumMapextiende AbstractMap. EnumMaptiene una velocidad comparable con una matriz indexada ordinal. ^[36] Esto se debe a que EnumMaputiliza internamente una matriz, con detalles de implementación completamente ocultos para el desarrollador. ^[36] Por lo tanto, EnumMap obtiene la seguridad de tipo de un Mapmientras que 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 contenedores. Es HashMapuna colección basada en hashes. ^[37]

LinkedHashMapse extiende HashMapcreando una lista doblemente enlazada entre los elementos, lo que permite acceder a ellos en el orden en que se insertaron en el mapa. LinkedHashMapcontiene un protected removeEldestEntrymétodo que es llamado por el putmétodo siempre que se agrega una nueva clave al Map. ^[38] El Mapelimina su entrada más antigua siempre que removeEldestEntrydevuelve verdadero. ^[38] El removeEldestEntrymétodo puede ser anulado. ^[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 Map. ^[39]

ConcurrentHashMapes similar a HashMapy también es una colección basada en hash. ^[37] Sin embargo, existen varias diferencias, como las diferencias en la estrategia de bloqueo que utilizan.

Utiliza ConcurrentHashMapuna estrategia de bloqueo completamente diferente para proporcionar una escalabilidad y una concurrencia mejoradas. ^[37] ConcurrentHashMap no sincroniza todos los métodos que utilizan el mismo bloqueo. ^[37] En su lugar, ConcurrentHashMaputiliza un mecanismo conocido como bloqueo por franjas . ^[37] Este mecanismo proporciona un mecanismo de bloqueo de grano 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 sincronizado SortedMap. ConcurrentSkipListMapes muy similar a ConcurrentSkipListSet, ya que ConcurrentSkipListMapreemplaza a un TreeMapque ha sido envuelto por el synchronizedMapmétodo. ^[35]

La java.util.SortedMapinterfaz extiende la java.util.Mapinterfaz. Esta interfaz define un Mapque se ordena por las claves proporcionadas. Usando, una vez más, el compareTo()método o un método proporcionado en el constructor para el SortedMap, los pares de clave-elemento se ordenan por las claves. La primera y la última clave en el Mapse pueden llamar usando los métodos firstKey()y lastKey()respectivamente. Además, se pueden crear submapas a partir de claves mínimas y máximas usando el subMap(K fromKey, K toKey)método . SortedMapse implementa mediante 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 se puede generar un iterador en orden inverso a partir de él. Se implementa mediante java.util.TreeMap. ^[41]

La java.util.concurrent.ConcurrentMapinterfaz extiende 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 de Java del lenguaje de programación Java . ^[20]

El marco de colecciones de Java se extiende mediante la biblioteca Apache Commons Collections, que agrega tipos de colección 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 guava .

• Recopilación
• Recipiente
• Biblioteca de plantillas estándar
• Concurrencia en Java
• Mapa concurrente de Java

• Bloch, Joshua (2018). "Effective Java: Programming Language Guide" (tercera edición). Addison-Wesley. ISBN 978-0134685991.
• Goetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Concurrencia en Java en la práctica. Addison Wesley. ISBN 0-321-34960-1.OL  25208908M .