El comienzo del camino
Hoy me gustaría hablaros de un tema tan interesante como es el “
Java Collections Framework ” o, en términos sencillos, de colecciones. La mayor parte del trabajo del código consiste en procesar datos de una forma u otra. Obtenga una lista de usuarios, obtenga una lista de direcciones, etc. De alguna manera ordenarlos, realizar una búsqueda, compararlos. Es por eso que el conocimiento de las colecciones se considera una habilidad básica. Por eso quiero hablar de ello. Además, una de las preguntas más comunes en las entrevistas con desarrolladores de Java son las colecciones. Por ejemplo, "dibujar una jerarquía de colecciones". El compilador en línea nos ayudará en nuestro camino. Por ejemplo, puede utilizar " Tutorialspoint
Online Java Compiler " o
Repl.it. El camino para conocer cualquier estructura de datos comienza con variables ordinarias (Variables). En el sitio web de Oracle, varios temas se representan como "rutas" o senderos. Entonces, el camino para conocer Java se llama "
Sendero: Aprender el lenguaje Java: Tabla de contenido ". Y los conceptos básicos del lenguaje (es decir, conceptos básicos del lenguaje) comienzan con Variables. Por lo tanto, escribamos un código simple:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Es bueno en todo, excepto que entendemos que este código es bueno y hermoso solo para una variable. ¿Qué hacer si son varios? Las matrices se inventaron para almacenar datos de un tipo. En el mismo Trail de Oracle hay una sección separada dedicada a las matrices. Esta sección se llama: "
Arrays ". Trabajar con matrices también es bastante sencillo:
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
Las matrices resuelven el problema de almacenar múltiples valores en un solo lugar. Pero impone una limitación: el tamaño de la matriz es constante. Si, como en el ejemplo, dijimos que tamaño = 2, entonces es igual a dos. Eso es todo. Si queremos una matriz más grande, necesitamos crear una nueva instancia. Además, encontrar un elemento también es complicado para una matriz. Existe un método
Arrays.binarySearch, pero esta búsqueda solo funciona en una matriz ordenada (para una matriz no ordenada, el resultado no está definido o simplemente es impredecible). Es decir, la búsqueda nos obligará a ordenar cada vez. Eliminar también simplemente borra el valor. Por lo tanto, todavía no sabemos cuántos datos hay realmente en la matriz, solo sabemos cuántas celdas hay en la matriz. Para actualizar sus conocimientos sobre matrices:
Y como consecuencia del desarrollo del lenguaje Java, apareció Java Collections Framework en JDK 1.2, del que hablaremos hoy.
Recopilación
Comience a calcular costos desde el principio. ¿Por qué colecciones? El término en sí proviene de cosas como "teoría de tipos" y "tipos de datos abstractos". Pero si no nos fijamos en ningún asunto importante, entonces cuando tenemos varias cosas, podemos llamarlas una “colección de cosas”. Los que coleccionan artículos. En general, la palabra recolectar proviene del lat. collectionio "reunir, coleccionar". Es decir, una colección es una colección de algo, un contenedor para algunos elementos. Entonces tenemos una colección de elementos. Qué podríamos querer hacer con él:
Como puedes ver, es posible que queramos cosas bastante lógicas. También entendemos que es posible que queramos hacer algo con varias colecciones:
En consecuencia, los desarrolladores de Java escribieron la interfaz java.util.Collection para describir este comportamiento general para todas las colecciones . La interfaz de Colección es donde se originan todas las colecciones. La colección es una idea, es una idea de cómo deberían comportarse todas las colecciones. Por tanto, el término "Colección" se expresa como una interfaz. Naturalmente, una interfaz necesita implementaciones. La interfaz
java.util.Collectiontiene una clase abstracta
AbstractCollection, es decir, una “colección abstracta”, que representa el esqueleto para otras implementaciones (como está escrito en el JavaDoc encima de la clase
java.util.AbstractCollection). Hablando de colecciones, regresemos y recordemos que queremos iterar sobre ellas. Esto significa que queremos recorrer los elementos uno por uno. Este es un concepto muy importante. Por lo tanto, la interfaz
Collectionse hereda de
Iterable. Esto es muy importante porque... En primer lugar, todo Iterable debe poder devolver un Iterador en función de su contenido. Y en segundo lugar, todo lo que Iterable se puede utilizar en bucles
for-each-loop. Y es con la ayuda de un iterador que se implementan
AbstractCollectionmétodos como
contains, . Y el camino hacia la comprensión de las colecciones comienza con una de las estructuras de datos más comunes: una lista, es decir. .
toArrayremoveList
Liza
Así, las listas ocupan un lugar importante en la jerarquía de colecciones:
Como podemos ver, las listas implementan la interfaz
java.util.List . Las listas expresan que tenemos una colección de elementos que están dispuestos en alguna secuencia, uno tras otro. Cada elemento tiene un índice (como en una matriz). Normalmente, una lista le permite tener elementos con el mismo valor. Como dijimos anteriormente,
Listconoce el índice del elemento. Esto le permite obtener (
get) un elemento por índice o establecer un valor para un índice específico (
set). Los métodos de colección
add, le permiten especificar el índice desde el cual ejecutarlos. Además, y tiene su propia versión de un iterador llamado . Este iterador conoce el índice del elemento, por lo que puede iterar no sólo hacia adelante sino también hacia atrás. Incluso se puede crear desde un lugar específico de la colección. Entre todas las implementaciones, hay dos más utilizadas: y . Primero, es una lista ( ) basada en una matriz ( ). Esto le permite lograr "acceso aleatorio"
a los elementos. El acceso aleatorio es la capacidad de recuperar inmediatamente un elemento por índice, en lugar de recorrer todos los elementos hasta encontrar el elemento con el índice deseado. Es la matriz como base la que permite lograr esto. Por el contrario, es una Lista Enlazada. Cada entrada en una lista enlazada se representa en el formulario , que almacena los datos en sí, así como un enlace a la siguiente (siguiente) y anterior (anterior) . De esta manera implementa el “Acceso Secuencial
” . Está claro que para encontrar el 5º elemento tendremos que ir del primer elemento al último, porque No tenemos acceso directo al quinto elemento. Sólo podemos acceder a él desde el 4º elemento. La diferencia en su concepto se da a continuación:
addAllremoveListListIteratorArrayListLinkedListArrayListListArrayLinkedListEntryEntryLinkedList
En el trabajo, como comprenderás, también hay una diferencia. Por ejemplo, agregando elementos. Los
LinkedListelementos están simplemente conectados como eslabones de una cadena. Pero
ArrayListalmacena elementos en una matriz. Y una matriz, como sabemos, no puede cambiar su tamaño. ¿Cómo funciona entonces
ArrayList? Y funciona de forma muy sencilla. Cuando se acaba el espacio en la matriz, aumenta 1,5 veces. Aquí está el código de zoom:
int newCapacity = oldCapacity + (oldCapacity >> 1); Otra diferencia en el funcionamiento es cualquier desplazamiento de elementos. Por ejemplo, al agregar o quitar elementos en el medio. Para eliminar de
LinkedListun elemento, simplemente elimine las referencias a este elemento. En el caso de ,
ArrayListnos vemos obligados a cambiar los elementos cada vez usando el
System.arraycopy. Así, cuantos más elementos, más acciones habrá que realizar. Puede encontrar una descripción más detallada en estos artículos:
Habiendo examinado ArrayList, uno no puede evitar recordar su "predecesor", la clase
java.util.Vector . Se diferencia
Vectoren
ArrayListque los métodos para trabajar con la colección (agregar, eliminar, etc.) están sincronizados. Es decir, si un hilo (
Thread) agrega elementos, los demás hilos esperarán hasta que el primer hilo termine su trabajo. Dado que la seguridad de subprocesos a menudo no es necesaria, se recomienda utilizar la clase en tales casos
ArrayList, como se indica explícitamente en el JavaDoc de la clase
Vector. Además,
Vectoraumenta su tamaño no 1,5 veces,
ArrayListsino 2 veces. De lo contrario, el comportamiento es el mismo:
Vectorel almacenamiento de elementos en forma de matriz está oculto y agregar/eliminar elementos tiene las mismas consecuencias que en
ArrayList. De hecho,
Vectorlo recordamos por una razón. Si miramos en el Javadoc, veremos en "Subclases conocidas directas" una estructura como
java.util.Stack . La pila es una estructura interesante que es una
last-in-first-outestructura LIFO (último en entrar, primero en salir). Pila traducida del inglés es una pila (como una pila de libros, por ejemplo). La pila implementa métodos adicionales:
peek(mirar, mirar),
pop(empujar),
push(empujar). El método
peekse traduce como mirar (por ejemplo,
mirar dentro de la bolsa se traduce como “
mirar dentro de la bolsa ”, y
mirar por el ojo de la cerradura se traduce como “
mirar por el ojo de la cerradura ”). Este método le permite mirar la "parte superior" de la pila, es decir. obtenga el último elemento sin eliminarlo (es decir, sin eliminarlo) de la pila. El método
pushempuja (agrega) un nuevo elemento a la pila y lo devuelve, y el método del elemento
popempuja (elimina) y devuelve el eliminado. En los tres casos (es decir, mirar, abrir y empujar), solo trabajamos con el último elemento (es decir, la "parte superior de la pila"). Ésta es la característica principal de la estructura de pila. Por cierto, hay una tarea interesante para comprender las pilas, descrita en el libro "La carrera de un programador" (entrevista sobre codificación de cracking). Hay una tarea interesante en la que, utilizando la estructura de "pila" (LIFO), es necesario implementar la "cola". ”estructura (FIFO). Debe tener un aspecto como este:
Puede encontrar un análisis de esta tarea aquí: "
Implementar una cola usando pilas: la cola ADT ("Implementar una cola usando pilas" en LeetCode) ". Entonces pasamos sin problemas a una nueva estructura de datos: una cola.
Cola
Una cola es una estructura que nos es familiar en la vida. Colas a las tiendas, a los médicos. Quien llegue primero (First In) será el primero en abandonar la cola (First Out). En Java, una cola está representada por la interfaz
java.util.Queue . Según el Javadoc de la cola, la cola agrega los siguientes métodos:
Como puede ver, hay métodos de orden (no ejecutarlos conlleva una excepción) y métodos de solicitud (la imposibilidad de ejecutarlos no genera errores). También es posible conseguir el elemento sin quitarlo (peek o elemento). La interfaz de cola también tiene un sucesor útil:
Deque . Esta es la llamada "cola de dos vías". Es decir, dicha cola le permite utilizar esta estructura tanto desde el principio como desde el final. La documentación dice que "Deques también se puede usar como pilas LIFO (último en entrar, primero en salir). Esta interfaz debe usarse con preferencia a la clase Stack heredada", es decir, se recomienda usar implementaciones de Deque en lugar de Pila. El Javadoc muestra qué métodos describe la interfaz Deque:
Veamos qué implementaciones hay. Y veremos un hecho interesante: LinkedList ha entrado en el campo de las colas) Es decir, LinkedList implementa tanto
List, como
Deque. Pero también existen “solo colas”, por ejemplo
PriorityQueue. Pocas veces se la recuerda, pero es en vano. En primer lugar, no puede utilizar "objetos no comparables" en esta cola, es decir Se debe especificar Comparador o todos los objetos deben ser comparables. En segundo lugar, "esta implementación proporciona tiempo O(log(n)) para los métodos de puesta en cola y retirada de cola". La complejidad logarítmica existe por una razón. Implementado PriorityQueue basado en el montón. El Javadoc dice: "Cola de prioridad representada como un montón binario equilibrado". El almacenamiento en sí para esto es una matriz normal. Que crece cuando es necesario. Cuando el montón es pequeño, aumenta 2 veces. Y luego en un 50%. Comentario del código: "Duplica el tamaño si es pequeño; de lo contrario, crece un 50%". La cola de prioridad y el montón binario son un tema aparte. Entonces para más información:
Como implementación,
java.util.Dequepuede utilizar la clase
java.util.ArrayDeque . Es decir, las listas se pueden implementar usando una lista vinculada y una matriz, y las colas también se pueden implementar usando una matriz o una lista vinculada. Las interfaces
Queuey
Dequetienen descendientes que representan la "cola de bloqueo":
BlockingQueuey
BlockingDeque. Aquí está el cambio de interfaz en comparación con las colas normales:
Veamos algunos ejemplos de colas de bloqueo. Pero son interesantes. Por ejemplo, BlockingQueue se implementa mediante:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Pero
BlockingDequeimplementan todo, desde los marcos de colección estándar
LinkedBlockingDeque. Cada cola es tema de una revisión separada. Y en el marco de esta revisión, representaremos la jerarquía de clases no solo con
List, sino también con
Queue:
Como podemos ver en el diagrama, las interfaces y clases del Java Collections Framework están altamente entrelazadas. Agreguemos otra rama de la jerarquía:
Set.
Colocar
Set- traducido como "conjunto". Se diferencia de una cola y una lista
Seten su mayor abstracción sobre el almacenamiento de elementos.
Set- como una bolsa de objetos, donde se desconoce cómo se encuentran los objetos y en qué orden se encuentran. En Java, dicho conjunto está representado por la interfaz
java.util.Set . Como dice la documentación,
Setesta es una "colección que no contiene elementos duplicados". Curiosamente, la interfaz en sí
Setno agrega nuevos métodos a la interfaz
Collection, solo aclara los requisitos (sobre qué no debe contener duplicados). Además, de la descripción anterior se deduce que no se puede simplemente
Setobtener un elemento de él. Iterador se utiliza para obtener elementos.
Settiene varias interfaces más asociadas. El primero es
SortedSet. Como sugiere el nombre,
SortedSetindica que dicho conjunto está ordenado y, por lo tanto, los elementos implementan la interfaz
Comparableo están especificados
Comparator. Además,
SortedSetofrece varios métodos interesantes:
Además, existen métodos
first(elemento más pequeño por valor) y
last(elemento más grande por valor). Hay
SortedSetun heredero -
NavigableSet. El propósito de esta interfaz es describir los métodos de navegación necesarios para identificar con mayor precisión los elementos apropiados. Una cosa interesante es
NavigableSetque agrega al iterador habitual (que va de menor a mayor) un iterador en orden inverso:
descendingIterator. Además,
NavigableSette permite utilizar el método
descendingSetpara obtener una vista de ti mismo (View), en la que los elementos están en orden inverso. Se llama así
Viewporque a través del elemento resultante se pueden cambiar los elementos del original
Set. Es decir, en esencia, se trata de una representación de los datos originales de otra forma, y no de una copia de los mismos. Curiosamente,
NavigableSetal igual que
Queue, puede manejar elementos
pollFirst(mínimos) y (máximos).
pollLastEs decir, obtiene este elemento y lo elimina del conjunto. ¿Qué tipo de implementaciones existen? En primer lugar, la implementación más famosa se basa en un código hash:
HashSet . Otra implementación igualmente conocida se basa en un árbol rojo-negro:
TreeSet . Completemos nuestro diagrama:
Dentro de las colecciones, queda por clasificar la jerarquía: los ermitaños. Que a primera vista se queda a un lado -
java.util.Map.
Mapas
Los mapas son una estructura de datos en la que los datos se almacenan por clave. Por ejemplo, la clave podría ser un ID o un código de ciudad. Y es mediante esta clave que se buscarán los datos. Es interesante que las cartas se muestren por separado. Según los desarrolladores (consulte "
Preguntas frecuentes sobre el diseño de API de colecciones de Java "), el mapeo clave-valor no es una colección. Y los mapas pueden considerarse más rápidamente como una colección de claves, una colección de valores, una colección de pares clave-valor. Este es un animal muy interesante. ¿Qué métodos proporcionan las tarjetas? Veamos la interfaz API de Java
java.util.Map . Porque Dado que los mapas no son colecciones (no heredan de las Colecciones), no contienen un archivo
contains. Y esto es lógico. Un mapa consta de claves y valores. ¿Cuál de estos debería comprobar el método
containsy cómo no confundirse? Por tanto, la interfaz
Maptiene dos versiones diferentes:
containsKey(contiene una clave) y
containsValue(contiene un valor). Usarlo
keySette permite obtener un juego de llaves (la misma
Set). Y usando el método
valuespodemos obtener una colección de valores en el mapa. Las claves en el mapa son únicas, lo que se enfatiza en la estructura de datos
Set. Los valores se pueden repetir, lo que se enfatiza en la estructura de datos de la Colección. Además, utilizando el método
entrySetpodemos obtener un conjunto de pares clave-valor. Puedes leer más sobre qué implementaciones de tarjetas hay en los análisis más detallados:
También me gustaría ver qué es
HashMapmuy similar a
HashSety
TreeMapa
TreeSet. Incluso tienen interfaces similares:
NavigableSety
NavigableMap,
SortedSety
SortedMap. Entonces nuestro mapa final se verá así:
Podemos terminar con el hecho interesante de que la colección
Setutiliza internamente
Map, donde los valores agregados son claves y el valor es el mismo en todas partes. Esto es interesante porque
Mapno es una colección y regresa
Set, que es una colección pero de hecho está implementada como
Map. Un poco surrealista, pero así resultó)
Conclusión
La buena noticia es que esta reseña termina aquí. La mala noticia es que este es un artículo muy reseñable. Cada implementación de cada una de las colecciones merece un artículo aparte, y también para cada algoritmo oculto a nuestros ojos. Pero el propósito de esta revisión es recordar qué son y cuáles son las conexiones entre las interfaces. Espero que después de una lectura atenta puedas dibujar de memoria un diagrama de las colecciones.
Bueno, como siempre, algunos enlaces:
#viacheslav
GO TO FULL VERSION