Tabla Hash vs Mapa STL

Este artículo se centra en: comparar y contrastar la tabla Hash y un mapa STL. ¿Cómo se implementa la tabla hash? Si la cantidad de entradas es pequeña, ¿qué opciones de estructura de datos se pueden usar en lugar de una tabla hash?

Tabla de picadillo

En una tabla hash, un valor se almacena llamando a una función hash en una clave.

• Los valores no se almacenan en orden ordenado.
• Además, dado que las tablas hash usan la clave para encontrar el índice que almacenará el valor, se puede realizar una inserción o búsqueda en el tiempo O(1) amortizado (suponiendo pocas colisiones en la tabla hash).
• En una tabla hash, también se deben manejar posibles colisiones. Esto se suele hacer enstringndo , lo que significa crear una lista enlazada de todos los valores cuyas claves se asignan a un índice particular.

Implementación de la tabla hash: una tabla hash se implementa tradicionalmente con una array de listas vinculadas. Cuando queremos insertar un par clave/valor, asignamos la clave a un índice en la array usando la función hash. A continuación, el valor se inserta en la lista vinculada en esa posición. Nota: Los elementos de la lista enlazada en un índice particular de la array no tienen la misma clave. Más bien, la función hash (clave) es la misma para estos valores. Por lo tanto, para recuperar el valor de una clave específica, debemos almacenar en cada Node tanto la clave exacta como el valor. Para resumir, se implementará una tabla hash con una array de listas vinculadas, donde cada Node de la lista vinculada contiene dos datos: el valor y la clave original. Además, querremos señalar los siguientes criterios de diseño:

1. Queremos usar una buena función hash para asegurarnos de que las claves estén bien distribuidas. Si no están bien distribuidos, tendríamos muchas colisiones y la velocidad para encontrar un elemento disminuiría.
2. No importa cuán buena sea la función hash, aún tendremos colisiones, por lo que necesitamos un método para manejarlas. esto a menudo significa enstringr a través de una lista enlazada, pero no es la única forma.
3. También es posible que deseemos implementar métodos para aumentar o disminuir dinámicamente el tamaño de la tabla hash según la capacidad. Por ejemplo, cuando la relación entre el número de elementos y el tamaño de la tabla supera cierto umbral, es posible que deseemos aumentar el tamaño de la tabla hash. Esto significaría crear una nueva tabla hash y transferir las entradas de la tabla anterior a la nueva. Debido a que esta es una operación costosa, queremos tener cuidado de no realizarla con demasiada frecuencia.

Mapa STL

El mapa de contenedores es un contenedor asociativo incluido en la biblioteca estándar de C++ . La definición de esta clase se encuentra en el archivo de encabezado «mapa» del espacio de nombres estándar. Implementación interna del mapa STL: se implementa como un árbol rojo-negro autoequilibrado. Probablemente los dos árboles de equilibrio automático más comunes son el árbol rojo-negro y los árboles AVL. Para equilibrar el árbol después de una inserción/actualización, ambos algoritmos utilizan la noción de rotaciones donde los Nodes del árbol se giran para realizar el reequilibrio. Mientras que en ambos algoritmos las operaciones de inserción/eliminación son O(log n), en el caso de Red-Black tree rebalanceing la rotación es una operación O(1) mientras que con AVL esta es una operación O(log n), lo que hace que Árbol RB más eficiente en este aspecto de la salvia reequilibrante y una de las posibles razones por las que se utiliza con mayor frecuencia.

Diferencias entre tabla hash y mapa STL

1. Claves nulas: STL Map permite una clave nula y múltiples valores nulos, mientras que la tabla hash no permite ninguna clave o valor nulo.
2. Sincronización de subprocesos: generalmente se prefiere el mapa a la tabla hash si no se necesita la sincronización de subprocesos. La tabla hash está sincronizada.
3. Seguro para subprocesos: STL Maps no es seguro para subprocesos, mientras que Hashmaps es seguro para subprocesos y se puede compartir con muchos subprocesos.
4. Orden de valor: en el mapa STL, los valores se almacenan en orden ordenado, mientras que en la tabla hash los valores no se almacenan en orden ordenado
5. Tiempo de búsqueda: puede usar el mapa STL o el árbol binario para datos más pequeños (aunque lleva tiempo O (log n), la cantidad de entradas puede ser lo suficientemente pequeña como para que este tiempo sea insignificante) y para una gran cantidad de datos, se prefiere la tabla hash .

Artículos relacionados 

• Ventajas de BST sobre hashmap
• Diferencias entre HashMap y HashTable en Java

Veamos las diferencias en forma tabular -:

	Tabla de picadillo	Mapa STL
1.	esta sincronizado	Es un contenedor asociado que se utiliza para almacenar elementos en pares clave, valor
2.	Es seguro para subprocesos.	STL tiene dos tipos de mapas que son: mapa ordenado y mapa desordenado.
3.	No permite ningún Valor Nulo	Su sintaxis es -: map<tipo_datos, tipo_datos> y mapa_desordenado<tipo_datos, tipo_datos>
4.	Es lento.	Es rápido.
5.	Es una clase heredada.	El tiempo de búsqueda en mapas es O(log n)

Este artículo es una contribución de Brahmani Sai . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.