Bonjour,
Afin d'optimiser un des mes algorithmes, il m'est nécessaire de mettre en "cache" le résultat de certains calcules. Afin de pouvoir, reprendre le résultat directement.
Afin de réduire au maximum le set de résulta, il m'est nécessaire d'avoir une fonction de hash particulière. Les spécifications de celle-ci doivent être :
- Pas de collision de hash
- Les rotation circulaires donne le même hash.
Les données générant le hash sont 4 nombres allant de 0 à 22 (ou manquant). Il m'est donc facile de passé à une représentation de string d'une longueur de 4
Toutes autres variations doivent donner un autre hash.Envoyé par Données ayant le même hash
Le sens ayant une importance. (Ici c'est le cas où je n'ai que 2 des nombres.)Envoyé par Données ayant un hash différent
J'ai réalisé une première recherche par rapport à ce problème est j'ai trouvé une réponse intéressante, mais incomplète. (Car, il y a des collisions de hash)
Code java : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class test { static int a; static int b; static int Hash(String s) { int H = 0; if (s.length() > 0) { //any arbitrary coprime numbers a = 61; b = 89; //an array of Euclid-Fermat sequences to generate additional coprimes for each duplicate character occurrence int[] c = new int[0xFF]; for (int i = 1; i < c.length; i++) { c[i] = i + 1; } //for i=0 we need to wrap around to the last character H = NextPair(s.toCharArray()[s.length() - 1], s.toCharArray()[0],c); //for i=1...n we use the previous character for (int i = 1; i < s.length(); i++) { H ^= NextPair(s.toCharArray()[i - 1], s.toCharArray()[i], c); } } return H; } static int NextCoprime(char letter, int[] table ){ return table[letter] = (table[letter] - letter) * table[letter] + letter; } static int NextPair(char letterX, char LetterY, int[] table){ return a * NextCoprime(letterX, table) * letterX + b * LetterY; } public static void main(String[] args) throws FileNotFoundException { System.out.println(Hash("abcd")); System.out.println(Hash("bcda")); System.out.println(Hash("cdab")); System.out.println(Hash("dabc")); // cas problèmatique dans mon set de donnée : System.out.println("problème 1 :"+Hash("mqe ")+" "+Hash("bor")); System.out.println("problème 2 :"+Hash("fql ")+" "+Hash("kfr")); System.out.println("problème 3 :"+Hash("ngi ")+" "+Hash("hpc")); System.out.println("problème 4 :"+Hash("kib ")+" "+Hash("ikb")); } }
Envoyé par Sortie Console
Note : Par variation des valeurs a et b, j'arrive à ne pas avoir de collision dans mon cas particulier. Cependant, avoir une solution propre au problème m'intéresse. (Si je change mon Set je n'ai rien d'assuré)
Cordialement,
Patrick Kolodziejczyk.
source :
http://stackoverflow.com/questions/8...rences-in-java
Edit : Contenu de la taille de mon set : 6280e entrées sans permutation circulaire, 1570 avec (/4)
Je suis passé à un hash plus simple :
Sachant que l'int java est sur 32 bits et que les valeurs sont stockable sur 6 bits (0 à 63).
Code java : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 static int Hash(int a, int b, int c,int d) { return ((a<< 18)+(b<< 12)+(c<< 6)+d); }
Faute de mieux pour le moment.
Partager