Collisions primaires


Les collisions primaires (primary clustering) surviennent lorsque plusieurs clefs hashent au même endroit dans la table. Si la fonction de hash est bonne, les clefs sont distribuées de façon uniforme dans la table, et si la table est assez grande par rapport au nombre de clefs, la probabilité d'une collision reste faible.

Si, au contraire, la fonction de hash n'est pas très forte plusieurs clefs vont hasher au même endroit dans la table et causer des collisions. Non seulement cela va provoquer des collisions, cela va aussi rendre les fouilles secondaires difficiles puisque de larges plages de la table de hash se trouveront remplies, sans espaces libres. Cela mène à une perte de performance importante.




( steven.pigeon@videotron.ca )