Est-ce une sortie de fonction de hachage doivent être limitée inférieur au nombre de seaux?

Question

Je lisais l'interview de cette personne « dans une entreprise de recherche bien connu ».

http: //asserttrue.blogspot .com / 2009/05 / one-of-difficile-emploi entretien-questions.html

Il a posé une question qui l'a amené à mettre en œuvre une table de hachage. Il a dit ce qui suit:

HASH = INITIAL_VALUE;
FOR EACH ( CHAR IN WORD ) {
HASH *= MAGIC_NUMBER
HASH ^= CHAR
HASH %= BOUNDS
}
RETURN HASH

  

Je lui ai expliqué que le tableau de table de hachage   longueur doit être premier, et les BOUNDS   nombre est inférieur à la longueur de la table,   mais coprime à la longueur de la table.

Pourquoi le nombre BOUNDS devrait être inférieur au nombre de seaux? Que signifie être à la longueur coprime de table faire? Est-il pas censé être au BOUNDS premiers entre eux?

Answer 1

Je hasarde qu'il est complètement faux. BOUNDS devrait être le nombre de seaux ou les dernières seaux vont être sous-utilisés.

En outre, la délimitation de la sortie au nombre de godets doit être en dehors de la fonction de hachage. Ceci est un détail de mise en œuvre de cette table de hachage particulière. Vous pourriez avoir une très grande table en utilisant beaucoup de seaux et un autre en utilisant quelques-uns. Les deux doivent partager la même string-> fonction de hachage

En outre, si vous lisez la page que vous avez accédé à il est très intéressant. Je l'ai mis en œuvre sa table de hachage comme quelque chose comme 10.000 seaux - Pour ceux qui ont pas lu, l'article suggère ~ 4000000000 seaux pour stocker ou 1.000.000 mots si possible. Pour les collisions, chaque godet a un vecteur de structures de mots, chacun de ceux qui contiennent un nombre, une chaîne et un hachage plaintext (unique dans le seau). Cela utilise beaucoup moins de mémoire et mieux travailler avec les caches modernes depuis votre poste de travail serait beaucoup plus faible.

Pour réduire davantage l'utilisation de la mémoire, vous pouvez expérimenter avec des mots du hachage culling pendant la phase d'entrée qui ressemblent à elles sont en dessous du haut 100 000 en fonction du nombre actuel.

Answer 2

J'ai déjà interrogé pour un emploi dans une entreprise de recherche bien connu. Je suis arrivé exactement la même question. J'ai essayé de s'y attaquer en utilisant la table de hachage.

Une chose que j'appris de cette interview était que dans une entreprise de recherche bien connu, vous ne proposez pas hash comme solutions. Vous utilisez une structure arborescente que vous voulez, mais vous utilisez toujours la structure ordonnée, pas la table de hachage.

Answer 3

Un arbre suffixe explicite simple serait que le pire des cas peut-être utiliser 500k mémoire (avec une mise en œuvre modérément efficace, 4 octets codages de caractères, et les mots anglais relativement longues qui ont un chevauchement minimal) pour faire la même chose.

Je pense que le gars dans l'article lui-même plus malin.