Discussion :

[kolodz]

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

abcd
bcda
cdab
dabc

Toutes autres variations doivent donner un autre hash.

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 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"));
		}
}

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 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);
	}

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.