c++ - unordered_set - unordered_map example

¿Cómo C++ STL unordered_map resuelve las colisiones?

Question

¿Cómo C ++ STL unordered_map resuelve las colisiones?

Mirando el http://www.cplusplus.com/reference/unordered_map/unordered_map/ , dice "Claves únicas No hay dos elementos en el contenedor que puedan tener claves equivalentes".

Eso debería significar que el contenedor está resolviendo colisiones. Sin embargo, esa página no me dice cómo lo está haciendo. Conozco algunas formas de resolver colisiones como el uso de listas vinculadas y / o sondeos. Lo que quiero saber es cómo el c ++ STL unordered_map lo está resolviendo.

Answer 1

El estándar define un poco más sobre esto de lo que la mayoría de las personas parece darse cuenta.

Específicamente, la norma requiere (§23.2.5 / 9):

Los elementos de un contenedor asociativo desordenado se organizan en cubos. Las claves con el mismo código hash aparecen en el mismo cubo.

La interfaz incluye un bucket_count que se ejecuta en tiempo constante. (tabla 103). También incluye un tamaño de cubo que debe ejecutarse en tiempo lineal en el tamaño del cubo.

Eso es básicamente describir una implementación que utiliza el encadenamiento de colisión. Cuando utiliza el encadenamiento de colisión, cumplir todos los requisitos es fácil y trivial. bucket_count() es el número de elementos en su matriz. bucket_size() es el número de elementos en la cadena de colisión. Conseguirlos en tiempo constante y lineal respectivamente es simple y directo.

Por el contrario, si utiliza algo como sondeo lineal o doble hashing, esos requisitos se vuelven casi imposibles de cumplir. Específicamente, todos los elementos con un valor de hash específico deben aterrizar en el mismo grupo, y usted debe contar esos grupos en un tiempo constante.

Pero, si usa algo como sondeo lineal o doble hash, encontrar todos los elementos con el mismo valor significa que necesita calcular el valor, luego recorrer la "cadena" de elementos no vacíos en su tabla para encontrar cuántos De esos hash al mismo valor. Sin embargo, eso no es lineal en el número de elementos que tienen el mismo valor hash, sino que es lineal en el número de elementos que tienen el mismo valor o un valor de colisión.

Con suficiente trabajo extra y una buena cantidad de estiramiento del significado de algunos de los requisitos casi hasta el punto de ruptura, podría ser casi imposible crear una tabla hash utilizando algo que no sea el encadenamiento de colisión, y al menos todavía cumplir los requisitos. -pero no estoy realmente seguro de que sea posible, y seguramente involucraría bastante trabajo adicional.

Resumen: todas las implementaciones prácticas de std::unordered_set (o unordered_map ), sin duda, utilizan el encadenamiento de colisiones. Si bien podría ser (apenas) posible cumplir los requisitos utilizando un sondeo lineal o un doble hashing, esta implementación parece perder mucho y no obtiene casi nada a cambio.