Descarga hopscotch map - Descarga del código fuente hopscotch map

Una implementación en C++ de un mapa hash rápido y un conjunto hash usando hash de rayuela

La biblioteca hopscotch-map es una implementación en C++ de un mapa hash rápido y un conjunto de hash que utiliza direccionamiento abierto y hash de rayuela para resolver colisiones. Es una estructura de datos compatible con caché que ofrece mejores rendimientos que std::unordered_map en la mayoría de los casos y es muy similar a google::dense_hash_map aunque utiliza menos memoria y proporciona más funcionalidades.

La biblioteca proporciona las siguientes clases principales: tsl::hopscotch_map , tsl::hopscotch_set , tsl::hopscotch_pg_map y tsl::hopscotch_pg_set . Los dos primeros son más rápidos y utilizan una política de crecimiento de poder de dos, los dos últimos utilizan una política de crecimiento principal y son capaces de hacer frente mejor a una función hash deficiente. Utilice la versión principal si existe la posibilidad de que se repitan patrones en los bits inferiores de su hash (por ejemplo, si está almacenando punteros con una función hash de identidad). Consulte GrowthPolicy para obtener más detalles.

Además de estas clases, la biblioteca también proporciona tsl::bhopscotch_map , tsl::bhopscotch_set , tsl::bhopscotch_pg_map y tsl::bhopscotch_pg_set . Estas clases tienen un requisito adicional para la clave, debe ser LessThanComparable , pero proporcionan un límite superior asintótico mejor; consulte los detalles en el ejemplo. No obstante, si no tiene requisitos específicos (riesgo de ataques DoS hash), tsl::hopscotch_map y tsl::hopscotch_set deberían ser suficientes en la mayoría de los casos y deberían ser su elección predeterminada, ya que funcionan mejor en general.

Puede encontrar una descripción general del hashing de rayuela y algunos detalles de implementación aquí.

Puede encontrar una referencia de tsl::hopscotch_map frente a otros mapas hash aquí. Esta página también brinda algunos consejos sobre qué estructura de tabla hash debería probar para su caso de uso (útil si está un poco perdido con las múltiples implementaciones de tablas hash en el espacio de nombres tsl ).

Características clave

Biblioteca de solo encabezado, simplemente agregue el directorio de inclusión a su ruta de inclusión y estará listo para comenzar. Si usa CMake, también puede usar el destino exportado tsl::hopscotch_map desde CMakeLists.txt.
Tabla hash rápida, consulte el punto de referencia para algunos números.
Soporte para clave/valor construible de solo movimiento y no predeterminado.
Soporte para búsquedas heterogéneas que permiten el uso de find con un tipo diferente a Key (por ejemplo, si tiene un mapa que usa std::unique_ptr<foo> como clave, puede usar foo* o std::uintptr_t como parámetro clave para find sin construir un std::unique_ptr<foo> , ver ejemplo).
No es necesario reservar ningún valor centinela de las claves.
Posibilidad de almacenar el valor hash al insertar para una repetición y búsqueda más rápidas si el hash o las funciones clave iguales son costosas de calcular (consulte el parámetro de plantilla StoreHash).
Si se conoce el hash antes de una búsqueda, es posible pasarlo como parámetro para acelerar la búsqueda (consulte el parámetro precalculated_hash en API).
tsl::bhopscotch_map y tsl::bhopscotch_set proporcionan el peor de los casos de O(log n) en búsquedas y eliminaciones, lo que hace que estas clases sean resistentes a los ataques de denegación de servicio (DoS) de la tabla hash (consulte los detalles en el ejemplo).
La biblioteca se puede usar con las excepciones deshabilitadas (a través de la opción -fno-exceptions en Clang y GCC, sin una opción /EH en MSVC o simplemente definiendo TSL_NO_EXCEPTIONS ). std::terminate se usa en reemplazo de la instrucción throw cuando las excepciones están deshabilitadas.
API muy similar a std::unordered_map y std::unordered_set .

Diferencias en comparación con `std::unordered_map`

tsl::hopscotch_map intenta tener una interfaz similar a std::unordered_map , pero existen algunas diferencias.

La invalidación del iterador al insertar no se comporta de la misma manera. En general, cualquier operación que modifique la tabla hash, excepto erase , invalida todos los iteradores (consulte la API para obtener más detalles).
Las referencias y punteros a claves o valores en el mapa se invalidan de la misma manera que los iteradores a estas claves-valor al insertar.
Para los iteradores, operator*() y operator->() devuelven una referencia y un puntero a const std::pair<Key, T> en lugar de std::pair<const Key, T> , lo que hace que el valor T no sea modificable. Para modificar el valor, debe llamar al método value() del iterador para obtener una referencia mutable. Ejemplo:

tsl::hopscotch_map< int , int > map = {{ 1 , 1 }, { 2 , 1 }, { 3 , 1 }};
for ( auto it = map.begin(); it != map.end(); ++it) {
    // it->second = 2; // Illegal
    it. value () = 2 ; // Ok
}

Los tipos de solo movimiento deben tener un constructor de movimiento no lanzado (con direccionamiento abierto, no es posible mantener la fuerte garantía de excepción en repetición si el constructor de movimiento puede lanzar).
No hay soporte para algunos métodos relacionados con depósitos (como bucket_size , bucket , ...).

Estas diferencias también se aplican entre std::unordered_set y tsl::hopscotch_set .

Las garantías de seguridad de subprocesos y excepciones son las mismas que std::unordered_map/set (es decir, es posible tener varios lectores sin ningún escritor).

Política de crecimiento

La biblioteca admite múltiples políticas de crecimiento a través del parámetro de plantilla GrowthPolicy . La biblioteca proporciona tres políticas, pero usted puede implementar fácilmente las suyas propias si es necesario.

tsl::hh::poder_de_dos_políticas_de_crecimiento. Política predeterminada utilizada por tsl::(b)hopscotch_map/set . Esta política mantiene el tamaño de la matriz de depósitos de la tabla hash en una potencia de dos. Esta restricción permite que la política evite el uso de la operación de módulo lento para asignar un hash a un depósito; en lugar de hash % 2 ⁿ , utiliza hash & (2 ⁿ - 1) (consulte módulo rápido). Rápido, pero esto puede causar muchas colisiones con una función hash deficiente, ya que el módulo con una potencia de dos solo enmascara los bits más significativos al final.
tsl::hh::prime_growth_policy. Política predeterminada utilizada por tsl::(b)hopscotch_pg_map/set . La política mantiene el tamaño de la matriz de depósitos de la tabla hash en un número primo. Al asignar un hash a un depósito, el uso de un número primo como módulo dará como resultado una mejor distribución de los hashes entre los depósitos, incluso con una función hash deficiente. Para permitir que el compilador optimice la operación del módulo, la política utiliza una tabla de búsqueda con módulos primos constantes (consulte la API para obtener más detalles). Más lento que tsl::hh::power_of_two_growth_policy pero más seguro.
tsl::hh::mod_growth_policy. La política hace crecer el mapa mediante un factor de crecimiento personalizable pasado en el parámetro. Luego simplemente usa el operador de módulo para asignar un hash a un depósito. Más lento pero más flexible.

Si encuentra un rendimiento deficiente, verifique overflow_size() ; si no es cero, es posible que tenga muchas colisiones de hash. Cambie la función hash por algo más uniforme o pruebe con otra política de crecimiento (principalmente tsl::hh::prime_growth_policy ). Desafortunadamente, a veces es difícil protegerse contra colisiones (por ejemplo, ataques DoS en el mapa hash). Si es necesario, consulte también tsl::bhopscotch_map/set , que ofrece el peor de los casos de O(log n) en las búsquedas en lugar de O(n), consulte los detalles en el ejemplo.

Para implementar su propia política, debe implementar la siguiente interfaz.

 struct custom_policy {
    // Called on hash table construction and rehash, min_bucket_count_in_out is the minimum buckets
    // that the hash table needs. The policy can change it to a higher number of buckets if needed 
    // and the hash table will use this value as bucket count. If 0 bucket is asked, then the value
    // must stay at 0.
    explicit custom_policy (std:: size_t & min_bucket_count_in_out);
    
    // Return the bucket [0, bucket_count()) to which the hash belongs. 
    // If bucket_count() is 0, it must always return 0.
    std:: size_t bucket_for_hash (std:: size_t hash) const noexcept ;
    
    // Return the number of buckets that should be used on next growth
    std:: size_t next_bucket_count () const ;
    
    // Maximum number of buckets supported by the policy
    std:: size_t max_bucket_count () const ;
    
    // Reset the growth policy as if the policy was created with a bucket count of 0.
    // After a clear, the policy must always return 0 when bucket_for_hash() is called.
    void clear () noexcept ;
}

Instalación

Para usar hopscotch-map, simplemente agregue el directorio de inclusión a su ruta de inclusión. Es una biblioteca de solo encabezados .

Si usa CMake, también puede usar el destino exportado tsl::hopscotch_map desde CMakeLists.txt con target_link_libraries .

 # Example where the hopscotch-map project is stored in a third-party directory
add_subdirectory (third-party/hopscotch-map)
target_link_libraries (your_target PRIVATE tsl::hopscotch_map)

Si el proyecto se instaló mediante make install , también puede usar find_package(tsl-hopscotch-map REQUIRED) en lugar de add_subdirectory .

El código debería funcionar con cualquier compilador compatible con el estándar C++17.

Para ejecutar las pruebas necesitará la biblioteca Boost Test y CMake.

git clone https://github.com/Tessil/hopscotch-map.git
cd hopscotch-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hopscotch_map_tests

Uso

La API se puede encontrar aquí.

Todos los métodos aún no están documentados, pero replican el comportamiento de los de std::unordered_map y std::unordered_set , excepto si se especifica lo contrario.

Ejemplo

# include < cstdint >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >
# include < tsl/hopscotch_set.h >

int main () {
    tsl::hopscotch_map<std::string, int > map = {{ " a " , 1 }, { " b " , 2 }};
    map[ " c " ] = 3 ;
    map[ " d " ] = 4 ;
    
    map. insert ({ " e " , 5 });
    map. erase ( " b " );
    
    for ( auto it = map. begin (); it != map. end (); ++it) {
        // it->second += 2; // Not valid.
        it. value () += 2 ;
    }
    
    // {d, 6} {a, 3} {e, 7} {c, 5}
    for ( const auto & key_value : map) {
        std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
    }
    
        
    if (map. find ( " a " ) != map. end ()) {
        std::cout << " Found " a " . " << std::endl;
    }
    
    const std:: size_t precalculated_hash = std::hash<std::string>()( " a " );
    // If we already know the hash beforehand, we can pass it in parameter to speed-up lookups.
    if (map. find ( " a " , precalculated_hash) != map. end ()) {
        std::cout << " Found " a " with hash " << precalculated_hash << " . " << std::endl;
    }
    
    
    /*
     * Calculating the hash and comparing two std::string may be slow. 
     * We can store the hash of each std::string in the hash map to make 
     * the inserts and lookups faster by setting StoreHash to true.
     */ 
    tsl::hopscotch_map<std::string, int , std::hash<std::string>, 
                       std::equal_to<std::string>,
                       std::allocator<std::pair<std::string, int >>,
                       30 , true > map2;
                       
    map2[ " a " ] = 1 ;
    map2[ " b " ] = 2 ;
    
    // {a, 1} {b, 2}
    for ( const auto & key_value : map2) {
        std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
    }
    
    
    
    
    tsl::hopscotch_set< int > set;
    set. insert ({ 1 , 9 , 0 });
    set. insert ({ 2 , - 1 , 9 });
    
    // {0} {1} {2} {9} {-1}
    for ( const auto & key : set) {
        std::cout << " { " << key << " } " << std::endl;
    }
}

Búsquedas heterogéneas

Las sobrecargas heterogéneas permiten el uso de otros tipos además de Key para operaciones de búsqueda y borrado, siempre que los tipos utilizados sean hash y comparables a Key .

Para activar las sobrecargas heterogéneas en tsl::hopscotch_map/set , el ID calificado KeyEqual::is_transparent debe ser válido. Funciona de la misma manera que para std::map::find . Puede usar std::equal_to<> o definir su propio objeto de función.

Tanto KeyEqual como Hash deberán poder manejar los diferentes tipos.

# include < functional >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >


struct employee {
    employee ( int id, std::string name) : m_id(id), m_name(std::move(name)) {
    }
    
    // Either we include the comparators in the class and we use `std::equal_to<>`...
    friend bool operator ==( const employee& empl, int empl_id) {
        return empl. m_id == empl_id;
    }
    
    friend bool operator ==( int empl_id, const employee& empl) {
        return empl_id == empl. m_id ;
    }
    
    friend bool operator ==( const employee& empl1, const employee& empl2) {
        return empl1. m_id == empl2. m_id ;
    }
    
    
    int m_id;
    std::string m_name;
};

// ... or we implement a separate class to compare employees.
struct equal_employee {
    using is_transparent = void ;
    
    bool operator ()( const employee& empl, int empl_id) const {
        return empl. m_id == empl_id;
    }
    
    bool operator ()( int empl_id, const employee& empl) const {
        return empl_id == empl. m_id ;
    }
    
    bool operator ()( const employee& empl1, const employee& empl2) const {
        return empl1. m_id == empl2. m_id ;
    }
};

struct hash_employee {
    std:: size_t operator ()( const employee& empl) const {
        return std::hash< int >()(empl. m_id );
    }
    
    std:: size_t operator ()( int id) const {
        return std::hash< int >()(id);
    }
};


int main () {
    // Use std::equal_to<> which will automatically deduce and forward the parameters
    tsl::hopscotch_map<employee, int , hash_employee, std::equal_to<>> map; 
    map. insert ({ employee ( 1 , " John Doe " ), 2001 });
    map. insert ({ employee ( 2 , " Jane Doe " ), 2002 });
    map. insert ({ employee ( 3 , " John Smith " ), 2003 });

    // John Smith 2003
    auto it = map. find ( 3 );
    if (it != map. end ()) {
        std::cout << it-> first . m_name << " " << it-> second << std::endl;
    }

    map. erase ( 1 );



    // Use a custom KeyEqual which has an is_transparent member type
    tsl::hopscotch_map<employee, int , hash_employee, equal_employee> map2;
    map2. insert ({ employee ( 4 , " Johnny Doe " ), 2004 });

    // 2004
    std::cout << map2. at ( 4 ) << std::endl;
}

Ataque de denegación de servicio (DoS)

Además de tsl::hopscotch_map y tsl::hopscotch_set , la biblioteca proporciona dos opciones "seguras" más: tsl::bhopscotch_map y tsl::bhopscotch_set (todas con sus contrapartes pg ).

Estas dos adiciones tienen una complejidad asintótica en el peor de los casos de O(log n) para búsquedas y eliminaciones y un peor caso amortizado de O(log n) para inserciones (amortizado debido a la posibilidad de repetición que estaría en O(n)) . Incluso si la función hash asigna todos los elementos al mismo depósito, O (log n) aún se mantendría.

Esto proporciona seguridad contra ataques de denegación de servicio (DoS) de tabla hash.

Para lograr esto, las versiones seguras utilizan un árbol de búsqueda binario para los elementos desbordados (consulte los detalles de implementación) y, por lo tanto, necesitan que los elementos sean LessThanComparable . Se necesita un parámetro de plantilla Compare adicional.

# include < chrono >
# include < cstdint >
# include < iostream >
# include < tsl/hopscotch_map.h >
# include < tsl/bhopscotch_map.h >

/*
 * Poor hash function which always returns 1 to simulate
 * a Deny of Service attack.
 */
struct dos_attack_simulation_hash {
    std:: size_t operator ()( int id) const {
        return 1 ;
    }
};

int main () {
    /*
     * Slow due to the hash function, insertions are done in O(n).
     */
    tsl::hopscotch_map< int , int , dos_attack_simulation_hash> map;
    
    auto start = std::chrono::high_resolution_clock::now ();
    for ( int i= 0 ; i < 10000 ; i++) {
        map. insert ({i, 0 });
    }
    auto end = std::chrono::high_resolution_clock::now ();
    
    // 110 ms
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration. count () << " ms " << std::endl;
    
    
    
    
    /*
     * Faster. Even with the poor hash function, insertions end-up to
     * be O(log n) in average (and O(n) when a rehash occurs).
     */
    tsl::bhopscotch_map< int , int , dos_attack_simulation_hash> map_secure;
    
    start = std::chrono::high_resolution_clock::now ();
    for ( int i= 0 ; i < 10000 ; i++) {
        map_secure. insert ({i, 0 });
    }
    end = std::chrono::high_resolution_clock::now ();
    
    // 2 ms
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration. count () << " ms " << std::endl;
}