Hashtables (dictionnaire etc) avec des touches entières

Je suis curieux de savoir ce que je fais depuis quelques jours ... n'hésitez pas à abattre l'une de mes suppositions.Hashtables (dictionnaire etc) avec des touches entières

Nous utilisons un dictionnaire avec des clés entières. Je suppose que la valeur de la clé dans ce cas est utilisée directement comme le hachage. Est-ce que cela signifie (si les clés sont groupées sur une petite plage) que la distribution de la clé de hachage (identique à la clé elle-même, n'est-ce pas?) Sera aussi petite, et donc un mauvais choix pour une hashtable?

Serait-il préférable de fournir un IEqualityComparer qui a fait quelque chose d'intelligent avec les nombres premiers et les mathématiques modulo pour calculer un hachage mieux distribué?

Source

2009-09-07 spender

dépend de la distribution de vos clés entières. Les clés sont déjà modulo'ed par un nombre premier lors du calcul du seau de hachage. –

Pourquoi supposer que le code de hachage est le même que la valeur entière? Essaye-le! – SteveD

Le code de hachage est identique à la valeur entière. – spender

Il n'est pas utilisé directement en ce que le dictionnaire demandera toujours la clé de son hachage - mais la valeur de hachage d'un Int32est juste la valeur, de sorte que le sens de votre question est pertinente, oui. Je crois que le fonctionnement du dictionnaire .NET ne dépend pas de la distribution uniforme des valeurs de hachage. Il faut hash % bucketCount où bucketCount est toujours premier. (C'est de mémoire cependant - je pourrais me tromper.)

Vous pourriez toujours vous retrouver avec un ensemble inefficace de touches, bien sûr, si elles sont espacées par le nombre de seaux. Ce sera toujours le cas cependant - une table de hachage ne serait jamais O (1) pour toutes les clés si elles avaient des valeurs de hachage uniques et la table a maintenu un ensemble de seaux pour chaque hachage possible :) En réalité, il a tendance à ne pas être un problème. Si vous savez qu'il est sera être d'un problème, alors oui, une coutume IEqualityComparer<T> pourrait aider.

Source

2009-09-07 08:57:55

Juste vérifié avec le réflecteur ... vous avez raison avec hash% bucketcount. Sachant cela, tout se met en place. Merci Jon. – spender

En supposant que vous utilisez une implémentation de table de hachage de bibliothèque standard, la clé est pas le hachage, même si la clé est un entier, exactement pour la raison que vous signalez.

Donc, même si votre logique concernant les distributions de hachage est correcte, votre hypothèse initiale selon laquelle les clés entières signifieraient que hashes = keys ne l'est probablement pas.

Si je me trompe re: .NET alors oh bien; c'est plus une réponse généralisée. :)

Source

2009-09-07 08:58:25 Amber

Je pense qu'il est assez commun que le hachage d'un type numérique soit simplement la valeur, en supposant qu'il se situe dans la plage de hachage. –

Un problème potentiel que vous rencontrez dans ce cas est avec des motifs dans les séquences de nombres - si vous obtenez malchanceux avec la largeur du motif étant un multiple de votre bucketCount, vous rencontrez des problèmes. – Amber

Exactement comme mon poste mentionne ... mais * tout algorithme de hachage peut se terminer avec ce problème si vous êtes malchanceux. –

Avant de faire quelque chose d'intelligent je voudrais tester la vitesse de celui-ci, et voir si elle vous convient. Si ce n'est pas le cas, essayez la chose intelligente. Mais je m'attendrais à ce qu'il soit préférable de le laisser tranquille. il est plus important que les hachages ne se heurtent pas, et tant que cela se produira, la vie ira bien.

Source

2009-09-07 09:02:15

Hashtables (dictionnaire etc) avec des touches entières

Répondre

Questions connexes