Discussion :

[kamel.seg]

les éléments lors de stockage dans un hashtable ne sont pas organisé.

comment on peut trier ses éléments en langage C.

merci

[BainE]

bonjour,

ben comme dans tout les autres langages.
En fait c'est plus une question d'algorithmique.

Et la une recherche sur google t en dira plus :
- les algo en pseudo-code (voir en code)
- les avantages/inconvenients par rapport aux cas d utilisations ...

[Vincent Rogier]

les éléments lors de stockage dans un hashtable ne sont pas organisé.

comment on peut trier ses éléments en langage C.

merci

Pourquoi les "organiser" puisque c'est la fonction de hachage qui détermine la position dans la table ?

[wiztricks]

les éléments lors de stockage dans un hashtable ne sont pas organisé.

comment on peut trier ses éléments en langage C.

merci

Idées:
1 - Construire un itérateur pour parcourir l'ensemble de la table et les insérer à la bonne place (au sens tri) dans une liste doublement chainée.
2 - Associer une liste doublement chainée à la table de hash qui sera mise à jour à chaque insertion / suppression.
- W

[Médinoc]

L'idée de wiztricks est pas mal.

Mais il faut bien voir ce que cela donne sémantiquement: Il ne s'agit pas d'une "table de hachage triée" mais d'une "liste chaînée triée indexée par une table de hachage".

Il faut savoir qu'une table de hachage triée ne peut pas exister. Ses sous-conteneurs peuvent l'être, mais c'est tout.

Si tu veux un conteneur associatif trié, il te faut quelque chose de moins performant : tableau linéaire trié, liste chaînée trié, ou arbre binaire de recherche.

À mon sens, le plus performant question temps serait un arbre binaire de recherche cousu, indexé par une table de hachage si tu as vraiment besoin d'un accès rapide clé par clé.

Code C/C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct elementArbreCousuHache
{
	/* Données pour arbre binaire de recherche */
	struct elementArbreCousuHache * arbre_pere; /* facultatif */
	struct elementArbreCousuHache * arbre_filsGauche;
	struct elementArbreCousuHache * arbre_filsDroit;
 
	/* Données de couture de l'arbre.
	   Pour un A.B.R, le parcours est forcément infixe. */
	struct elementArbreCousuHache * liste_prec;
	struct elementArbreCousuHache * liste_suiv;
 
	/* Données de hachage (sous-conteneur: liste simplement chaînée, triée ou non) */
	struct elementArbreCousuHache * hachage_suiv;
 
 
	/* Les données stockées */
	...
};

[wiztricks]

L'idée de wiztricks est pas mal.

Mais il faut bien voir ce que cela donne sémantiquement: Il ne s'agit pas d'une "table de hachage triée" mais d'une "liste chaînée triée indexée par une table de hachage".
...

Merci!
Mais je n'aime pas cette sémantique: çà semble dire qu'on a marrié la carpe et le lapin alors que nous avons une table de hash d'un côté et une liste triée de l'autre bien séparées et accédées leur des primitives propres.
- W

[Médinoc]

Je disais "indexée" au sens base-de-donnée : Des données dans leur format propre, mais avec un index pour les retrouver plus vite.