salut
 
quel est la meilleur méthode pour la gestion des collisions dans un hash table, il me faut la plus performante... (j'utilise des tableau)
 
merci

la plus performante en terme de quoi ?

Tout dépend de la taille de la table... Si tu as un tableau de 100 et que tu dois y mettres 10 données, les collisions seront plutôt rares..
 
à l'inverse, 1000 infos dans un tableau de 100 généreront beaucoup de collisions.
 
 
 
Voici quelques trucs que j'avais noté à ce sujet :
HACAHGE OUVERT (avec file)
==============
Type de hachage ouvert, cas d'école (données RAM et pas sur HD
|0 ---> Nicolas ---> Marc
|1
|2 ---> Igor
 
Les collisions sont simplement enfilées à la suite les une des autres.
 
HACHAGE OUVERT
==============
Dans la pratique, on utilise des index de taille au minimum 20% plus grande
que le taille des enregistrement, pour empêcher les collisions. il n'y a alors
plus de files. lorsque qu'une case est prise, on la place dans la suivante,
jusqu'à qu'on trouve un "blanc" (voilà pourquoi les 20% supplémentaire)
 
HACHAGE FERME (avec réserve)
============================
le tableau contient l'information, + un pointeur (mémoire ou physique)
En cas de collision (Fanfan --> Lea) on mets Fanfan dans la réserve et on pointe
Jean vers cet endroit de la réserve. En cas de double collision (Lea) on continue
de pointer
 
=============
|0 Jean(0)     | xx
|              |
|2 Zoe(2)      | NULL
|              |
|¬¬¬¬¬¬¬¬¬¬¬¬¬¬|
|xx Fanfan(0)  |  xy
|xy Lea(0)     |  NULL
|xz            |

tout dépend surtout de si tu veux avoir la possibilité de faire des suppressions

C'est clair qu'avec les files les suppressions deviennent lourdes à gérer. quoique

euh par rapport un truc sans file, je dis non

 
hachage ouvert, avec une taille étant un nombre premier suffisament grand pour le nombre d'éléments à stoquer, avec une fonction de hachage qui a une bonne répartition pour le type d'éléments stoqués

 
Oui c'est vrai. Les files c'est pas plus mal pour les suppressions tout compte fait  

 
tu as un algo de cette technique?

euh oui, donne moi ton mail en pv

Hello @ tous,
 
J'ai un tableau qui doit gérer 1000 clients (Nom,Prénom:STRING(30 char. max))
 
est-il possible de faire une table hash sans collision ?
si oui, connaissez-vous la formule coresspondante ?
 
svp, Merci
 
 

Knuth, "The art of computer programming" tu as dedans les critères pour choisir la taille du tableau et comment calculer cette taille.

pour toute serie de données connues à l'avance, il existe une fonction de hachage parfaite, c'est un théorème.

 
huh    
 
théorème de qui ? de quoi ?    
 
 
Désolé, je suis un newb'      
 

qui dit que la réponse est oui. Par contre, j'ai pas l'algo sous la main.
 
De qui, j'ai ai aucune idée. Il est aussi dans le Knuth.

 
tu penses que tu arrivais à le retrouver svp ?      
 
  pour les autres, on s'est jamais....  
 
 

non
1) je suis dans le trou-du-cul de l'Allemagne
2) j'ai pas de bibliothèque sous la main

je passais dans la section comme ça:
 
enfaite chuis aller jeter un coup d'oeil dans le Knuth, la section HASH se trouve dans le 2ème volume, si je me rappelle bien,
bref j'ai rien capter à ce livre pour matheux anglophone, y'a de ces formules de ouf  
 

beaucoup de choses tres interessantes sur le sujet sur le site de Bob Jenkins:
 
http://burtleburtle.net/bob/
 
(mais le site à l'air out en ce moment)

 
C'est simple, pour cela tu associes un integer i pour le client i...un integer i+1 pour le client i+1. Tu alloues un tableau de taille 1000. L'integer associe au client correspond a la case du tableau.
 
PS : si tu veux etre SUR de ne pas avoir de collision dans une table de hash, il te faut au MINIMUM un tableau de taille egal au nombre de donnees que tu veux y mettre...cela va de soi  

pas nécessairement. car deux éléments peuvent avoir le même hash...

ça fait longtemps que je ne me suis pas remis sur le programme( donc j'ai pas encore tout ma tête, excusez-moi si je dis des bêtises )
 
donc ta solution Griz: serait exemple lors du recherche d'un client dans le tableau que je le recherche par son numéro integer i ?
 
paske l'avantage du hash, c'est de pouvoir définir un clé *si possible* unique qui coressponderait à une case(index) du tableau(bon bien sur en ayant une taille de tableau assez "modéré"...) donc si je veux faire une recherche par nom sans vouloir parcourir tous le tableau je fais comment avec l'histoire du integer i ???
 

unique non. la plus unique possible oui. relis ma première intervention

 
c tout con, la personne est stockee a l'indice i du tableau. Indice associe a la personne (en plus de son nom, prenom,etc..)

 
ma solution ne fait intervenir AUCUN hashcode hein !!!  

 
selon Knuth ou nraynaud, il parait que oui c'est possible (ça m'étonne aussi, m'enfin les math c'est puissant lol)
 

 
et pour faire une recherche d'une personne tu fais comment ?      
 

et pourtant, c'est bien le titre du topic... --> HS

bonne question  

 
et ben tu as son integer associe. On te donnes le pointeur sur la personne et voila

je suis pas d'accord. moi place ces éléments dans un tableau de hash de longueur n (n =10)
 
"Marc"
"Nicolas"
"Marc"
 
en tout logique les marc vont se trouver ensemble... (sinon ton algo de hash est inutilisable pour les retrouver) et pourtant tu as encore le triple de l'espace et déjà des collisions

et... le pointeur associé tu l'obtiens comment ? je crois que tu n'as pas vraiment compris à quoi sert une table de hachage toi  

 
Les tableaux et les tables de hach c tres proche hein  

 
oui c'est sur que si tu tombes 2 fois sur le meme prénom...
 
m'enfin avec le nom ET le prénom, c'est faisable ??? (bien sur il faut absolument que dans le monde il y'aurait qu'une seul personne ayant le meme nom de famille et le meme prénom)
 

 
ben je sais pas, moi j'imagine une structure de donnee (bon jse pas si c exactement pareil en bdd) :
 
struct personne i
{
 int placedsletableau
 char *nom
 char *prenom
}
 
fonction personne chercherpersonne (int placedsletableau)
{
 retourner tableau[placedsletableau]
}
 
void main ()
{
 personne pers = {0, "Jean", "Dupond"};
 chercherpersonne (pers.placedsletableau)
}
 
 
un truc comme ca koi...ca me pareil un peu facile, kkchose m'echappe sinon dans ce que tu ve faire exactement
}

 
je ne sais pas si tu as saisi l'avantage du hash ou si c'est moi qui capte vraiment pas ce que tu essaie de m'expliquer...
 
exemple concret: je veux faire une recherche par NOM uniquement, en tappant uniquement le nom comment je peux faire pour retrouver ton integer i sans à avoir parcourir tous le tableau ????
 
EDIT: GRILLED

 
Ha tres bien, ca s'eclairci pour moi ...donc du coup effectivement, tu es oblige de passer par du hashCode
Suffit d'appliquer une formule magique de hashCode sur les strings...mais evidemment la, tu n'est plus sur de ne pas avoir de collisions
Passer un integer t'aurais garanti l'unicite au lieu de passer par le nom
 
EDIT : ou alors, tu alloues un TRES TRES grand tableau, et la tu as plus de chances de ne pas avoir de collisions

 
ca yest le lien remarche
 
je vous conseil vraiment d'aller le voir!

 
Merci beaucoup    
 
  http://burtleburtle.net/bob/hash/perfect.html
 
mais pour te dire la vérité: je capte vraiment Q U E D A L      
 
si qqun aurait la bonté de nous expliqué un tout ptit peu svp