Les conteneurs unordered_set et unordered_map de la bibliothèque standard C++ (STL) repoesnt sur une structure de données de type table de hachage avec chaînage (hachage ouvert). Pour implémenter ces deux structures de manière efficace, nous devons concevoir une table de hachage générique capable de manipuler aussi bien des clés uniques que des paires clé-valeur.
1. Architecture de la table de hachage sous-jacente
La clé du polymorphisme antre set et map réside dans le paramétrage des templates. La table de hachage doit accepter un type de données générique T, qui sera K pour le set et std::pair<const K, V> pour le map.
// Structure du nœud pour le chaînage
template<class T>
struct NoeudHachage {
T _donnee;
NoeudHachage<T>* _suivant;
NoeudHachage(const T& data)
: _donnee(data)
, _suivant(nullptr)
{}
};
2. Conception des foncteurs d'extraction et de hachage
Puisque la table de hachage traite un type T opaque, elle a besoin d'un mécanisme pour extraire la clé de T afin de calculer l'indice de hachage. Nous utilisons pour cela un foncteur KeyOfT.
// Pour unordered_set : la donnée est la clé
struct SetExtraction {
const K& operator()(const K& cle) {
return cle;
}
};
// Pour unordered_map : la clé est le premier élément de la paire
struct MapExtraction {
const K& operator()(const std::pair<const K, V>& kv) {
return kv.first;
}
};
Pour transformer la clé en un entier utilisable pour l'indexation, un foncteur de hachage est nécessaire. Pour les types complexes comme std::string, nous utilisons l'algorithme BKDR :
template<class K>
struct GenerateurHachage {
size_t operator()(const K& cle) { return (size_t)cle; }
};
// Spécialisation pour les chaînes de caractères
template<>
struct GenerateurHachage<std::string> {
size_t operator()(const std::string& s) {
size_t hash = 0;
for (char ch : s) {
hash = hash * 131 + ch;
}
return hash;
}
};
3. Système d'itérateurs
L'itérateur d'une table de hachage avec chaînage doit pouvoir passer d'un nœud au suivant au sein d'une liste, puis sauter au premier nœud du prochain compartiment (bucket) non vide lorsque la liste actuelle est épuisée.
template<class K, class T, class KeyOfT, class Hash>
class TableHachage;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct IterateurHachage {
typedef NoeudHachage<T> Noeud;
typedef TableHachage<K, T, KeyOfT, Hash> Table;
typedef IterateurHachage<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Noeud* _noeud;
const Table* _table_ref;
IterateurHachage(Noeud* n, const Table* t) : _noeud(n), _table_ref(t) {}
Ref operator*() { return _noeud->_donnee; }
Ptr operator->() { return &(_noeud->_donnee); }
Self& operator++() {
if (_noeud->_suivant) {
_noeud = _noeud->_suivant;
} else {
Hash hf;
KeyOfT kot;
size_t indice = hf(kot(_noeud->_donnee)) % _table_ref->_buckets.size();
indice++;
while (indice < _table_ref->_buckets.size()) {
if (_table_ref->_buckets[indice]) {
_noeud = _table_ref->_buckets[indice];
return *this;
}
indice++;
}
_noeud = nullptr;
}
return *this;
}
bool operator!=(const Self& it) const { return _noeud != it._noeud; }
};
4. Implémentation de la table de hachage
La classe principale gère le redimensionnement automatique pour maintenir un facteur de charge approprié (généralement proche de 1.0 dans le cas du chaînage).
template<class K, class T, class KeyOfT, class Hash = GenerateurHachage<K>>
class TableHachage {
template<class K, class T, class R, class P, class Kot, class H>
friend struct IterateurHachage;
typedef NoeudHachage<T> Noeud;
public:
typedef IterateurHachage<K, T, T&, T*, KeyOfT, Hash> iterator;
std::pair<iterator, bool> Inserer(const T& data) {
KeyOfT extraction;
Hash hachage;
iterator it = Chercher(extraction(data));
if (it != end()) return {it, false};
// Redimensionnement si nécessaire
if (_nb_elements == _buckets.size()) {
size_t nouvelle_taille = _buckets.empty() ? 11 : _buckets.size() * 2;
std::vector<Noeud*> nouvelle_table(nouvelle_taille, nullptr);
for (auto& node_ptr : _buckets) {
while (node_ptr) {
Noeud* prochain = node_ptr->_suivant;
size_t pos = hachage(extraction(node_ptr->_donnee)) % nouvelle_taille;
node_ptr->_suivant = nouvelle_table[pos];
nouvelle_table[pos] = node_ptr;
node_ptr = prochain;
}
}
_buckets.swap(nouvelle_table);
}
size_t index = hachage(extraction(data)) % _buckets.size();
Noeud* nouveau = new Noeud(data);
nouveau->_suivant = _buckets[index];
_buckets[index] = nouveau;
_nb_elements++;
return {iterator(nouveau, this), true};
}
iterator Chercher(const K& cle) const {
if (_buckets.empty()) return end();
Hash hachage;
KeyOfT extraction;
size_t index = hachage(cle) % _buckets.size();
Noeud* actuel = _buckets[index];
while (actuel) {
if (extraction(actuel->_donnee) == cle) return iterator(actuel, this);
actuel = actuel->_suivant;
}
return end();
}
iterator begin() const {
for (size_t i = 0; i < _buckets.size(); ++i) {
if (_buckets[i]) return iterator(_buckets[i], this);
}
return end();
}
iterator end() const { return iterator(nullptr, this); }
private:
std::vector<Noeud*> _buckets;
size_t _nb_elements = 0;
};
5. Encapsulation des conteneurs finaux
Une fois la table de hachage générique implémentée, les classes unordered_set et unordered_map deviennent de simples enterfaces deleguant le travail à la TableHachage.
// Exemple pour unordered_map
template<class K, class V, class Hash = GenerateurHachage<K>>
class MonUnorderedMap {
struct MapKeyOfT {
const K& operator()(const std::pair<const K, V>& kv) { return kv.first; }
};
TableHachage<K, std::pair<const K, V>, MapKeyOfT, Hash> _table;
public:
typedef typename TableHachage<K, std::pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
std::pair<iterator, bool> insert(const std::pair<K, V>& kv) {
return _table.Inserer(kv);
}
V& operator[](const K& key) {
auto res = _table.Inserer({key, V()});
return res.first->second;
}
iterator begin() { return _table.begin(); }
iterator end() { return _table.end(); }
};
Cette approche modulaire permet d'éviter la duplication de code complexe lié à la gestion des collisions et du redimensionnement mémoire, tout en offrant la flexibilité requise pour supporter différentes sémantiques de stockage.