Les implémentations de C++ unordered_map doivent toutes utiliser le chainage. Il existe de nombreuses bonnes raisons pour lesquelles vous pourriez vouloir faire cela pour une table de hachage à usage général, qui sont discutées ici.
Cela a des implications énormes sur les performances. Plus important encore, cela signifie que les entrées de la table de hachage sont susceptibles d'être dispersées dans toute la mémoire de manière à rendre l'accès à chacune d'entre elles moins efficace d'un ordre de grandeur (ou quelque chose comme ça) que ce serait le cas si elles pouvaient être accessibles de manière séquentielle.
Heureusement, vous pouvez construire des tables de hachage qui, lorsqu'elles sont presque pleines, offrent un accès quasi séquentiel aux éléments adjacents. Cela se fait en utilisant l'adressage ouvert.
Puisque votre table de hachage n'est pas à usage général, vous pourriez essayer cela.
Voici, j'ai construit un conteneur de table de hachage simple avec adressage ouvert et sondage linéaire. Cela suppose quelques choses :
-
Vos clés sont déjà d'une certaine manière distribuées aléatoirement. Cela élimine le besoin d'une fonction de hachage (bien que de bonnes fonctions de hachage soient assez simples à construire, même si les grandes fonctions de hachage sont difficiles).
-
Vous n'ajoutez jamais que des éléments à la table de hachage, vous ne les supprimez pas. Si ce n'était pas le cas, vous devriez changer le vecteur used en quelque chose qui pourrait contenir trois états : USED, UNUSED, et TOMBSTONE où TOMBSTONE est l'état d'un élément supprimé et sert à poursuivre la sonde de recherche linéaire ou à arrêter une sonde d'insertion linéaire.
-
Vous connaissez la taille de votre table de hachage à l'avance, donc vous n'avez pas besoin de la redimensionner/re-hacher.
-
Vous n'avez pas besoin de traverser vos éléments dans un ordre particulier.
Évidemment, il existe probablement toutes sortes d'excellentes implémentations de tables de hachage à adressage ouvert en ligne qui résolvent bon nombre des problèmes ci-dessus. Cependant, la simplicité de ma table me permet de transmettre le point important.
Le point important est le suivant : ma conception permet de stocker toutes les informations de la table de hachage dans trois vecteurs. C'est-à-dire : la mémoire est contiguë.
La mémoire contiguë est rapide à allouer, rapide à lire et rapide à écrire. L'effet de ceci est profond.
En utilisant le même test que dans ma réponse précédente, j'obtiens les temps suivants :
Enregistrer. Temps d'enregistrement = 82.9345 ms
Charger. Temps de chargement = 115.111 ms
Cela représente une diminution de 95% du temps d'enregistrement (22 fois plus rapide) et une diminution de 98% du temps de chargement (62 fois plus rapide).
Code :
#include
#include
#include
#include
#include
#include
#include
#include
const int TEST_TABLE_SIZE = 10000000;
template
class SimpleHash {
public:
int usedslots = 0;
std::vector keys;
std::vector vals;
std::vector used;
//size0 should be a prime and about 30% larger than the maximum number needed
SimpleHash(int size0){
vals.resize(size0);
keys.resize(size0);
used.resize(size0/8+1,0);
}
//If the key values are already uniformly distributed, using a hash gains us
//nothing
uint64_t hash(const K key){
return key;
}
bool isUsed(const uint64_t loc){
const auto used_loc = loc/8;
const auto used_bit = 1<<(loc%8);
return used[used_loc]&used_bit;
}
void setUsed(const uint64_t loc){
const auto used_loc = loc/8;
const auto used_bit = 1<<(loc%8);
used[used_loc] |= used_bit;
}
void insert(const K key, const V val){
uint64_t loc = hash(key)%keys.size();
//Use linear probing. Can create infinite loops if table too full.
while(isUsed(loc)){ loc = (loc+1)%keys.size(); }
setUsed(loc);
keys[loc] = key;
vals[loc] = val;
}
V& get(const K key) {
uint64_t loc = hash(key)%keys.size();
while(true){
if(!isUsed(loc))
throw std::runtime_error("Item not present!");
if(keys[loc]==key)
return vals[loc];
loc = (loc+1)%keys.size();
}
}
uint64_t usedSize() const {
return usedslots;
}
uint64_t size() const {
return keys.size();
}
};
typedef SimpleHash table_t;
void SaveSimpleHash(const table_t &map){
std::cout<<"Enregistrer. ";
const auto start = std::chrono::steady_clock::now();
FILE *f = fopen("/z/map", "wb");
uint64_t size = map.size();
fwrite(&size, 8, 1, f);
fwrite(map.keys.data(), 8, size, f);
fwrite(map.vals.data(), 1, size, f);
fwrite(map.used.data(), 1, size/8+1, f);
fclose(f);
const auto end = std::chrono::steady_clock::now();
std::cout<<"Temps d'enregistrement = "<< std::chrono::duration (end-start).count() << " ms" << std::endl;
}
table_t LoadSimpleHash(){
std::cout<<"Charger. ";
const auto start = std::chrono::steady_clock::now();
FILE *f = fopen("/z/map", "rb");
uint64_t size;
fread(&size, 8, 1, f);
table_t map(size);
fread(map.keys.data(), 8, size, f);
fread(map.vals.data(), 1, size, f);
fread(map.used.data(), 1, size/8+1, f);
fclose(f);
const auto end = std::chrono::steady_clock::now();
std::cout<<"Temps de chargement = "<< std::chrono::duration (end-start).count() << " ms" << std::endl;
return map;
}
int main(){
//Perfectly horrendous way of seeding a PRNG, but we'll do it here for brevity
auto generator = std::mt19937(12345); //Combination of my luggage
//Generate values within the specified closed intervals
auto key_rand = std::bind(std::uniform_int_distribution(0,std::numeric_limits::max()), generator);
auto val_rand = std::bind(std::uniform_int_distribution(std::numeric_limits::lowest(),std::numeric_limits::max()), generator);
table_t map(1.3*TEST_TABLE_SIZE);
std::cout<<"Table créée de taille "<
