🧑🏾 😺 ⚔️ Lo que necesita saber sobre las colecciones basadas en hash 👩🏿‍🤝‍👩🏻 🎵 🍱

Hola a todos. En contacto Vladislav Rodin. Actualmente, soy el jefe del curso High Load Architect en OTUS, y también doy cursos sobre arquitectura de software.

Además de la enseñanza, como puede ver, he estado escribiendo para un blog de material de copyright OTUS Habré y el artículo de hoy quiero dedicar el lanzamiento de los "Algoritmos para desarrolladores" de New Deal Flow .

Introducción

Las tablas hash (HashMap) junto con las matrices dinámicas son las estructuras de datos más populares utilizadas en la producción. Muy a menudo puede escuchar preguntas en las entrevistas sobre su propósito, características de su estructura interna, así como algoritmos relacionados. Esta estructura de datos es clásica y se encuentra no solo en Java, sino también en muchos otros lenguajes de programación.

Formulación del problema

Establezcamos un objetivo para crear una estructura de datos que le permita:

contiene (Elemento del elemento) verifica si hay un elemento en él o no, para O (1)
add (elemento Element) agrega un elemento en O (1)
delete (Elemento del elemento) eliminar un elemento en O (1)

Formación

Intentemos hacer estas operaciones sobre una matriz, que es la estructura de datos más simple. Estamos de acuerdo en que consideraremos que la celda está vacía si contiene nulo.

Verificación de disponibilidad

Es necesario hacer una búsqueda lineal a través de la matriz, porque el elemento puede estar potencialmente en cualquier celda. Asintóticamente, esto se puede hacer en O (n), donde n es el tamaño de la matriz.

Agregando

Si necesitamos agregar un elemento en cualquier lugar, primero tenemos que encontrar una celda vacía y luego escribirle el elemento. Así, nuevamente realizamos una búsqueda lineal y obtenemos el comportamiento asintótico de O (n).

Eliminar

Para eliminar un elemento, primero debe encontrarlo y luego escribir nulo en la celda encontrada. Nuevamente, la búsqueda lineal nos lleva a O (n).

El conjunto de hash más simple

Tenga en cuenta que con cada operación, primero buscamos el índice de la celda deseada, y luego realizamos la operación, ¡y es la búsqueda la que nos estropea las asíntotas! Si aprendiéramos a obtener este índice para O (1), entonces el problema original estaría resuelto.

Ahora reemplacemos la búsqueda lineal con el siguiente algoritmo: calcularemos el valor de una determinada función, una función hash que asigna un objeto de clase a un entero. Después de eso, compararemos el entero resultante con el índice de la celda de la matriz (esto es bastante fácil de hacer, por ejemplo, tomando el resto de dividir este número por el tamaño de la matriz). Si la función hash está escrita de tal manera que se considera que es O (1) (y generalmente se escribe así), entonces hemos obtenido la implementación más simple del conjunto hash. Una celda de matriz en términos de un conjunto hash puede llamarse un depósito .

Los problemas de la implementación más simple de un conjunto hash

No importa cómo se escriba la función hash, el número de celdas en la matriz siempre es limitado, mientras que el conjunto de elementos que queremos almacenar en la estructura de datos es ilimitado. Después de todo, no nos molestaríamos con la estructura de datos si fuera necesario guardar solo diez elementos previamente conocidos, ¿verdad? Este estado de cosas conduce a conflictos inevitables . Una colisión es una situación en la que, al agregar diferentes objetos, caemos en la misma celda de la matriz.

Se inventaron dos métodos para resolver colisiones: el método de encadenamiento y el método de direccionamiento abierto .

Método de encadenamiento

El método de encadenamiento es el método más simple para resolver colisiones. En la celda de la matriz no almacenaremos los elementos, sino una lista vinculada de estos elementos. Debido a que agregar a la parte superior de la lista (y no importa a qué parte de la lista agregar un elemento) tiene el comportamiento asintótico de O (1), no estropearemos el comportamiento asintótico general, y seguirá siendo igual a O (1).

Esta implementación tiene un problema: si las listas crecen mucho (como último recurso, podemos considerar una función hash que devuelve una constante para cualquier objeto), entonces obtenemos las asintóticas O (m), donde m es el número de elementos en el conjunto, si el tamaño La matriz es fija. Para evitar tales problemas, se introduce el concepto de ciclo de trabajo .(puede ser igual, por ejemplo, 1.5). Si al agregar un elemento resulta que la fracción del número de elementos que están en la estructura de datos en relación con el tamaño de la matriz excede el factor de relleno, entonces sucede lo siguiente: se selecciona una nueva matriz cuyo tamaño excede el tamaño de la matriz anterior (por ejemplo, 2 veces), y la estructura de datos se reconstruye en la nueva matriz.

Este método de resolución de colisiones se usa en Java, y la estructura de datos se llama HashSet .

Método de direccionamiento abierto

En este método, las celdas se almacenan en las celdas y, en caso de colisión, se produce una secuencia de muestras , es decir, comenzamos a clasificar las celdas utilizando algún algoritmo con la esperanza de encontrar una libre. Esto puede hacerse mediante diferentes algoritmos ( secuencia lineal / cuadrática de muestras , doble hashing ), cada uno de los cuales tiene sus propios problemas (por ejemplo, la aparición de grupos primarios o secundarios ).

De un conjunto de hash a una tabla de hash (HashMap)

Creemos una estructura de datos que le permita agregar, eliminar, buscar elementos, pero mediante alguna tecla, tan rápido como un conjunto de hash (es decir, más allá de O (1)).

Utilizaremos la misma estructura de datos que el conjunto de hash, pero no almacenaremos elementos, sino pares de elementos.

Por lo tanto, la inserción (put (Key key, Value value)) se implementará de la siguiente manera: calcularemos la celda de la matriz por un objeto de tipo Key, obtendremos el número de bucket. Repasemos la lista en el cubo, comparando la clave con la clave en pares almacenados. Si encuentra la misma clave, simplemente exprima el valor anterior, si no la encontró, agregue un par.

¿Cómo se recibe un artículo por clave? Sí, de acuerdo con un principio similar: obtenemos un depósito por clave, revisamos los pares y devolvemos el valor en un par, cuya clave es igual a la clave en la solicitud, si existe tal par, y nulo de lo contrario.

Esta estructura de datos se llama tabla hash .

Preguntas típicas de entrevista

P: ¿Cómo se organizan HashSet y HashMap? ¿Cómo se llevan a cabo las principales operaciones en estas colecciones? ¿Cómo se aplican los métodos equals () y hashCode ()?
R : Las respuestas a estas preguntas se pueden encontrar arriba.

P: ¿Cuál es el contrato para equals () y hashCode ()? ¿A qué se debe?
R : Si los objetos son iguales, entonces deben tener un código hash igual. Por lo tanto, hashCode debe determinarse por la capacidad de los campos involucrados en iguales. La violación de este contrato puede conducir a efectos muy interesantes. Si los objetos son iguales, pero su código hash es diferente, entonces es posible que no obtenga el valor correspondiente a la clave por la que acaba de agregar el objeto al HashSet o al HashMap.

Conclusión

En las entrevistas, les gusta preguntar diferentes casos relacionados con estas estructuras de datos. Además, la decisión de cualquiera de ellos se puede deducir de la comprensión de los principios de su trabajo sin ningún tipo de "hacinamiento".

Eso es todo. Si ha leído el material hasta el final, invito a mi colega Evgeny Volosatov a mostrarle cómo resolver el problema de la olimpiada utilizando las ideas de programación dinámica para una lección gratuita sobre el tema "Secretos de la programación dinámica" .

Lo que necesita saber sobre las colecciones basadas en hash