Coût d'un algorithme avec des variantes "open adressing"

[JBB]

Bonjour, j'ai des doutes sur la justesse de la réponse que j'ai donnée à cette question si quelqu'un peut me donner une main moi je suis trop :--: :

On veut insérer n=20 000 entiers naturels dans un vecteur de taille M=50 021 (qui es un nombre premier).
On définit pour cela la suite fonctions d'adressage ouvert (i est ici un indice):

h0(x)=x mod M
pour tout i entre 1 et M hi(x)=1+ hi-1(x) mod M.

On insère d'abord les n/2 naturels allant de 0 a 9999 et les n/2 entiers allant de 10 042 a 10 141.

Donner le coût de chaque insertion. Si ce coût n'est pas constant, dire comment améliorer l'algorithme.

Réponse:

Nous avons un dictionnaire où les clés sont les indices du vecteur et les valeurs les naturels.

Le coût des n/2 premières insertions est constant car il n'y a pas collision de clés, les résidus étant tous différents modulo M.

Cependant M divise 10 042 donc les n/2 insertions suivantes collisionnent toutes avec les n/2 insertions précédentes une à une.

Là vient mon doute:
en cas de collision la nouvelle clé adressé à l'élément à insérer est (par exemple pour le premier élément 10 042)
Clé= 1+h0(x)=1+0=1 qui colisionne avec la clé de 1 et ainsi de suite jusque 9999
ou bien alors

en cas de collision la nouvelle clé adressée à l'élement à insérer est: (par exemple pour le premier élément 10 042)
Clé= h0(x) +2*h1(x)+-----(M-1)*hM(x) somme dont le coût est O(M) donc non constant.

Pour rémédier à ce problème il faut veiller à ne pas prendre une liste de nombres qui commence par le même nombre dans l'anneau Z/Z(M) ou alors si c'est le cas augmenter de plus de 1 le terme de la suite qui définit les fonctions d'adressage ouvert.

[Patastronch]

Y a de trucs qui m'échapent, j'ai pas du capter un truc :

[...]n=20 000 entiers naturels [...]
On insère d'abord les n/2 naturels allant de 0 a 9999 et les n/2 entiers allant de 10 042 a 10 141[...]

entre 10042 et 10141 y a pas 10000 entiers non ?

[...]M=50 021 [...]

Cependant M divise 10 042 donc les n/2 insertions suivantes collisionnent toutes avec les n/2 insertions précédentes une à une.
[...]

Euh en quoi 50021 divise 10 042 ?

[buzard]

C'est quoi ce langage, tu peut pas parler comme tous le monde et dire fonction de hachage, table de hachage et tous ca. on y comprend rien à ta terminologie chelou.
Un dictionnaire ca à pas de clé, c'est juste une structre qui conserve ce qu'on pourait appeler l'ordre lexicographique. L'association d'une valeur à une clef, ce fait avec une table associatif, ou table de hashage. Bref soit ton prof utilise des bouquins trop vieux, soit tu sait pas lire les tiens.

L'adressage ouvert (lineaire) c'est juste une methode qui permet d'eviter les collisions dans les table de hachage, elle n'est pas la seul, mais donne de bonne performance lorsque la table est peu dense. De toute manière tu auras toujours un pire des cas, et avec une table de has ce pire cas c'est en O(n). On ne peut qu'esperer ne pas tomber dessus.