Complejidad de tiempo hashmap y c ++

"La complejidad del tiempo es el tiempo de ejecución relativo de alguna codificación. Antes de discutir la complejidad del tiempo de un hashmap, el lector debe conocer el papel de una función hash en un mapa hash.

En teoría, una función hash convertiría datos de cualquier tamaño (cualquier texto grande) a un número entero que sea mayor o igual a cero. Diferentes textos grandes se convierten a diferentes números. El interés en este artículo no es convertir texto grande a un entero. El interés en este artículo es asignar datos de cualquier tamaño a un número entero. Esto incluye la posibilidad de mapeo (convertir) un número único en otro número único.

Los datos (a la izquierda) a mapear se llaman claves. Entonces, cada clave se convierte en un número completo que es igual o mayor que cero. Imagine que hay cinco claves que se han convertido en números: 0, 1, 2, 3 y 4. Si estas claves son los índices de una matriz que contiene cinco valores del mismo tipo, entonces estas claves se han asignado a cinco valores diferentes.

Y entonces, ¿qué es un hashmap (mapa hash)?? Un hashmap es una estructura de datos que consiste en pares de clave/valor, donde cada clave se ha asignado a un valor. En realidad, cada clave se ha asado en una serie de una matriz, y la celda de matriz correspondiente es contener un valor. En el tema de hashmap, la ubicación para la celda de cada índice de matriz se llama cubo."

Problema de colisión y resolución

En la práctica, se pueden asignar diferentes claves a más de un valor. Considere el caso de diez claves para una matriz de longitud 5, con 5 cubos. En este caso, se construiría una estructura como una matriz de matrices. Cada cubo sería realmente una variedad de longitud 2. Dos claves compartirían el mismo cubo. En este intercambio, la primera clave se asignaría al primer elemento de matriz para el cubo, y la segunda clave se asignaría al segundo elemento de matriz para el mismo cubo. Este esquema resuelve el problema de colisión, y diez claves se han asignado a 10 valores, como se esperaba.

Para el resto de este artículo, imagine un hashmap con el problema de colisión resuelto. El objetivo de este artículo es proporcionar la complejidad del tiempo de la codificación para la inserción en un hashmap, codificar la eliminación en un hashmap y codificar para buscar en un hashmap. La complejidad del tiempo para hashmap se describe con estas tres características. El mapeo hash para C ++ también se aborda en este artículo.

Pares de clave/valor y valor_type

Imagine un hashmap de nombres de personas contra números de teléfono para un directorio telefónico. Los nombres de los usuarios telefónicos son de tipo de datos, texto (cadena). Los valores de los números de teléfono son de tipo de datos y texto, suponiendo que los espacios y/o los guiones estén permitidos en un número de teléfono. Los nombres de usuario son las claves, y los números de teléfono son los valores. No olvide que, internamente, las claves se convierten en índices de matriz en la estructura de datos. Entonces, el tipo de clave es el texto, y el tipo de valor sigue siendo texto.

Tipo de valor significa el par de clave/valor como elemento. En C ++, cada elemento (par) es apuntado por un iterador. Entonces, en C ++, también hay mapeo iterador/par. Un par (clave y su valor) se conoce como un tipo de valor.

Complejidad del tiempo para la inserción de hashmap

La complejidad del tiempo para un hashmap no se refiere al tiempo necesario para crear el hashmap. Se refiere al tiempo necesario para insertar, eliminar o buscar un valor basado en una clave dada. La complejidad del tiempo normalmente se escribe utilizando la notación Big-O. La notación Big-O consiste en O en mayúscula, seguida de paréntesis. Entre paréntesis hay variables y números, que dan el tiempo de ejecución relativo para un código y no necesariamente todo el programa. Con el hashmap, k significa el número de llaves, y n significa el número de cubos. Recuerde que con algunos hashmaps, un cubo puede tener más de un valor para las claves correspondientemente diferentes. En este caso, más de una clave se ha asado en el mismo índice de cubo. Un buen hashmap resuelve esta colisión.

Inserción

Dada una nueva clave, la complejidad del tiempo promedio para tener la clave y su valor correspondiente insertado en una estructura de datos hashmap es:

O (1 + n/k)

Donde n es el número de cubos y k es el número de claves. Por ejemplo, N tal vez 10 y K tal vez 5. En esta situación particular, algunos cubos están vacíos (no tienen valor). Entonces, el número de operaciones sería, 1 + 10/5 = 1 + 2 = 3. Es decir, habría 3 operaciones de codificación para insertar un elemento de par de clave/valor (dada la clave). Dada una nueva clave y valor, la complejidad del tiempo en el peor de los casos para tener la clave y su valor correspondiente insertado en una estructura de datos hashmap es:

En)

Donde n es el número de cubos para operaciones n, si el hashmap toma más de un valor por cubo para más de una clave, entonces cualquier tiempo adicional para insertar un valor adicional en el mismo cubo es insignificante y descuidado.

Supresión

Dada una clave que ya está en la estructura de datos hashmap, la eliminación elimina el elemento de par de clave/valor. La complejidad del tiempo promedio para la eliminación es:

O (1 + n/k)

Donde n es el número de cubos y k es el número de claves. Por ejemplo, N tal vez 10 y K tal vez 5. En esta situación particular, algunos cubos están vacíos (no tienen valor). Entonces, el número de operaciones para el código de deleción sería, 1 + 10/5 = 1 + 2 = 3. Entonces, aquí, habría 3 operaciones de codificación para eliminar un elemento de par de clave/valor, dada la clave.

La peor complejidad del tiempo para la eliminación, dada una clave, es:

En)

Donde n es el número de cubos, por lo tanto, si hay n cubos para la estructura de datos hashmap, en el límite, se necesitarían 10 operaciones para eliminar un elemento de par de clave/valor en el hashmap.

buscando

Buscar significa encontrar el elemento de par de clave/valor que tiene la tecla dada, que ya debería estar en el hashmap. La complejidad del tiempo promedio para esto es:

O (1 + n/k)

Con los argumentos que tienen los mismos significados que anteriormente. La peor complejidad del tiempo para esto es:

En)

Con el argumento que tiene el mismo significado que el anterior.

C ++ 20

¿C ++ 20 tiene una clase de hashmap?? - Bueno, sí, pero no con el nombre, hashmap. C ++ 20 tiene cuatro contenedores asociativos desordenados, que son diferentes formas de clases de hashmap. Los contenedores son: unordered_map, unordered_multimap, unordered_set y unordered_multiset. Estos contenedores asociativos están en la biblioteca estándar C ++ 20. El contenedor asociativo a considerar en este artículo es undered_map. El unordered_map utiliza una función hash predeterminada proporcionada por la biblioteca estándar C ++.

Para incluir el encabezado undered_map en un programa, use la directiva,

#incluir

No use #include, que incluirá el ordenado_map. C ++ no toma #Include . El encabezado undered_map trae la clase undered_map al programa C ++.

Insertar con c++

El siguiente segmento de código en la función principal de C ++ insertará un elemento de par de clave/valor (nombre y número de teléfono) en el objeto undered_map, UMP:

#incluir
desordenable_map Ump;
brecha.insertar ("John Rambo", "555-5555");

Eliminar con C++

La sintaxis para eliminar un elemento de par de clave/valor de un objeto undered_map, dada la clave, k, es:

a.borrar (k)

Donde "a" es el objeto unordered_map (como UMP arriba), y ERASE () es la función miembro undered_map.

buscando

La sintaxis para buscar un elemento de par de clave/valor en un objeto undered_map, dada la clave k, que ya debería estar en el ordened_map, es:

b.encontrar (k)

Donde b es el objeto undered_map (como UMP arriba), y find () es la función miembro undered_map.

Conclusión

La complejidad del tiempo significa tiempo de ejecución relativo para algún código. Aunque se puede determinar la complejidad del tiempo para crear un hashmap, al tratar con el hashmap, la complejidad del tiempo es para insertar, eliminar y buscar tareas. Las complejidades de tiempo de casos promedio y peores para un inserto hashmap bien definido son:

O (1 + n/k)
En)

Las complejidades de tiempo de casos promedio y peores para una eliminación de hashmap bien definida son:

O (1 + n/k)
En)

Las complejidades de tiempo de casos promedio y peores para una búsqueda de hashmap bien definida son:

O (1 + n/k)
En)