Comment puis-je obtenir un identifiant unique pour une baie 2d?

Question

Je veux un moyen d'obtenir un identifiant unique pour un tableau 2d. par exemple:

Tableau A:

[4,2,3] 
[4,5,6] 
[7,8,9] 

Tableau B:

[9,2,3] 
[4,5,6] 
[1,1,9] 

Je veux une fonction de savoir que <> B sans enregistrer l'ensemble A et B. tout

Merci d'avance

Answer 1

Eh bien, pour obtenir une garantie de unique valeur, vous aura effectivement d'enregistrer le contenu complet de la matrice. Vous pouvez utiliser un hachage qui vous dira si un tableau est probablement le même que l'autre, mais vous ne pouvez pas obtenir l'unicité sans avoir une transformation sans perte.

À titre d'exemple d'une simple fonction de hachage:

int hash = 17; 
for (int i = 0; i < 3; i++) { 
    for (int j = 0; j < 3; j++) { 
    hash = hash * 31 + array[i, j]; 
    } 
} 
return hash; 

Maintenant, deux tableaux différents seront très probablement un hachage différent - mais ils ne pourraient pas.

Combien d'espace êtes-vous prêt à dépenser pour l'ID, et quelle est la taille de chaque valeur dans le tableau? Plus vous aurez d'informations à mettre dans l'ID, moins vous aurez de faux positifs ... jusqu'à ce que vous arriviez à l'étape où l'ID est aussi grand que le tableau, à quel point vous pouvez vous assurer que Bien sûr, il n'y aura pas de faux positifs.

Answer 2

public static long computeHash(int[][] array) { 

     final int p = 16777619; 
     long hash = 2166136261l; 

     for(int i = 0; i< array.length; i++) { 
      for(int j = 0; j < array[i].length; j++) { 
       hash = (hash^array[i][j]^(i * j)) * p; 
      } 
     } 

     hash += hash << 13; 
     hash ^= hash >> 7; 
     hash += hash << 3; 
     hash ^= hash >> 17; 
     hash += hash << 5; 

     return hash; 

    } 

A propos de la fonction de hachage: here