Expérimentation avec hachage coucou

Suppression impatiente

Notez que dans le code pour suppression impatiente, on réinsère les éléments après la case vidée (et non pas à partir de la première case identifiée à l’indice i=h(x).) Voir correction en Ligne S1 dans l’énoncé: devoir4.

Quant à la date de remise, vous ne serez pas pénalisé si vous soumettez avant le 17 novembre 20:15 (donc, avec un délai ≤ 72h).

Exemple avec hachage coucou

Pour illustrer ce qu’on veut faire en Devoir 4, voici mon expérimentation avec hachage coucou. C’est une structure très élégante, avec O(1) temps au pire pour recherche et suppression. Rasmus Pagh donne une bonne présentation en ligne sur l’idée.

  1. J’ai encodé la méthode dans la classe koekoeke.CuckooHashingSet:https://github.com/csurosm/Koekoeke/blob/master/src/koekoeke/CuckooHashingSet.java. La classe implémente l’interface de java.util.Set.
  2. J’ai modifié la source de SetTester pour utiliser CuckooHashingSet. En Ligne 480:
    Set<Object> trythis =  new koekoeke.CuckooHashingSet(); 
    
  3. J’ai lancé l’exécution après compilation dans la ligne de commande, 12 fois par taille testée:
    % bash -c 'for N in 65536 131072 262144 524288 1048576 2097152 4194304; do for rep in 1 2 3 4 5 6 7 8 9 10 11 12; do  java -Xmx2G -cp IFT2015-A16.jar SetTester ${N}; done; done' > timings.log 
    
  4. Afin d’importer les données dans un logiciel de feuille de calcul (Microsoft Excel ou Google Sheets), j’ai enlevé les lignes de remarques. (Dans la feuille, j’ai trié les rangées par les colonnes `Phase’ et ‘size’.)
    % grep -v '#' timings.log > timings.txt      
    
  5. J’ai répeté la procédure pour HashSet. Voici la combinaison des deux fichiers (avec 25 répétitions au lieu de 12):  Google spreadsheet. (Temps amorti rapporté dans phase `exec’, usage de mémoire dans phase `final’.)

cuckoo-timingscuckoo-memory