unordered_set - unordered_map c++ example

Cómo se implementa std:: unordered_map

Question

Manejo de colisiones de un mapa desordenado de C ++, cambio de tamaño y repetición

Esta es una pregunta anterior abierta por mí y he visto que tengo mucha confusión sobre cómo se implementa unordered_map. Estoy seguro de que muchas otras personas comparten esa confusión conmigo. Según 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 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 todo pero 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 pudiera explicar la implementación y cómo encaja 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 mapa hash, ¿cómo se puede mejorar?

Answer 1

El estándar exige de manera efectiva implementaciones std::unordered_set y std::unordered_map que usan hashing abierto, lo que significa una matriz de cubos, cada uno de los cuales tiene 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áxima predeterminado sea 1.0 y la garantía de que la tabla no se volverá a colocar en la tabla a menos que crezca más allá de ese factor de carga: eso sería poco práctico sin encadenar, ya que las colisiones con el hash cerrado se vuelven abrumadoras a medida que factor de carga se aproxima a 1:

23.2.5 / 15: Los miembros 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 elementos insertados, B es el recuento de cubetas del contenedor y z es el factor de carga máxima 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 antes de los elementos de ese cubo, por lo que el siguiente puntero puede ser reconectado si se borra el último valor del cubo).

Con respecto 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 todo pero 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 podrían haberse alcanzado otros compromisos, pero el enfoque de hashing / encadenamiento abierto es un compromiso razonable para el uso general, que hace frente de manera razonablemente elegante a las colisiones de funciones 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 como lo hacen muchas implementaciones de hash cerradas.

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

No conozco ninguna implementación satisfactoria de 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 tipos con un constructor predeterminado y construir cada elemento de la matriz con anticipación, o bien mantener una matriz de algunos de cuyos elementos son objetos y otros de los cuales son memoria sin procesar.

• 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 gestión de colisiones es especialmente complicada cuando se permite borrar elementos. (Vea Knuth para una discusión.) Una clase de contenedor para la biblioteca estándar debería permitir el borrado.

• Los esquemas de gestión de colisiones para direccionamiento abierto tienden a asumir 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 insertan 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 en implementación en el contexto de C ++, sería inapropiado estandarizar una clase de contenedor de direccionamiento abierto.

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

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