Ces deux nombres sont des nombres premiers suffisamment grands. Veuillez lire l' article sur la table de hachage sur Wikipedia pour plus d'informations.
Boris Pavlović
Réponses:
140
1231 et 1237 ne sont que deux nombres premiers arbitraires (suffisamment grands) . Tout autre grand nombre premier ferait l'affaire.
Pourquoi des nombres premiers?
Supposons pendant une seconde que nous ayons choisi des nombres composites (non premiers), disons 1000 et 2000. Lors de l'insertion de booléens dans une table de hachage, vrai et faux iraient dans le compartiment 1000 % Nresp 2000 % N(où Nest le nombre de compartiments).
Maintenant remarquez que
1000 % 8 même seau que 2000 % 8
1000 % 10 même seau que 2000 % 10
1000 % 20 même seau que 2000 % 20
....
en d'autres termes, cela conduirait à de nombreuses collisions .
C'est parce que la factorisation de 1000 (2 3 , 5 3 ) et la factorisation de 2000 (2 4 , 5 3 ) ont autant de facteurs communs. Ainsi, les nombres premiers sont choisis, car il est peu probable qu'ils aient des facteurs communs avec la taille du seau.
Pourquoi de grands nombres premiers. Est-ce que 2 et 3 ne feraient pas?
Lors du calcul des codes de hachage pour les objets composites, il est courant d'ajouter les codes de hachage pour les composants. Si des valeurs trop petites sont utilisées dans un ensemble de hachage avec un grand nombre de compartiments, il y a un risque de se retrouver avec une distribution inégale des objets.
Les collisions sont-elles importantes? Les booléens ont juste deux valeurs différentes de toute façon?
Les cartes peuvent contenir des booléens avec d'autres objets. De plus, comme l'a souligné Drunix, une manière courante de créer des fonctions de hachage d'objets composites consiste à réutiliser les implémentations de code de hachage des sous-composants, auquel cas il est bon de renvoyer de grands nombres premiers.
Je suppose que ceux-ci sont suffisamment grands. Pour obtenir un pgcd supérieur à 1, vous avez besoin d'au moins des 2*1231 = 2462seaux. Les collisions sont-elles un problème dans une telle situation?
aioobe
2
Il est intéressant de noter qu'ils ne sont pas vraiment "assez grands" compte tenu de ce qui peut tenir dans un int. Je suppose qu'ils sont juste assez grands pour bien fonctionner avec la table de hachage JDK, mais encore assez petits pour minimiser les coûts de calcul.
Thilo
2
Oui, cela m'a aussi frappé qu'ils ne soient pas si gros. Mais croyez-vous qu'il y a un coût plus élevé avec des nombres premiers plus importants?
aioobe
3
@Thilo vous auriez besoin d'un multiple de 1231 * 1237 = 1522747 seaux avant qu'ils n'entrent en collision, c'est assez grand
monstre à cliquet
2
Je dirais que conduire à des collisions avec le nombre de seaux n'est pas vraiment un problème avec booléen, mais plutôt la construction courante sur la façon dont nous obtenons le hascode d'un objet composite, à savoir en multipliant les hashcodes des composants avec certaines constantes et en les additionnant.
Drunix
2
En plus de tout ce qui est dit ci-dessus, il peut également s'agir d'un petit œuf de Pâques des développeurs:
vrai: 1231 => 1 + 2 + 3 + 1 = 7
7 - est un chiffre porte-bonheur dans les traditions européennes;
faux: 1237 => 1 + 2 + 3 + 7 = 13
13 (aka la douzaine du diable) - nombre malchanceux.
Réponses:
1231 et 1237 ne sont que deux nombres premiers arbitraires (suffisamment grands) . Tout autre grand nombre premier ferait l'affaire.
Pourquoi des nombres premiers?
Supposons pendant une seconde que nous ayons choisi des nombres composites (non premiers), disons 1000 et 2000. Lors de l'insertion de booléens dans une table de hachage, vrai et faux iraient dans le compartiment
1000 % Nresp2000 % N(oùNest le nombre de compartiments).Maintenant remarquez que
1000 % 8même seau que2000 % 81000 % 10même seau que2000 % 101000 % 20même seau que2000 % 20en d'autres termes, cela conduirait à de nombreuses collisions .
C'est parce que la factorisation de 1000 (2 3 , 5 3 ) et la factorisation de 2000 (2 4 , 5 3 ) ont autant de facteurs communs. Ainsi, les nombres premiers sont choisis, car il est peu probable qu'ils aient des facteurs communs avec la taille du seau.
Pourquoi de grands nombres premiers. Est-ce que 2 et 3 ne feraient pas?
Lors du calcul des codes de hachage pour les objets composites, il est courant d'ajouter les codes de hachage pour les composants. Si des valeurs trop petites sont utilisées dans un ensemble de hachage avec un grand nombre de compartiments, il y a un risque de se retrouver avec une distribution inégale des objets.
Les collisions sont-elles importantes? Les booléens ont juste deux valeurs différentes de toute façon?
Les cartes peuvent contenir des booléens avec d'autres objets. De plus, comme l'a souligné Drunix, une manière courante de créer des fonctions de hachage d'objets composites consiste à réutiliser les implémentations de code de hachage des sous-composants, auquel cas il est bon de renvoyer de grands nombres premiers.
Questions connexes:
la source
2*1231 = 2462seaux. Les collisions sont-elles un problème dans une telle situation?En plus de tout ce qui est dit ci-dessus, il peut également s'agir d'un petit œuf de Pâques des développeurs:
7 - est un chiffre porte-bonheur dans les traditions européennes;
13 (aka la douzaine du diable) - nombre malchanceux.
la source