Cómo se usa std :: unordered_map

c ++ unordered_map manejo de colisiones, cambio de tamaño y repetición

Esta es una pregunta anterior abierta por mí y he visto que estoy teniendo mucha confusión sobre cómo se implementa unordered_map. Estoy seguro de que muchas otras personas comparten esa confusión conmigo. Basado en la información que conozco sin leer el estándar:

Cada implementación de unordered_map almacena una lista vinculada a nodos externos en la matriz de cubos … No, esa no es en absoluto 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

Esperaba que alguien explicara la implementación y cómo se corresponde con la definición estándar de c ++ (en términos de requisitos de rendimiento) y si realmente no es la forma más eficiente de implementar una estructura de datos de mapas hash, ¿cómo se puede mejorar?

El estándar efectivamente exige implementaciones std::unordered_set y std::unordered_map que usan hash abierto, lo que significa una matriz de cubos, cada uno de los cuales contiene el encabezado de una lista lógica (y típicamente real). Ese requisito es sutil: es una consecuencia de que el factor de carga máximo predeterminado sea 1.0 y la garantía de que la tabla no se volverá a generar a menos que crezca más allá de ese factor de carga: eso sería poco práctico sin encadenamiento, ya que las colisiones con hash cerrado se vuelven abrumadoras. factor de carga se aproxima a 1:

23.2.5 / 15: Los elementos de insert y emplace no afectarán la validez de los iteradores si (N+n) < z * B , donde N es el número de elementos en el contenedor antes de la operación de inserción, n es el número de los elementos insertados, B es el recuento de cubos del contenedor z es el factor de carga máximo del contenedor.

entre los Efectos del constructor en 23.5.4.2/1: max_load_factor() devuelve 1.0 .

(Para permitir una iteración óptima sin pasar por los cubos vacíos, la implementación de GCC llena los cubos con iteradores en una sola lista enlazada individualmente que contiene todos los valores: los iteradores apuntan al elemento inmediatamente anterior a los elementos de ese cubo, por lo que el siguiente puntero puede ser volver a cablear si se borra el último valor del cubo.)

En cuanto al texto que cita:

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

No hay "supervisión" ... lo que se hizo fue muy deliberado y se hizo con plena conciencia. Es cierto que otros compromisos podrían haberse solucionado, pero el enfoque de hashing / encadenamiento abierto es un compromiso razonable para el uso general, que se comporta de forma razonablemente elegante con colisiones de funciones de hash mediocres, no es demasiado derrochador con tipos de clave / valor pequeños o grandes. y maneja arbitrariamente muchos pares de insert / erase sin degradar gradualmente el rendimiento de la misma manera que lo hacen muchas implementaciones de hash cerrado.

Como evidencia de la conciencia, de la propuesta de Matthew Austern aquí :

No estoy al tanto de ninguna implementación satisfactoria del direccionamiento abierto en un marco genérico. El direccionamiento abierto presenta una serie de problemas:

• Es necesario distinguir entre un puesto vacante y uno ocupado.

• Es necesario restringir la tabla hash a los tipos con un constructor predeterminado, y construir cada elemento de matriz con anticipación, o bien mantener una matriz cuyos elementos son objetos y otros son memoria en bruto.

• El direccionamiento abierto dificulta la gestión de colisiones: si está insertando un elemento cuyo código hash se asigna a una ubicación ya ocupada, necesita una política que le indique dónde intentarlo a continuación. Este es un problema resuelto, pero las soluciones más conocidas son complicadas.

• La administración de colisiones es especialmente complicada cuando se permite el borrado de elementos. (Consulte a Knuth para una discusión.) Una clase de contenedor para la biblioteca estándar debe permitir el borrado.

• Los esquemas de administración de colisiones para el direccionamiento abierto tienden a suponer una matriz de tamaño fijo que puede contener hasta N elementos. Una clase de contenedor para la biblioteca estándar debería poder crecer según sea necesario cuando se inserten nuevos elementos, hasta el límite de la memoria disponible.

Resolver estos problemas podría ser un proyecto de investigación interesante, pero, en ausencia de experiencia de implementación en el contexto de C ++, sería inapropiado estandarizar una clase de contenedor de direccionamiento abierto.

Específicamente para tablas solo de inserción con datos lo suficientemente pequeños como para almacenarlos directamente en los depósitos, un valor de centinela conveniente para cubos no utilizados y una buena función hash, un enfoque de hash cerrado puede ser aproximadamente un orden de magnitud más rápido y usar mucho menos memoria, pero eso no es un propósito general.

Una comparación y elaboración completas de las opciones de diseño de la tabla hash y sus implicaciones está fuera de tema para SO, ya que es demasiado amplia para abordarla correctamente aquí.