Implémentation d'une HashMap à l'aide d'une implémentation HashTable

Question

J'ai une implémentation de hachage qui contient des fonctions telles que insert, remove, find, exists. En utilisant cette hashtable, je voulais implémenter un hashmap. Je voulais donc créer une classe de paire simple qui contiendrait simplement une clé et une valeur. Il aurait surchargé operator= pour ne prendre en compte que l'égalité des touches. De plus, la fonction de hachage recevrait en entrée un objet paire et retournerait le hachage, en ne tenant compte que de la partie clé.

Ainsi, j'aurais un hashtable<pair> à l'intérieur de la hashmap qui serait essentiellement quelque chose comme hashtable<key> car il ne prendrait en compte que la partie clé et porterait simplement un membre de valeur.

Mais des problèmes sont apparus. Par exemple, je voulais implémenter une fonction exists qui vérifierait si une paire avec une clé spécifiée existait dans la hashmap. Donc, cela prendrait une clé et vérifierait si la clé est à l'intérieur de la carte. Cela serait mis en œuvre en utilisant le hashtable existe. Mais le hashtable::exists prend maintenant en entrée un type de paire.

Alors maintenant j'ai eu ces alternatives que je n'aime pas.

• Créer un objet paire avec la clé, et laisser la partie valeur non initialisée

• Cast de l'objet clé d'un objet paire (comme reinterpret_cast (& clé)) que les fonctions de Hashtable utiliseront uniquement la partie clé de la paire dans cette situation.

Le premier crée une copie inutile. Et avec l'adresse de la deuxième clé peut ne pas être égale à l'adresse de l'objet de la paire. Bien que je crois que je peux savoir pour que l'adresse de la clé en tenant compte du fait que je peux calculer

(&pair.key) - (&pair) 

Et en utilisant que je pouvais faire des moulages appropriés pour passer la clé comme une paire.

Des idées pour les alternatives?

Answer 1

Si vous regardez les implémentations existantes de carte de hachage comme google::dense_hash_maphere (je prends cela comme exemple parce que je crois qu'il est plus facile à lire que le code STL comme std::unordered_map), vous verrez que la carte de hachage n'est pas simplement un hachage basé sur un modèle table.

En d'autres termes, il est pas mis en œuvre comme:

template <class T> 
struct hash_table { ... }; 

template <class Key, class Value> 
using hash_map = hash_table<std::pair<Key, Value>>; 

... mais comme:

template <class Value, class Key> 
struct hash_table { ... }; 

template <class Key, class Value> 
struct hash_map 
{ 
    using ht = hash_table<std::pair<Key, Value>, Key>; 
    ht _ht; 
}; 

Puis, en hash_table<Value, Key> vous pouvez avoir insert(const Value&) mais aussi find(const Key&), que cette classe est au courant de tous les types.

En plus de cela, vous pouvez mettre en œuvre très facilement hash_set.La logique entière sera dans votre classe hash_table, hash_map et hash_set seulement transmettre les appels et faire quelques trucs cosmétiques pour le client de l'API.