Et comme le but du topic c'est de retrouver rapidement un mot dans un grand nombre de mots (1000 ?), qui feraient 5 lettres en moyenne, c'est même pas la peine... à moins que la TI89 ait quelques millions de Go cachés quelque part 
/ a - b - c
Racine - x - y - y
\ u - v - wThibaut (./31) :
Imagine si on ne place que ces 3 mots de 3 lettres : abc, xyy, uvw.
On a la racine : 256*4 octets
Puis, pour la lettre a, on crée un noeud afin d'y placer le b : 256*4 octets
Puis, on y crée un neud, relié au b, pour y placer le c : 256*4 octets Pour chaque mot on retrouve cette situation. Résultat : 3x3x256x4= 9 ko.
$tree = array(); // abc $tree['a'] = array(); $tree['a']['b'] = array(); $tree['a']['b']['c'] = array(); // xyy $tree['x'] = array(); $tree['x']['y'] = array(); $tree['x']['y']['y'] = array(); // xsd $tree['x']['s'] = array(); $tree['x']['s']['d'] = array(); // uvw $tree['u'] = array(); $tree['u']['v'] = array(); $tree['u']['v']['w'] = array();
array
'a' =>
array
'b' =>
array
'c' =>
array
empty
'x' =>
array
'y' =>
array
'y' =>
array
empty
's' =>
array
'd' =>
array
empty
'u' =>
array
'v' =>
array
'w' =>
array
empty
.
(le nb d'entrées est borné par la taille de la fenêtre de compression donc ça simplifie les choses, mais on peut aussi se débrouiller dans le cas général)BookeldOr (./35) :
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.
), donc déjà 10240x6 = 60k [+ de la marge pour que ça reste performant + l'éventuelle mémoire pour les valeurs] c'est plus raisonnable 
Pollux (./38) :
Déjà y a pas forcément besoin de pointeurs vers la clé ni vers la valeur, et ensuite on peut éviter le pointeur vers l'élément suivant en stockant dans la valeur de hash suivante jusqu'à ce qu'on trouve une case libre (c'est ce que fait xpack, qui a des clés et des valeurs de 2 octets donc un pointeur doublerait la taille), donc déjà 10240x6 = 60k [ de la marge pour que ça reste performant l'éventuelle mémoire pour les valeurs] c'est plus raisonnable
int hash_toutcon(const char *string)
{
unsigned int result;
result= 0;
do {
result+= *string;
} while (*string++ != 0);
return (result % 256);
}
C'est la fonction la plus simple et la plus rapide de toutes qui donnerait le meilleur résultat !
par contre quand elle marche pas correctement elle renvoie 0 pour la moitié des mots de plus de 6 caractères, c'est un peu con )Godzil (./40) :
Mais si ta table est mal dimmentionné, des qu'elle est pleine c'est fini tu peut plus ajouter d'élements, alors qu'une table de hashage chainé, meme si c'est un poil moins efficace, le nombre d'élement est "infini")
note aussi que tu compares des fonctions case-sensitive à des fonctions case-insensitive, c'est pas une très bonne idée ^^Note que la seule fonction insensible à la casse, c'est celle de wikipedia. L'algo est peut-être conçu pour ne donner de bons résultats que pour *s compris entre certaines bornes (d'où le lowchar).
Moi j'ai eu une réponse à ma question, je sais maintenant ce que je vais choisir dans tout ce binz de fonctions.
/**
* Computes the hashcode for this String. This is done with int arithmetic,
* where ** represents exponentiation, by this formula:<br>
* <code>s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]</code>.
*
* @return hashcode value of this String
*/
public int hashCode()
{
if (cachedHashCode != 0)
return cachedHashCode;
// Compute the hash code using a local variable to be reentrant.
int hashCode = 0;
int limit = count + offset;
for (int i = offset; i < limit; i++)
hashCode = hashCode * 31 + value[i];
return cachedHashCode = hashCode;
}Pollux (./47) :
je pense que celle de godzil a un bug, val et tmp devraient être unsigned (et puis je vois pas l'intérêt du test de signe à la fin si la fonction marchait correctementpar contre quand elle marche pas correctement elle renvoie 0 pour la moitié des mots de plus de 6 caractères, c'est un peu con
squalyl (./50) :
t'as regardé la jvm?au moins dans classpath
Très bon résultat aussi ! Elle semble aussi efficace que la fonction de wikipedia sans tolower. C'est pas étonnant, car ce sont... les mêmes ! à un facteur près : l'une multiplie par 33, l'autre par 31.int hach_wkp(const char *str)
{
unsigned int hash = 5381; // DJB Hash
unsigned int hash5 = 0;
const char *s;
for (s = str; *s; s++) {
hash5 += hash;
hash += *s;
}
return (hash + hash5<<5) & 0xFF;
}
lose lose
This hash function appeared in K&R (1st ed) but at least the reader was warned: "This is not the best possible algorithm, but it has the merit of extreme simplicity." This is an understatement; It is a terrible hashing algorithm, and it could have been much better without sacrificing its "extreme simplicity." [see the second edition!] Many C programmers use this function without actually testing it, or checking something like Knuth's Sorting and Searching, so it stuck. It is now found mixed with otherwise respectable code, eg. cnews. sigh. [see also: tpop]
unsigned long
hash(unsigned char *str)
{
unsigned int hash = 0;
int c;
while (c = *str++)
hash += c;
return hash;
}
Thibaut (./56) :
Ben je vais pas changer le modulo de la fonction de wikipedia, sinon elle serait plus comparable aux autres
int hach_wkp(const char *str)
{
unsigned int hash = 5381; // DJB Hash
const char *s;
for (s = str; *s; s++) {
hash = ((hash << 5) + hash) + *s;
}
while (hash%257==256)
hash /= 257;
return hash%257;
}unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}