¿El mapa sin ordenar es realmente desordenado?

Question

Estoy muy confundido por el nombre 'unordered_map'. El nombre sugiere que las claves no están ordenadas en absoluto. Pero siempre pensé que estaban ordenados por su valor hash. ¿O es incorrecto (porque el nombre implica que no están ordenados)?

O, para decirlo diferente: ¿Es esta

typedef map<K, V, HashComp<K> > HashMap; 

con

template<typename T> 
struct HashComp { 
    bool operator<(const T& v1, const T& v2) const { 
     return hash<T>()(v1) < hash<T>()(v2); 
    } 
}; 

lo mismo que

typedef unordered_map<K, V> HashMap; 

? (Bueno, no exactamente, STL se quejará aquí porque puede haber claves k1, k2 y tampoco k2 k1 < ni < k1 k2 Usted tendría que utilizar multimap y sobrescribir la igualdad de verificación..)

O también de otra manera: Cuando los repito, ¿puedo suponer que la lista de claves está ordenada por su valor hash?

Answer 1

En respuesta a su pregunta editada, no esos dos fragmentos no son equivalentes en absoluto. std::map almacena nodos en una estructura de árbol, unordered_map los almacena en una tabla hash *.

Las claves no se almacenan en orden de su "valor hash" porque no están almacenadas en ninguna orden en absoluto. En cambio, se almacenan en "cubos" donde cada cubeta corresponde a un rango de valores hash. Básicamente, la implementación es el siguiente:

function add_value(object key, object value) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     buckets[bucket_index] = new linked_list(); 
    } 
    buckets[bucket_index].add(new key_value(key, value)); 
} 

function get_value(object key) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     return null; 
    } 

    foreach(key_value kv in buckets[bucket_index]) { 
     if (kv.key == key) { 
      return kv.value; 
     } 
    } 
} 

Obviamente que es una simplificación grave e implementación real sería mucho más avanzados (por ejemplo, el apoyo a cambiar el tamaño de la matriz buckets, tal vez usando una estructura de árbol en lugar de lista enlazada para los cucharones , y así sucesivamente), pero eso debería dar una idea de cómo no puede recuperar los valores en un orden en particular. Ver wikipedia para más información.

* Técnicamente, la implementación interna de std::map y unordered_map son definido por la implementación, pero el estándar requiere cierta complejidad Big-O para las operaciones que implica esas implementaciones internas

Answer 2

Si quieres una analogía, mira el RDBMS que elijas.

Si no especifica una cláusula ORDER BY al realizar una consulta, los resultados se devuelven "desordenados", es decir, en el orden en que se encuentre la base de datos. La orden no está especificada, y el sistema es libre de "ordenarlos" como quiera para obtener el mejor rendimiento.

Answer 3

Tienes razón, unordered_map es en realidad hash ordenado. Tenga en cuenta que la mayoría de las implementaciones actuales (pre TR1) lo llaman hash_map.

El IBM C/C++ documentation comentarios que si tiene una función de dispersión óptima, el número de operaciones realizadas durante las operaciones de búsqueda, inserción y eliminación de un elemento arbitrario no depende del número de elementos en la secuencia , entonces esto significa que la orden no está tan desordenada ...

Ahora, ¿qué significa que es hash pedido? Como un hash debe ser impredecible, por definición no puede asumir ningún supuesto sobre el orden de los elementos en el mapa. Esta es la razón por la que ha sido renombrado en TR1: el antiguo nombre sugería una orden. Ahora sabemos que realmente se usa un pedido, pero puede ignorarlo ya que es impredecible.

Answer 4

"Desordenado" no significa que no haya una secuencia lineal en algún lugar de la implementación. Significa que "no se puede asumir nada sobre el orden de estos elementos".

Por ejemplo, las personas suelen suponer que las entradas saldrán de un mapa hash en el mismo orden en que se colocaron. Pero no es así, porque las entradas no están ordenadas.

En cuanto a "ordenado por su valor hash": los valores hash generalmente se toman de la gama completa de enteros, pero los mapas hash no tienen 2 ** 32 ranuras en ellos. El rango del valor de hash se reducirá al número de slots tomando el módulo de la cantidad de slots. Además, al agregar entradas a un mapa hash, es posible que cambie el tamaño para acomodar los nuevos valores. Esto puede causar que todas las entradas anteriores sean reubicadas, cambiando su orden.

En una estructura de datos desordenada, no se puede asumir nada sobre el orden de las entradas.

Answer 5

Como sugiere el nombre unordered_map, el orden en C++ 0x no especifica ningún orden. El orden aparente de unordered_map dependerá de lo que sea conveniente para la implementación real.