Pourquoi un godet de hachage prend-il un numéro privilégié?
Avoir une fonction de hachage
H (c) = c% n;
Lorsque n prend un numéro composite, l'exemple le plus simple est de prendre 2 ^ n, par exemple, prendre 2 ^ 3 = 8, pour le moment
H (11100 (binaire)) = h (28) = 4
H (10100 (binaire)) = h (20) = 4
À l'heure actuelle, le 4ème morceau de binaire (de droite à gauche) de C "échouera", ce qui signifie que peu importe la valeur prise dans le 4ème morceau de C, cela conduira à la même valeur de H (C). À l'heure actuelle, le quatrième morceau de C ne participe pas du tout au fonctionnement de H (C), donc H (c) ne peut pas pleinement refléter les caractéristiques de C, augmentant les risques de conflit.
Lorsque vous prenez d'autres numéros composites, certains bits de C seront «échoués» à des degrés divers, entraînant des conflits dans certaines applications courantes.
Cependant, la prise de nombres premiers peut essentiellement garantir que chaque bit de C participe à l'opération de H (C), réduisant ainsi le risque de conflit dans les applications communes. ．
(Opinion personnelle: parfois l'efficacité de ne pas prendre de nombres premiers n'est pas trop mal ... mais il est sans aucun doute plus sûr de prendre des nombres premiers ...)
Ce qui précède est ma compréhension
Pour ajouter à cela, cela signifie que dans les applications courantes, certaines données sont souvent similaires. Il est préférable d'utiliser des nombres premiers pour le moment. Par exemple, les données à stocker sont dans un état compressé, comme le stockage d'un tableau décrivant l'état de recherche actuel. À l'heure actuelle, la probabilité de hachage sans nombres premiers est relativement élevée.
S'il s'agit d'un entier distribué au hasard, le module de hachage sera le même tant qu'il est pris suffisamment grand, mais c'est évidemment hors de l'application pratique.
Ce que vous avez dit est une situation spéciale, car lorsqu'un nombre primaire relativement petit est sélectionné, lorsque le grand nombre de prime N est sélectionné, il ne peut échouer que dans un certain nombre du système à n chiffon. Combinée aux caractéristiques du système informatique, la représentation à n chiffon n'est souvent pas critique, tandis que le système à 2 ^ n chiffon couramment utilisé est plus critique, donc les conflits peuvent être évités.
En fait, j'ai utilisé quelques grands nombres pour le tester pour stocker une matrice d'adjacence comprimée en binaire. Lorsque le module est suffisamment grand, même le nombre composite peut avoir un effet très proche du nombre privilégié, mais dans certaines (plusieurs dizaines) de nombres composites, l'efficacité sera gravement réduite, donc les nombres premiers sont relativement sûrs.
Vous pourriez aussi bien faire vos propres expériences, ne pas choisir des entiers aléatoires, mais considérer certaines applications courantes, utiliser des nombres premiers et des nombres composites pour tester, examinant principalement le facteur de chargement moyen, et la conclusion que vous obtenez peut être la même que les mien: les nombres composites sont également bons au plus du temps, mais l'effet est surprenant dans certains numéros composites, et presque tous les nombres premiers ont de bons résultats.
Je pense personnellement que dans un sens plus général, si vous ne prenez pas de nombres premiers, il y aura un certain danger. Le danger se produit lorsque le nombre non prison m = x * y est supposé être sélectionné, et si la clé du hachage est liée à ce diviseur x, il sera misérable. Dans le pire des cas, tous supposent que ce sont des multiples de x, alors vous pouvez imaginer que le résultat du hachage est: 1 ~ y, pas 1 ~ m. Cependant, si la taille du seau est sélectionnée comme numéro premier, il n'y aura pas de problème.
Merci d'avoir lu, j'espère que cela peut vous aider. Merci pour votre soutien à ce site!