hashing dynamiques parfaits et fonctions de hachage universelle - explication s'il vous plaît?

Question

Je suis lecture.Jusqu'à sur les tables de hachage, les fonctions de hachage etc. J'ai été intrigué de lire sur wikipedia sur la façon « dynamique hash parfaite » consiste à utiliser une seconde table de hachage comme la structure de données pour stocker plusieurs valeurs dans un seau particulier.

Là où je me perds cependant, est en ce qui concerne la façon dont une fonction de hachage universelle est sélectionné pour effectuer le hachage pour cette seconde table de hachage. Quelqu'un peut-il expliquer comment cette fonction de hachage universelle est déterminée à partir des valeurs stockées dans le seau? Je me suis vaguement suivant le raisonnement et la logique dans la page « fonction de hachage universelle » wikipedia, mais je suis mal à avoir une intuition à ce sujet. En particulier, comment ces fonctions garantissent pas de conflit? Ou du moins, si elles sont éliminés et un nouveau généré si un choc est détecté, comment pouvons-nous savons que cela peut se faire dans un laps de temps réaliste le cas échéant?

explication du livre Ladybird s'il vous plaît?

Answer 1

moyen de hachage parfait qui prend l'accès en lecture constante de temps, même dans le pire des cas.

Pour insérer des clés, il n'y a aucune garantie les plus défavorables, les limites de temps ne sont vrai en moyenne (ou peut-être amorti).

Pour insérer assez rapidement la deuxième table de hachage de niveau est choisi très grand pour le nombre de touches (k ² ), suffisamment grand pour que les collisions deviennent suffisamment improbable. Ce n'est pas un problème w.r.t. taille parce que le premier hachage de niveau distribue des clés de manière uniforme afin que sur les tables de hachage deuxième niveau moyen sont encore faibles.

La fonction de hachage pour les tables de second niveau sont choisis au hasard dans un ensemble de fonctions de hachage paramétrées.

Answer 2

Que diriez-vous de regarder des conférences MIT? :)
Présentation du MIT aux algorithmes, conférences 7 et 8: hachant