Thibaut> Certes la structure est plus lourde qu'une table de hachage mais c'est optimisable.
Par exemple, j'ai mis des tableaux de 256 mais si tu utilise des identificateurs sans casse tu peux te restreindre à [a-z_0-9] soit 37 caractères et diminuer la consommation. Tu peux aussi utiliser une liste au lieu d'un tableau et là tu as la situation décrite par Hippo (mais tu as des perfs moins bonnes).
Ensuite, tu prends un mauvais exemple en te limitant à 3 chaînes car plus tu as de chaînes plus tu as de partage et donc la conso par chaîne diminue avec le nombre. Une idée aussi c'est de limiter la hauteur de l'arbre en remplaçant les feuilles par des tables de hachage sur la fin de la clef à partir d'une certaine hauteur, tu auras donc un morceau de dico ayant en fait une consommation raisonnable puisque très partagé et tu allègeras le temps dans les sous tables de hachage car elles seront moins surchargées. Bien sûr c'est plus dur à coder.
Ah, au fait, si tu veux stocker 10240 clefs de 5 caractères dans une table de hachage tu as par élément : la clef, un pointeur vers cette clef, un pointeur vers la valeur et un pointeur vers l'élément suivant, soit 10240x(6+4+4+4) = ~180k ce qui est déjà mort sur Ti
.