En lisant le principe du pigeonnier sur Wikipedia, je tombe sur - "les collisions sont inévitables dans une table de hachage car le nombre de clés possibles dépasse le nombre d'indices dans le tableau. Aucun algorithme de hachage, aussi intelligent soit-il, ne peut éviter ces collisions". Mais n'est-ce pas gperf en faisant ça exactement ?
Veuillez m'éclairer.
gperf crée la fonction de hachage et la table de hachage en se basant sur une prédéfini liste de chaînes de caractères.
Il me semble donc que gperf crée des hachages suffisamment longs pour qu'il y ait suffisamment de possibilités.
C'est ce que vous pouvez faire seulement si vous connaissez toutes les clés possibles à l'avance - ce qui est une hypothèse qui n'est pas valable pour la description dans l'entrée de la wikipedia, qui était apparemment liée à une table de hachage "non constante".
Extrait du site web du gperf : "Pour une liste donnée de chaînes de caractères, il produit une fonction de hachage et une table de hachage,..." - ce qui signifie qu'il doit connaître toutes les chaînes de caractères précédemment afin de préparer une fonction qui fonctionne sans collisions.
Les fonctions de hachage habituelles que vous utilisez dans les langages de programmation généraux sont capables de traiter n'importe quelle chaîne de caractères en entrée, l'une après l'autre (la liste n'est pas donnée en une seule fois), et elles peuvent donc produire des collisions.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
