hopscotch map Télécharger - hopscotch map Téléchargement du code source

Une implémentation C++ d'une carte de hachage rapide et d'un ensemble de hachage utilisant le hachage à la marelle

La bibliothèque hopscotch-map est une implémentation C++ d'une carte de hachage rapide et d'un ensemble de hachage utilisant l'adressage ouvert et le hachage à la marelle pour résoudre les collisions. Il s'agit d'une structure de données conviviale pour le cache offrant de meilleures performances que std::unordered_map dans la plupart des cas et est très similaire à google::dense_hash_map tout en utilisant moins de mémoire et en offrant plus de fonctionnalités.

La bibliothèque fournit les classes principales suivantes : tsl::hopscotch_map , tsl::hopscotch_set , tsl::hopscotch_pg_map et tsl::hopscotch_pg_set . Les deux premiers sont plus rapides et utilisent une politique de croissance en puissance de deux, les deux derniers utilisent plutôt une politique de croissance principale et sont capables de mieux gérer une mauvaise fonction de hachage. Utilisez la version principale s'il existe un risque de répétition de modèles dans les bits inférieurs de votre hachage (par exemple, vous stockez des pointeurs avec une fonction de hachage d'identité). Voir GrowthPolicy pour plus de détails.

En plus de ces classes, la bibliothèque fournit également tsl::bhopscotch_map , tsl::bhopscotch_set , tsl::bhopscotch_pg_map et tsl::bhopscotch_pg_set . Ces classes ont une exigence supplémentaire pour la clé, elle doit être LessThanComparable , mais elles fournissent une meilleure limite supérieure asymptotique, voir les détails dans l'exemple. Néanmoins, si vous n'avez pas d'exigences spécifiques (risque d'attaques DoS par hachage), tsl::hopscotch_map et tsl::hopscotch_set devraient être suffisants dans la plupart des cas et devraient être votre choix par défaut car ils fonctionnent mieux en général.

Un aperçu du hachage à la marelle et quelques détails de mise en œuvre peuvent être trouvés ici.

Un benchmark de tsl::hopscotch_map par rapport à d'autres cartes de hachage peut être trouvé ici. Cette page donne également quelques conseils sur la structure de table de hachage que vous devriez essayer pour votre cas d'utilisation (utile si vous êtes un peu perdu avec les multiples implémentations de tables de hachage dans l'espace de noms tsl ).

Principales caractéristiques

Bibliothèque d'en-tête uniquement, ajoutez simplement le répertoire d'inclusion à votre chemin d'inclusion et vous êtes prêt à partir. Si vous utilisez CMake, vous pouvez également utiliser la cible exportée tsl::hopscotch_map à partir du fichier CMakeLists.txt.
Table de hachage rapide, voir benchmark pour quelques chiffres.
Prise en charge des clés/valeurs constructibles à déplacement uniquement et non par défaut.
Prise en charge des recherches hétérogènes permettant l'utilisation de find avec un type différent de Key (par exemple, si vous avez une carte qui utilise std::unique_ptr<foo> comme clé, vous pouvez utiliser un foo* ou un std::uintptr_t comme paramètre de clé pour find sans construire un std::unique_ptr<foo> , voir exemple).
Pas besoin de réserver une valeur sentinelle aux clés.
Possibilité de stocker la valeur de hachage lors de l'insertion pour un remaniement et une recherche plus rapides si le hachage ou les fonctions égales de clé sont coûteuses à calculer (voir le paramètre de modèle StoreHash).
Si le hachage est connu avant une recherche, il est possible de le passer en paramètre pour accélérer la recherche (voir paramètre precalculated_hash dans l'API).
Les tsl::bhopscotch_map et tsl::bhopscotch_set fournissent le pire des cas de O(log n) lors des recherches et des suppressions, ce qui rend ces classes résistantes aux attaques par déni de service (DoS) par table de hachage (voir les détails dans l'exemple).
La bibliothèque peut être utilisée avec les exceptions désactivées (via l'option -fno-exceptions sur Clang et GCC, sans option /EH sur MSVC ou simplement en définissant TSL_NO_EXCEPTIONS ). std::terminate est utilisé en remplacement de l'instruction throw lorsque les exceptions sont désactivées.
API très similaire à std::unordered_map et std::unordered_set .

Différences par rapport à `std::unordered_map`

tsl::hopscotch_map essaie d'avoir une interface similaire à std::unordered_map , mais certaines différences existent.

L'invalidation de l'itérateur lors de l'insertion ne se comporte pas de la même manière. En général toute opération modifiant la table de hachage, sauf erase , invalide tous les itérateurs (voir API pour plus de détails).
Les références et les pointeurs vers des clés ou des valeurs dans la carte sont invalidés de la même manière que les itérateurs vers ces clés-valeurs lors de l'insertion.
Pour les itérateurs, operator*() et operator->() renvoient une référence et un pointeur vers const std::pair<Key, T> au lieu de std::pair<const Key, T> , rendant la valeur T non modifiable. Pour modifier la valeur, vous devez appeler la méthode value() de l'itérateur pour obtenir une référence mutable. Exemple:

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
}

Les types de déplacement uniquement doivent avoir un constructeur de déplacement nul (avec un adressage ouvert, il n'est pas possible de conserver la forte garantie d'exception lors du rehachage si le constructeur de déplacement peut lancer).
Aucune prise en charge de certaines méthodes liées aux buckets (comme bucket_size , bucket , ...).

Ces différences s'appliquent également entre std::unordered_set et tsl::hopscotch_set .

Les garanties de sécurité des threads et d'exceptions sont les mêmes que celles std::unordered_map/set (c'est-à-dire qu'il est possible d'avoir plusieurs lecteurs sans écrivain).

Politique de croissance

La bibliothèque prend en charge plusieurs politiques de croissance via le paramètre de modèle GrowthPolicy . Trois politiques sont fournies par la bibliothèque mais vous pouvez facilement mettre en œuvre la vôtre si nécessaire.

tsl :: hh :: power_of_two_growth_policy. Politique par défaut utilisée par tsl::(b)hopscotch_map/set . Cette stratégie maintient la taille du tableau de compartiments de la table de hachage à une puissance de deux. Cette contrainte permet à la politique d'éviter l'utilisation de l'opération modulo lente pour mapper un hachage à un compartiment, au lieu du hash % 2 ⁿ , elle utilise hash & (2 ⁿ - 1) (voir modulo rapide). Rapide mais cela peut provoquer beaucoup de collisions avec une mauvaise fonction de hachage car le modulo avec une puissance de deux ne masque finalement que les bits de poids fort.
tsl::hh::prime_growth_policy. Politique par défaut utilisée par tsl::(b)hopscotch_pg_map/set . La politique maintient la taille du tableau de compartiments de la table de hachage à un nombre premier. Lors du mappage d'un hachage sur un compartiment, l'utilisation d'un nombre premier comme modulo entraînera une meilleure répartition des hachages dans les compartiments, même avec une mauvaise fonction de hachage. Pour permettre au compilateur d'optimiser le fonctionnement modulo, la politique utilise une table de recherche avec des modulos à nombres premiers constants (voir API pour plus de détails). Plus lent que tsl::hh::power_of_two_growth_policy mais plus sécurisé.
tsl :: hh :: mod_growth_policy. La stratégie agrandit la carte selon un facteur de croissance personnalisable passé en paramètre. Il utilise ensuite simplement l'opérateur modulo pour mapper un hachage à un compartiment. Plus lent mais plus flexible.

Si vous rencontrez de mauvaises performances, vérifiez overflow_size() , s'il n'est pas nul, vous risquez d'avoir de nombreuses collisions de hachage. Modifiez la fonction de hachage pour quelque chose de plus uniforme ou essayez une autre politique de croissance (principalement tsl::hh::prime_growth_policy ). Malheureusement, il est parfois difficile de se prémunir contre les collisions (par exemple, attaque DoS sur la hash map). Si nécessaire, vérifiez également tsl::bhopscotch_map/set qui propose le pire des cas de O(log n) lors des recherches au lieu de O(n), voir les détails dans l'exemple.

Pour implémenter votre propre politique, vous devez implémenter l'interface suivante.

 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 ;
}

Installation

Pour utiliser hopscotch-map, ajoutez simplement le répertoire include à votre chemin d'inclusion. Il s'agit d'une bibliothèque d'en-tête uniquement .

Si vous utilisez CMake, vous pouvez également utiliser la cible exportée tsl::hopscotch_map à partir du CMakeLists.txt avec 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 le projet a été installé via make install , vous pouvez également utiliser find_package(tsl-hopscotch-map REQUIRED) au lieu de add_subdirectory .

Le code doit fonctionner avec n’importe quel compilateur conforme à la norme C++17.

Pour exécuter les tests, vous aurez besoin de la bibliothèque Boost Test et de 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

Usage

L'API peut être trouvée ici.

Toutes les méthodes ne sont pas encore documentées, mais elles reproduisent le comportement de celles de std::unordered_map et std::unordered_set , sauf indication contraire.

Exemple

# 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;
    }
}

Recherches hétérogènes

Les surcharges hétérogènes permettent l'utilisation d'autres types que Key pour les opérations de recherche et d'effacement tant que les types utilisés sont hachables et comparables à Key .

Pour activer les surcharges hétérogènes dans tsl::hopscotch_map/set , l'identifiant qualifié KeyEqual::is_transparent doit être valide. Cela fonctionne de la même manière que pour std::map::find . Vous pouvez soit utiliser std::equal_to<> , soit définir votre propre objet fonction.

KeyEqual et Hash devront être capables de gérer les différents types.

# 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;
}

Attaque par déni de service (DoS)

En plus de tsl::hopscotch_map et tsl::hopscotch_set , la bibliothèque fournit deux autres options « sécurisées » : tsl::bhopscotch_map et tsl::bhopscotch_set (toutes avec leurs homologues pg ).

Ces deux ajouts ont une complexité asymptotique dans le pire des cas de O (log n) pour les recherches et les suppressions et un pire cas amorti de O (log n) pour les insertions (amorti en raison de la possibilité de remaniement qui serait en O (n)) . Même si la fonction de hachage mappe tous les éléments sur le même compartiment, le O(log n) serait toujours valable.

Cela fournit une sécurité contre les attaques par déni de service (DoS) par table de hachage.

Pour y parvenir, les versions sécurisées utilisent un arbre de recherche binaire pour les éléments survolés (voir détails d'implémentation) et nécessitent donc que les éléments soient LessThanComparable . Un paramètre de modèle Compare supplémentaire est nécessaire.

# 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;
}