Hash/clé : permutation circulaire et unicité
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
Citation:
Envoyé par Données ayant le même hash
abcd
bcda
cdab
dabc
Toutes autres variations doivent donner un autre hash.
Citation:
Envoyé par Données ayant un hash différent
bc
cb
Le sens ayant une importance. (Ici c'est le cas où je n'ai que 2 des nombres.)
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:
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"));
}
} |
Citation:
Envoyé par Sortie Console
199052
199052
199052
199052
problème 1 :2058518 1917362
problème 2 :1855590 1991362
problème 3 :1279850 1150890
problème 4 :1136810 1266474
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 :
Code:
1
2
3
| static int Hash(int a, int b, int c,int d) {
return ((a<< 18)+(b<< 12)+(c<< 6)+d);
} |
Sachant que l'int java est sur 32 bits et que les valeurs sont stockable sur 6 bits (0 à 63).
Faute de mieux pour le moment.
