Lo que podrían preguntar en una entrevista: Estructuras de datos en Java. Parte 2

PARTE 1 Ahora hablamos de la base que todo desarrollador de Java debe conocer. Sobre ese conocimiento clásico desde el que comienza todo. Hoy me gustaría abordar uno de los temas fundamentales de cualquier entrevista: las estructuras de datos en Java . Entonces, en lugar de andar con rodeos, comencemos. Vea la continuación de la lista de preguntas que le pueden hacer sobre este tema durante una entrevista.

6. Cuéntanos sobre la Lista

Lista es una interfaz que representa una estructura ordenada de objetos, que se denomina lista. El “truco” de esta estructura es que los elementos contenidos en la Lista se pueden insertar, modificar o eliminar por índice, es decir, el identificador interno de la Lista . En otras palabras, índice significa: "cuántos elementos hay desde el principio de la lista". El primer elemento de la Lista tiene el índice 0, el segundo tiene el índice 1, y así sucesivamente. Entonces, el quinto elemento está a cuatro elementos del principio de la lista. Como se mencionó anteriormente, el orden en que se agregan los elementos a una lista es importante. Por eso la estructura de datos se llama lista . Enumeramos métodos exclusivos de esta estructura que tienen como objetivo trabajar con elementos por índice:

• get : devuelve el elemento en la posición especificada (por valor de índice),
• eliminar : elimina el elemento en la posición especificada,
• set : reemplaza el elemento en la posición especificada con el elemento especificado en el método.

Las principales implementaciones son ArrayList y LinkedList . Hablaremos más sobre ellos un poco más adelante. Vector es una lista segura para subprocesos, por lo que cada método de esta clase está sincronizado. Pero tenga en cuenta que si desea proteger algunas acciones de la lista, sincronizará una secuencia completa de operaciones. Y la sincronización de operaciones individuales es menos segura y mucho más lenta. Por supuesto, Vector también tiene un bloqueo superior, incluso si no lo necesita. Por lo tanto, esta clase ahora se considera obsoleta y no se utiliza. Por cierto: ArrayList es similar a Vector , pero no usa bloqueo, por lo que se usa en todas partes. Stack es una subclase de la clase Vector con un constructor predeterminado y todos los métodos de la clase Vector , además de algunos propios (hablaremos de ellos más adelante). Como ejemplo, puedes imaginar el proceso como una pila de carpetas con documentos. Coloca una carpeta en la parte superior de la pila y solo puede tomar estas carpetas en orden inverso, comenzando desde arriba. En realidad, este es un mecanismo de tipo LIFO , es decir, Last In First Out , el último en llegar es el primero en salir. La pila implementa sus propios métodos:

• push : agrega el elemento pasado a la parte superior de la pila;
• vistazo : devuelve el elemento que está en la parte superior de la pila;
• pop : también devuelve el elemento que está en la parte superior de la pila, pero lo elimina;
• vacío : comprueba si la pila está vacía; verdadero o no; falso ;
• buscar : busca en la pila un elemento determinado. Si se encuentra un elemento, se devuelve su número de secuencia relativo a la parte superior de la pila. Si no se encuentra el elemento, se devuelve el valor -1.

Por el momento, la subclase Stack no se utiliza debido a su simplicidad e inflexibilidad, pero, sin embargo, es posible que la encuentres. Por ejemplo, cuando recibes algún error y en la consola ves una pila de mensajes al respecto. Puede leer más sobre la pila y la cola en este artículo .

7. Cuéntanos sobre el mapa

Como se indicó anteriormente, un mapa es una colección que tiene una estructura separada de interfaces y sus implementaciones. Está separado porque aquí los valores no se almacenan uno a la vez, sino en un par “clave-valor”. Métodos básicos de mapas :

• put(tecla K, valor V) : agregar un elemento al mapa;
• get(Clave de objeto) : busca un valor por clave;
• contieneClave(Clave de objeto) : verifica en el Mapa la presencia de esta clave;
• contieneValue(Valor del objeto) : comprueba en el mapa la presencia de este valor;
• eliminar (clave de objeto) : eliminar un valor mediante su clave.

Como puede ver, la mayoría de las operaciones funcionan mediante una clave. Como regla general, se eligen objetos inmutables como claves . Un ejemplo típico de este objeto es String . Implementaciones de mapas básicos :

1. HashMap : diseñado para almacenar valores en orden aleatorio, pero le permite buscar rápidamente elementos del mapa. Le permite especificar una clave usando la palabra clave nula , pero no más de una vez, porque los pares con las mismas claves se escriben uno encima del otro. La condición principal es la unicidad de las claves: los valores se pueden repetir (puede haber varios valores nulos).
2. LinkedHashMap es un análogo de HashMap que almacena valores en el orden en que fueron agregados. En consecuencia, al igual que LinkedList , tiene un encabezado : el encabezado de una lista doblemente enlazada. Cuando se inicializa, apunta a sí mismo.

   LinkedHashMap también tiene un accessOrder que especifica cómo se accederá a los elementos cuando se utilice el iterador. Si accessOrder es falso, el acceso se realizará en el orden en que se insertaron los elementos. Si es verdadero, los elementos estarán en el orden en que se accedió por última vez (el último elemento al que se accedió se colocará al final).

3. TreeMap es un mapa que ordena elementos por valores clave. Similar a TreeSet , pero para pares basados ​​en valores clave. Para establecer reglas de clasificación de TreeMap , las claves deben implementar la interfaz Comparable . De lo contrario, debería haber un Comparador orientado a claves (el que se especifica en el constructor TreeMap ), un TreeSet, implementado con un objeto TreeMap en su interior, en el que, de hecho, ocurre toda la magia.

   Puede leer más sobre la clasificación en TreeMap utilizando árboles rojo-negro en el artículo sobre las características de TreeMap .

4. Hashtable es similar a HashMap , pero no permite almacenar valores nulos ni como claves ni como valores. Está cuidadosamente sincronizado desde un punto de vista de subprocesos múltiples, lo que a su vez significa que es seguro desde un punto de vista de subprocesos múltiples. Pero esta implementación está desactualizada y es lenta, por lo que ahora no verás Hashtable en proyectos más o menos nuevos.

8. Lista de matrices frente a lista vinculada. ¿Cuál es preferible utilizar?

Esta pregunta es quizás la más popular sobre estructuras de datos y conlleva algunos inconvenientes. Antes de responder, aprendamos más sobre estas estructuras de datos. ArrayList implementa la interfaz List y opera en una matriz interna que se expande según sea necesario. Cuando la matriz interna está completamente llena y es necesario insertar un nuevo elemento, se crea una nueva matriz con un tamaño de (oldSize * 1.5) +1. Después de esto, todos los datos de la matriz anterior se copian al elemento nuevo + nuevo, y el recolector de basura eliminará el anterior . El método add agrega un elemento a la última celda vacía de la matriz. Es decir, si ya tenemos 3 elementos allí, agregará el siguiente a la 4ta celda. Repasemos el rendimiento de los métodos básicos:

• get(int index) : tomar un elemento en una matriz por índice es lo más rápido en O(1) ;
• add(Object obj) : si hay suficiente espacio en la matriz interna para un nuevo elemento, entonces con una inserción normal se gastará tiempo O(1) , ya que la adición está dirigida a la última celda.

  Si necesitamos crear una nueva matriz y copiar el contenido en ella, entonces nuestro tiempo será directamente proporcional al número de elementos en la matriz O(n) ;

• remove(int index) : al eliminar un elemento, por ejemplo, del medio, obtendremos un tiempo O(n/2), ya que necesitaremos mover los elementos a la derecha una celda hacia atrás. En consecuencia, si se elimina desde el principio de la lista, entonces O(n), desde el final - O(1);
• add(int index, Object obj) : una situación similar a eliminar: al agregar en el medio, necesitaremos mover los elementos de la derecha una celda hacia adelante, por lo que el tiempo es O(n/2). Por supuesto, desde el principio - O(n), desde el final - O(1);
• set(int index, Object obj) : aquí la situación es diferente, ya que solo necesitas encontrar el elemento deseado y escribir sobre él sin mover el resto, entonces O(1).

Lea más sobre ArrayList en este artículo . LinkedList implementa dos interfaces a la vez: List y Queue y, por lo tanto, tiene propiedades y métodos inherentes a ambas estructuras de datos. Desde Lista accedió a un elemento por índice, desde Cola, por la presencia de una "cabeza" y una "cola". Internamente, se implementa como una estructura de datos que representa una lista doblemente enlazada. Es decir, cada elemento tiene un vínculo con el siguiente y el anterior, excepto la “cola” y la “cabeza”.

• get(int index) : cuando busca un elemento que está en el medio de la lista, comienza a buscar entre todos los elementos en orden hasta encontrar el deseado. Lógicamente la búsqueda debería tomar O(n/2) , pero LinkedList también tiene cola, por lo que la búsqueda se realiza simultáneamente desde ambos lados. En consecuencia, el tiempo se reduce a O(n/4) .

  Si el elemento está cerca del principio o del final de la lista, entonces el tiempo será O(1) ;

• add(Object obj) : al agregar un nuevo elemento, el elemento "cola" tendrá un enlace al siguiente elemento agregado, y el nuevo recibirá un enlace a este elemento anterior y se convertirá en la nueva "cola". En consecuencia, el tiempo será O(1) ;
• remove(int index) : lógica similar al método get(int index) . Para eliminar un elemento del medio de la lista, primero debes encontrarlo. Esto es nuevamente O(n/4) , mientras que la eliminación en sí no requiere nada, ya que solo cambia el puntero de los objetos vecinos (comienzan a referirse entre sí). Si el elemento está al principio o al final, entonces nuevamente - O(1) ;
• add(int index, Object obj) y set(int index, Object obj) : los métodos tendrán una complejidad temporal idéntica a get(int index) , ya que la mayor parte del tiempo se dedica a buscar el elemento. Por lo tanto, para la mitad de la lista - O(n/4) , para el principio - O(1).

En este artículo se describe más información sobre cómo trabajar con LinkedList . Veamos todo esto en una tabla: Como probablemente ya habrá entendido, es imposible responder a esta pregunta de manera inequívoca. Después de todo, en diferentes situaciones trabajan a diferentes velocidades. Por lo tanto, cuando le hagan una pregunta como esta, debe preguntar inmediatamente en qué se centrará esta lista y qué operaciones se realizarán con mayor frecuencia. A partir de esto, da una respuesta, pero con explicaciones de por qué es así. Resumamos nuestra comparación: ArrayList:

• la mejor opción si la operación más frecuente es buscar un elemento, sobrescribiendo un elemento;
• la peor opción si la operación es la inserción y eliminación al principio-medio, porque se realizarán las operaciones de desplazamiento de elementos a la derecha.

Lista enlazada:

• la mejor opción si nuestra operación frecuente es la inserción y eliminación al principio-medio;
• peor opción si la operación más común es la búsqueda.

9. ¿Cómo se almacenan los elementos en un HashMap?

La colección HashMap contiene una tabla Node[] de matriz interna , cuyas celdas también se denominan depósitos . El nodo contiene:

• clave - enlace a la clave,
• valor - referencia al valor,
• hash - valor hash,
• next : enlace al siguiente nodo .

Una celda de la matriz tabla[] puede contener una referencia a un objeto Nodo con un enlace al siguiente elemento Nodo , y puede tener un enlace a otro, y así sucesivamente... Como resultado, estos elementos Nodo pueden formar un lista enlazada individualmente , con elementos con enlace al siguiente. En este caso, el valor hash de los elementos de una cadena es el mismo. Después de una breve digresión, veamos cómo se almacenan los elementos en un HashMap :

1. Se comprueba que la clave sea nula . Si es nulo , la clave se almacenará en la celda de la tabla [0] porque el código hash para nulo es siempre 0.
2. Si la clave no es nula , entonces se llama al método hashcode() del objeto clave , que devolverá su código hash. Este código hash se utiliza para determinar la celda de la matriz donde se almacenará el objeto Nodo.
3. A continuación, este código hash se coloca en el método hash() interno , que calcula el código hash, pero dentro del tamaño de la matriz table[] .
4. A continuación, dependiendo del valor hash, Node se coloca en una celda específica en la matriz table[] .
5. Si la celda de la tabla [] utilizada para guardar el elemento Nodo actual no está vacía, pero ya tiene algún elemento, entonces los elementos Nodo se iteran sobre el siguiente valor hasta llegar al último elemento. Es decir, aquel cuyo siguiente campo es nulo .

   Durante esta búsqueda, la clave del objeto Nodo protegido se compara con las claves de los que se buscan:

   • si se encuentra una coincidencia, la búsqueda finalizará y el nuevo Nodo sobrescribirá el Nodo en el que se encontró la coincidencia (solo se sobrescribirá su campo de valor );
   • Si no se encuentran coincidencias de claves, el nuevo nodo pasará a ser el último de esta lista y el anterior tendrá el siguiente enlace .

A menudo surge la pregunta durante las entrevistas: ¿qué es un conflicto ? La situación en la que una celda de la matriz tabla[] almacena no un elemento, sino una cadena de dos o más, se llama colisión . En casos normales donde solo se almacena un elemento en una sola celda de tabla [] , acceder a los elementos de un HashMap tiene una complejidad de tiempo constante O (1) . Pero cuando una celda con el elemento deseado contiene una cadena de elementos ( colisión ), entonces O(n) , ya que en este caso el tiempo es directamente proporcional al número de elementos que se ordenan.

10. Explica el iterador.

En el diagrama de mapeo de la jerarquía de la Colección anterior, la interfaz de la Colección era donde comenzaba toda la jerarquía, pero en la práctica no es así. La colección hereda de una interfaz con un método iterator() , que devuelve un objeto que implementa la interfaz Iterator<E> . La interfaz del Iterador se ve así:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() : al llamar a este método, puede obtener el siguiente elemento. hasNext() : te permite saber si hay un elemento siguiente y si se ha llegado al final de la colección. Y cuando todavía haya elementos, hasNext() devolverá verdadero . Normalmente, hasNext() se llama antes del método next() , ya que next() arrojará una NoSuchElementException cuando llegue al final de la colección . remove() : elimina el elemento que se recuperó mediante la última llamada a next() . El propósito de Iterator es iterar sobre elementos. Por ejemplo:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

En realidad, el bucle for-each se implementa bajo el capó mediante un iterador. Puedes leer más sobre esto aquí . List proporciona su propia versión de un iterador, pero una más fresca y sofisticada: ListIterator . Esta interfaz amplía Iterator y tiene métodos adicionales:

• hasPrevious devolverá verdadero si hay un elemento anterior en la colección; falso en caso contrario;
• anterior devuelve el elemento actual y pasa al anterior; si no hay ninguno, se lanza una NoSuchElementException;
• add insertará el objeto pasado antes del elemento que será devuelto por la siguiente llamada a next() ;
• set asigna al elemento actual una referencia al objeto pasado;
• nextIndex devuelve el índice del siguiente elemento. Si no existe tal cosa, se devuelve el tamaño de la lista;
• anteriorIndex devuelve el índice del elemento anterior. Si no hay ninguno, se devuelve el número -1.

Bueno, eso es todo para mí hoy. Espero que después de leer este artículo esté aún más cerca de su preciado sueño: convertirse en desarrollador.