Discussion :

[J4e8a16n]

Bonjour à tous,


C'est une question plutôt mathématique.............. J'ai tenté de multiplier par 3 5 7 11.
Toujours , j'ai des doublons pour 10 appels sur 11, 8 appels sur 11, 5 appels sur 11..

Code :

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#define HASHSIZE 11
#include <stdio.h>
 
static struct nlist *hashtab[HASHSIZE] ;  /*   pointer table */
unsigned hash (char *s);
 
int main(void)
{
	printf("%u\t= Hello, world\n", hash ("Hello, world"));
	printf("%u\t= hello, world\n", hash ("hello, world"));
	printf("%u\t= Helo, world\n", hash ("Helo, world"));
	printf("%u\t= Hella, world\n", hash ("Hella, world"));
	printf("%u\t= Hello, World\n", hash ("Hello, World"));
	printf("%u\t= Hello, WOrld\n", hash ("Hello, WOrld"));
	printf("%u\t= Hello, worldd\n", hash ("Hello, worldd"));
	printf("%u\t= Hello, wfrld\n", hash ("Hello, wfrld"));
	printf("%u\t= Hello, worf\n", hash ("Hello, worf"));
	printf("%u\t= Hlo, world\n", hash ("Hlo, world"));
	return 0;
}
 
 
unsigned hash (char *s)
{
  unsigned hashval;
  for (hashval = 0; *s != '\0' ; s++ )
    {
    hashval += *s + 5 * hashval;
    }
  return hashval % HASHSIZE;
}
 
/*   
8       = Hello, world
1       = hello, world
8       = Helo, world
6       = Hella, world
6       = Hello, World
2       = Hello, WOrld
0       = Hello, worldd
0       = Hello, wfrld
5       = Hello, worf
3       = Hlo, world
 */

[kwariz]

bonjour,
bah avec un hashsize a 11 tu ne peux pas non plus t'attendre à des merveilles !
Pourquoi ne pas choisir une fonction de hash plus évoluée genre CRC32, et une liste plutôt qu'un tableau à taille fixe ?

[J4e8a16n]

CRC32

Ça me semble un peu avancé...

[kwariz]

bah ça marche bien sur les chaînes, mais bon ... une hashtable avec 11 positions c;est court ; tu auras forcément beaucoup de collisions, et ce quelle que soit la hashfunction.