Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Loïc Joly
Philippe wrote:
Bonjoir,
Je voudrais savoir s'il existe des HashTable en C / C++ ?
Pas en standard, le plus proche de standard (en terme d'interface, mais pas de performances), c'est std::map, mais ce n'est pas une hash table.
Il existe par contre des implémentations disponibles. Peut-être même déjà fournies avec ton compilateur.
Pour pouvoir stocker des objets avec comme clé une chaine de caractères Et bien évidement retrouver l'objet voulu en temps constant...
Une hash table ne retrouve pas forcément l'objet en temps constant. Si effectivement le cas moyen est en O(1), le cas pire est je crois en O(n) avec les implémentations classiques (ca dépend de la structure utilisée pour les collisions).
-- Loïc
Philippe wrote:
Bonjoir,
Je voudrais savoir s'il existe des HashTable en C / C++ ?
Pas en standard, le plus proche de standard (en terme d'interface, mais
pas de performances), c'est std::map, mais ce n'est pas une hash table.
Il existe par contre des implémentations disponibles. Peut-être même
déjà fournies avec ton compilateur.
Pour pouvoir stocker des objets avec comme clé une chaine de caractères
Et bien évidement retrouver l'objet voulu en temps constant...
Une hash table ne retrouve pas forcément l'objet en temps constant. Si
effectivement le cas moyen est en O(1), le cas pire est je crois en O(n)
avec les implémentations classiques (ca dépend de la structure utilisée
pour les collisions).
Je voudrais savoir s'il existe des HashTable en C / C++ ?
Pas en standard, le plus proche de standard (en terme d'interface, mais pas de performances), c'est std::map, mais ce n'est pas une hash table.
Il existe par contre des implémentations disponibles. Peut-être même déjà fournies avec ton compilateur.
Pour pouvoir stocker des objets avec comme clé une chaine de caractères Et bien évidement retrouver l'objet voulu en temps constant...
Une hash table ne retrouve pas forcément l'objet en temps constant. Si effectivement le cas moyen est en O(1), le cas pire est je crois en O(n) avec les implémentations classiques (ca dépend de la structure utilisée pour les collisions).
-- Loïc
James Kanze
Loïc Joly writes:
|> Une hash table ne retrouve pas forcément l'objet en temps |> constant. Si effectivement le cas moyen est en O(1), le cas pire est |> je crois en O(n) avec les implémentations classiques (ca |> dépend de la structure utilisée pour les collisions).
Peut-être, mais pour certains types de données au moins, comme les chaînes de caractères, on connaît des fonctions de hachage qui sont assez efficace pour que, combiné avec une bonne implémentation de la table et un taux de remplissage pas trop fort, la risque de ne pas être O(1) est assez faible.
-- James Kanze mailto: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
Loïc Joly <loic.actarus.joly@wanadoo.fr> writes:
|> Une hash table ne retrouve pas forcément l'objet en temps
|> constant. Si effectivement le cas moyen est en O(1), le cas pire est
|> je crois en O(n) avec les implémentations classiques (ca
|> dépend de la structure utilisée pour les collisions).
Peut-être, mais pour certains types de données au moins, comme les
chaînes de caractères, on connaît des fonctions de hachage qui
sont assez efficace pour que, combiné avec une bonne
implémentation de la table et un taux de remplissage pas trop fort,
la risque de ne pas être O(1) est assez faible.
--
James Kanze mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
|> Une hash table ne retrouve pas forcément l'objet en temps |> constant. Si effectivement le cas moyen est en O(1), le cas pire est |> je crois en O(n) avec les implémentations classiques (ca |> dépend de la structure utilisée pour les collisions).
Peut-être, mais pour certains types de données au moins, comme les chaînes de caractères, on connaît des fonctions de hachage qui sont assez efficace pour que, combiné avec une bonne implémentation de la table et un taux de remplissage pas trop fort, la risque de ne pas être O(1) est assez faible.
-- James Kanze mailto: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
Thierry Miceli
Tu peux essayer d'utiliser hash_map. Je crois que hash_map ne fait pas partie du standard STL. Mais il est possible que la bibliothèque de STL que tu utilises le contienne. Personnellement j'utilise la bibliothèque stlport (www.stlport.org/) qui contient des implémentations hash_map et hash_multimap efficaces.
"Philippe" wrote in message news:bs28mb$98m$
Bonjoir,
Je voudrais savoir s'il existe des HashTable en C / C++ ?
Pour pouvoir stocker des objets avec comme clé une chaine de caractères Et bien évidement retrouver l'objet voulu en temps constant...
Merci d'avance. -- Philippe
Tu peux essayer d'utiliser hash_map.
Je crois que hash_map ne fait pas partie du standard STL. Mais il est
possible que la bibliothèque de STL que tu utilises le contienne.
Personnellement j'utilise la bibliothèque stlport (www.stlport.org/) qui
contient des implémentations hash_map et hash_multimap efficaces.
"Philippe" <nobody@nowhere.com> wrote in message
news:bs28mb$98m$1@news-reader5.wanadoo.fr...
Bonjoir,
Je voudrais savoir s'il existe des HashTable en C / C++ ?
Pour pouvoir stocker des objets avec comme clé une chaine de caractères
Et bien évidement retrouver l'objet voulu en temps constant...
Tu peux essayer d'utiliser hash_map. Je crois que hash_map ne fait pas partie du standard STL. Mais il est possible que la bibliothèque de STL que tu utilises le contienne. Personnellement j'utilise la bibliothèque stlport (www.stlport.org/) qui contient des implémentations hash_map et hash_multimap efficaces.
"Philippe" wrote in message news:bs28mb$98m$
Bonjoir,
Je voudrais savoir s'il existe des HashTable en C / C++ ?
Pour pouvoir stocker des objets avec comme clé une chaine de caractères Et bien évidement retrouver l'objet voulu en temps constant...
