Pourquoi la taille de 127 (premier) mieux que 128 pour une table de hachage?

Question

En supposant simple et uniforme de hachage, cela étant, toute valeur donnée est aussi comme de hachage dans l'une des fentes de la table de hachage. Pourquoi est-il préférable d'utiliser un tableau de taille 127 et 128 pas? Je ne comprends vraiment pas quel est le problème avec la puissance de 2 numéros. Ou comment il est en fait aucune différence.

Lors de l'utilisation de la méthode de répartition, nous avons l'habitude d'éviter certaines valeurs de m (la taille de la table). Par exemple, m ne doit pas être une puissance de 2, depuis si m = 2^p , alors h(k) est la p la plus faible de bits d'ordre k.

Supposons que les éléments qui sont seulement entre 1 et 10000 et j'ai choisi la taille de la table que 128. Comment peut-127-être mieux? Donc, 128 est de 2^6 (1000000) et 127 est 0111111. Quelle différence cela fait-il? Tous les nombres (quand haché) sont toujours en cours à la p plus faible de bits de k 127 trop. Ai-je quelque chose de mal?

Je suis à la recherche pour certains des exemples que je ne comprends vraiment pas pourquoi est-ce mauvais pas. Merci beaucoup à l'avance!

PS: je suis conscient de: Table de hachage: pourquoi la taille devrait être le premier?

Answer 1

Tous les nombres (quand haché) sont toujours en cours à la p plus faible de bits de k 127 trop.

C'est faux (ou j'ai mal compris..). k % 127 dépend de tous les bits de k. k % 128 ne dépend que de la 7 plus bas bits.

---

EDIT:

Si vous avez une distribution parfaite entre 1 et 10 000. 10,000 % 127 et 10,000 % 128 à la fois à cet dans une excellente distribution plus petits. Tous les compartiments contiennent de 10 000 /128 = 78 (79).

Si vous avez une répartition entre 1 et 10 000, qu'il est biaisé, parce que {x, 2x, 3x, ..} se produire plus souvent. Puis un premier taille donnera une bien meilleure distribution, comme indiqué dans cette réponse. (Sauf si x est exactement ce que le premier de la taille.)

Ainsi, en coupant le haut de bits (en utilisant une taille de 128) n'est pas un problème que ce soit, si la distribution dans les bits de poids faible est assez bon. Mais, avec des données réelles et véritables mal conçu fonctions de hachage, vous aurez besoin de ces bits élevés.

Answer 2

Tout d'abord, il n'est pas sur la sélection d'un nombre premier. Pour votre exemple, si vous savez que votre ensemble de données sera dans la gamme de 1 à 10 000, la cueillette 127 ou 128 ne fera pas une différence de bc, c'est un mauvais choix de conception.

Au contraire, il est préférable de choisir un VRAIMENT grand comme 3967 pour votre exemple, afin que chaque a son propre paire clé/valeur. Vous voulez juste pour limiter les collisions. La cueillette de 127 ou 128 pour votre exemple ne fera pas une différence bc toutes les 127/128 seaux seront uniformément rempli (ce qui est mauvais et va dégrader l'insertion et la recherche d'exécution O(1) O(n)) par opposition à 3967 (qui permettra de préserver le O(1) temps d'exécution)

EDIT #4

La conception de la "fonction de hachage" est un peu de magie noire. Il peut être fortement influencé par les données destinées à être stockées dans le le hachage basée sur la structure de données, de sorte que le discussion sur un bon hachage la fonction peut souvent s'aventurer dans un discussion à propos des entrées spécifiques.

Pourquoi les nombres premiers sont "privilégiées", a à envisager un "adversaire" de l'analyse, c'est-à supposer que j'ai conçu un général le hachage basée sur la structure des données, la façon dont serait-il effectuer compte tenu de la pire entrée à partir d'un adversaire. Puisque les performances est dictée par le malaxage des collisions de la la question devient quoi le hachage l'utilisation qui minimise la collision dans la la pire condition. Une telle condition est lorsque l'entrée sont toujours des nombres divisible par certaines entier, dire 4. Si vous utilisez N = 128 ensuite n'importe quel nombre divisible par 4 mod 128 est encore divisible par 4, ce qui veut dire qu' seaux de 4, 8, 12, ... sont toujours utilisés, ce qui a 25% de l'utilisation de la structure de données. Les nombres premiers efficacement réduit la probabilité d'un tel le scénario se réalise, avec les numéros > N.

Answer 3

Nick est juste qu'en général, la table de hachage de taille n'a pas d'importance. Toutefois, dans le cas particulier où, en abordant avec double hachage est utilisé (dans laquelle l'intervalle entre les sondes est calculée par une autre fonction de hachage, puis un nombre premier de taille de la table de hachage est préférable de s'assurer que toutes les entrées de la table de hachage sont disponibles pour un élément nouveau (comme Corkscreewe mentionné.)

Answer 4

Si vous avez une parfaite fonction de hachage qui a une distribution uniforme, alors qu'il n'a pas d'importance.

Answer 5

Wikipedia a fait un bon résumé de ce:

http://en.wikipedia.org/wiki/Hash_table

Ils soulignent que certaines fonctions de hachage sont conçus pour fonctionner UNIQUEMENT avec des nombres premiers. Cet article explique pourquoi les puissances de deux sont mauvais:

http://www.concentric.net/~Ttwang/tech/primehash.htm