Discussion :

[marcelin88]

Bonjour,

Je dois réaliser un programme gérant les revenus d'une population. On a trois paramètres: le nom de l'individu , son adresse et ses revenus. Il ne peut pas y avoir plusieurs fois le même nom à la même adresse.
Quelle structure est la plus adaptée pour résoudre ce problème sachant que le temps d'execution doit être le plus court possible.
J'hésite entre un tas trié et un AVL.

[ol9245]

http://www.cplusplus.com/reference/map/multimap/

[Graffito]

Le plus perfomant me semble être une table de hachage qui pointe vers le tableau contenant les enregistrements.
Le hash code sera basé sur la concaténation Nom+Adresse.

La taille de la table sera la plus grande possible en fonction de la mémoire que l'on veut allouer à l'application.
Par exemple, une table de hash de 64 Mo pourra gérer des hash codes de 24 bits (64Mo = 256x256x256x4 octets) avec un risque de collision assez faible si on gère quelques dizaines de milliers de nom-addresse.

Pour gérer les collisions, on ajoutera aux enregistrements les index permettant de gérer les collisions en chainant entre eux les enregistrements de même hash code.

[ol9245]

Le plus perfomant me semble être une table de hachage qui pointe vers le tableau contenant les enregistrements.
Le hash code sera basé sur la concaténation Nom+Adresse.

La taille de la table sera la plus grande possible en fonction de la mémoire que l'on veut allouer à l'application.
Par exemple, une table de hash de 64 Mo pourra gérer des hash codes de 24 bits (64Mo = 256x256x256x4 octets) avec un risque de collision assez faible si on gère quelques dizaines de milliers de nom-addresse.

Pour gérer les collisions, on ajoutera aux enregistrements les index permettant de gérer les collisions en chainant entre eux les enregistrements de même hash code.

Oui, en effet, c'est mieux qu'une multimap si il n'a pas besoin de rechercher séparément par nom ou par adresse mais toujours par nom+adresse, ce qui est ele plus vraisemblable.
Est-ce qu'il y a une structure de données C++ pour les tables de hachage ?