example - c++ unordered_map manejo de colisiones, cambio de tamaño y repetición
unordered_map example (2)
Con cada solicitud de envío, restriegue el objeto y asígnelo a un espacio en esta memoria
Desafortunadamente, esto no es exactamente cierto. Se refiere a un direccionamiento abierto o una estructura de datos hash cerrada que no es cómo se especifica unordered_map .
Cada implementación de unordered_map almacena una lista vinculada a nodos externos en la matriz de cubos. Lo que significa que la inserción de un elemento siempre asignará al menos una vez (el nuevo nodo) si no es dos veces (redimensionando la matriz de cubos, luego el nuevo nodo).
No, esa no es la forma más eficiente de implementar un mapa hash para los usos más comunes. Desafortunadamente, un pequeño "descuido" en la especificación de unordered_map requiere este comportamiento. El comportamiento requerido es que los iteradores a los elementos deben permanecer válidos al insertar o eliminar otros elementos. Debido a que la inserción puede hacer que la matriz de cubetas crezca (reasigne), generalmente no es posible tener un iterador que apunte directamente a la matriz de cubetas y cumpla con las garantías de estabilidad.
unordered_map es una estructura de datos mejor si está almacenando elementos costosos de copiar como su clave o valor. Lo cual tiene sentido, dado que su diseño general se eliminó del diseño semántico previo al movimiento de Boost.
Chandler Carruth (Google) menciona este problema en su CppCon ''14 talk "Eficiencia con algoritmos, rendimiento con estructuras de datos" .
No he leído el estándar de C ++, pero así es como creo que funciona el mapa desordenado de c ++.
- Asigna un bloque de memoria en el montón.
- Con cada solicitud de envío, restriegue el objeto y asígnelo a un espacio en esta memoria
- Durante este proceso, maneje el manejo de colisiones a través del encadenamiento o el direccionamiento abierto.
Estoy bastante sorprendido de que no pude encontrar mucho acerca de cómo la memoria es manejada por unordered_map. ¿Hay un tamaño inicial específico de memoria que asigna unordered_map? ¿Qué sucede si digamos que asignamos 50 int de memoria y terminamos insertando 5000 enteros?
Esta será una gran cantidad de colisiones, por lo que creo que debería haber algo así como un algoritmo de rehechizado y redimensionamiento para disminuir el número de colisiones después de alcanzar un cierto nivel de umbral de colisión. Dado que se proporcionan explícitamente como funciones de miembro a la clase, supongo que también se usan internamente. ¿Hay tal mecanismo?
std :: unordered_map contiene un factor de carga que utiliza para administrar el tamaño de sus depósitos internos. std :: unordered_map usa este factor impar para mantener el tamaño del contenedor en algún lugar entre un factor de 0.0 y 1.0. Esto disminuye la probabilidad de una colisión en un cubo. Después de eso, no estoy seguro de si recurrirán a un sondeo lineal dentro de un cubo en el que se encontró una colisión, pero supongo que sí.