Je veux comparer b nombres de base-b de b chiffres chacun pour déterminer lesquels sont les mêmes, en utilisant une table de hachage. Si j'utilise une fonction de hachage modulaire, devrais-je utiliser h (a) = un mod (b) ou h (a) = un mod (b-1)? Je ne suis pas sûr de savoir si elles sont appropriées ou non.Comparer des nombres en utilisant une fonction de hachage modulaire?
Vous avez donc b chiffres dans la gamme 0 ... b^b - 1 (par exemple 10 nombres dans la gamme 0 ... 9999999999).
Si vous souhaitez garantir que la fonction de hachage est sans collision, vous ne pouvez pas utiliser mod. Si vous utilisez par exemple a mod 10, puis 31 et 56465421 tous les deux obtiennent un hachage de 1 et entrent en collision, et cela se produit pour chaque mod ci-dessous 10000000000. Par conséquent, vous ne pouvez réduire la probabilité de collisions de hachage que dans les cas suivants:
Et la plus petite valeur mod avec une chance d'éviter les collisions est b (mais très probablement, vous rencontrerez alors des collisions). Sans faire des calculs de probabilité appropriés, je voudrais quelque chose comme mod b*b, en prenant effectivement les deux derniers chiffres.
** mod b **. Supposons que b = 5, si vous avez 5 nombres, 0 serait égal à 4 si votre mod était b-1, ce qui n'est pas vrai dans la base 5 – Daniel