Fonction de hashageRésolu

Question

Bonjour, 

Je cherche à créer une fonction de hashage dans la logique suivante.

En entrée on a par exemple:

1 2 2 3 4 5 5 5 14 19 80 80 2 2 2 80 80

Qui donnerait en sortie :

1 2 3 4 5 6 7 8 9 8

La logique est qu'on parcoure la liste d'entier séparée par des espaces et que pour chaque répétition identiques , on attribut un entier.

Au dessus les valeurs se transforment ainsi :

1 = 1
2 2 = 2
3 = 3
4 = 4
5 5 5 = 5
14 = 6
19 = 7
80 80 = 8
2 2 2 = 9 (on change bien les trois successions de "2" et non pas les deux premiers)
80 80 = 8 (déjà indexé auparavant, on garde le même index)

Auriez vous une idée de la fonction que je pourrais utiliser et comment la coder s'il vous plait ?

Merci d'avance :)

KX · Answer

Bonjour,

Une fonction de hashage ne se construit pas à partir d'un cas particulier, ça n'a pas de sens et peu d'intérêt...

Exemple (absurde volontairement)

int hash(int n) {
    switch (n) {
        case 1 : return 1;
        case 2 : return 2;
        case 3 : return 3;
        case 4 : return 4;
        case 5 : return 5;
        case 14 : return 6;
        case 19 : return 7;
        case 80 : return 8;
        default: return n%100;
    }
}
C'est bien une fonction de hachage et elle respecte tes contraintes...

cevug5 · Answer

Bonjour KX,

Merci pour ta réponse. Mais je ne vois pas pourquoi ce serait un cas particulier , si j'ai une très longue liste d'entiers, je ne vois pas d'autre façon de le faire ...

KX · Answer

Une fonction de hachage doit être définie pour sa facilité de calcule et ses propriétés statistiques afin d'éviter au maximum les collisions (cas où deux valeurs différentes sont hachée de la même manière), pas pour matcher un cas d'utilisation défini "arbitrairement" au départ...

Voici par exemple, la fonction de hachage qu'utilise Java pour un tableau d'entiers.

    public static int hashCode(int a[]) {
        if (a == null)
            return 0;

int result = 1;
        for (int element : a)
            result = 31 * result + element;

return result;
    }

cevug5 · Answer

Ok je vois, faut que je trouve une autre façon d'obtenir le résultat alors.

Fonction de hashage

4 réponses

Votre réponse

Discussions similaires