Discussion :

[Schlada]

Hello

voila je bosse sur la focntion de hachage et jaurais voulu savoir comment realiser une fonction de hachage pour le resultat suivant :

[2^0x(valeur ASCII de la lettre)+...+2^nx(valeur ASCII de lettre)]mod m

m la taille de mon tableau

exemple avec le mot : OK avec m=6

je voudrais avoir

[2^0x(valeur ACSII de 0)+2^1x(valeur ACSII de K)]mod 6=

Mille de merci de votre aide

[Musaran]

^
nx

Quoi qu'est-ce ?

[Schlada]

desole c vrai ke c pas tres clair

2^nx(valeur ASCII de lettre)

je voulai dire par la 2 exposant n multiplie par la valeur ASCII de la lettre, n etant egale au nombre de lettre du mot moins 1 puisque au commence a 2 exposant 0.

Merci

[Ol']

Je ne vois pas bien où est ton problème. toutefois, sache que pour effectuer une multiplication par 2^n, tu peux faire un décalage vers la gauche de n bits sur ton nombre.

Pour ce qui est du modulo

a mod b est le reste de la division euclidienne de a par b.
Cela doit te donner quelquechose du style
a mod b = a - ((long)(a)/(long)(b)*b)

Au erreurs de calcul près...

Ol'

[golem]

Bonjour,

un modulo se fait avec %.

Ceci me semble être ce que tu veux:

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
 
#include <stdio.h>
#include <string.h>
 
unsigned my_hach( const char* pstr, unsigned m)
{
	unsigned l_i, l_r;
 
	if( !pstr)
		return 0;
 
	for( l_i=0, l_r=0; l_i < strlen(pstr); l_r += (1<<l_i)*pstr[l_i++]);
 
	return l_r % m;
};
 
int main()
{
	printf("%u\n", my_hach( "OK", 6) );
	return 0;
};

en cas de pstr nul, il faudra peut être convenir d'une autre valeur de retour que 0 ...

golem
+++

[Schlada]

Merci golem

c'est bien le fonction de hachage que je cherche, je vais pouvoir commencer a constituer mon dictionnaire

[regis1_1]

a quoi ca sert une fonction fonction de hachage?

[Choupi]

On cherche a associer à un element d'un ensemble un entier qui le caracterise. pour cela on utilise une fonction de hachage comme vu ci dessus.
Une bonne fonction de hachage fait en sorte que le nombre d'elements associés à chaque entier soit constant.

C'est pratique pour une recherche car dans ce cas son cout est de 1 ...

http://fastnet.univ-brest.fr/~gire/C..._C/node13.html

A voir le robleme des collisions...

Freif'