Hash universel avec des collisions

Question

J'ai un devoir mais je ne sais vraiment pas par où commencer. Ecrivez un programme en Java qui implémente les deux familles de fonctions de hachage universelles que nous avons vues en classe aujourd'hui. Les deux familles de fonctions dépendent de divers paramètres, de sorte que Java doit utiliser deux classes dont les constructures reçoivent les paramètres appropriés et C doit créer une sorte de structure qui contient un pointeur vers une fonction. Pour tester leurs implémentations, utilisez les jeux suivants: U = f0; 1; 2; ::: 10008g et D = f0; 1; 2; ::: 2052g. Ecrire une application au hasard choisir une fonction de chaque type et insérer U 500 nombre aléatoire dans un tableau contenant les adresses de D. La sortie de votre programme devrait être le nombre de collisions obtenues lors des insertions en utilisant la politique des buckets pour résoudre les collisions.

Pouvez-vous s'il vous plaît me dire comment puis-je commencer ou que dois-je mettre en œuvre pour cela. Merci

Answer 1

1. Créer les deux fonctions de hachage que vous avez donné
2. Générez et insérez dans votre table de hachage, 500 numéros de type U quelle carte à une adresse de type D. L'insertion doit également choisir au hasard un hachage fonction à utiliser pour l'insertion
3. Itérez sur votre table de hachage et comptez le nombre de compartiments contenant plus d'un élément de type U