Comment hacher un tableau 2-D efficacement (à stocker dans un HashSet)?

Question

J'ai écrit une classe appelée PuzzleBoard qui représente un tableau nxn. Je vais garder plusieurs objets PuzzleBoard dans un HashSet, donc je dois écraser la méthode 'int hashCode()'.

Voici les champs de ma classe:

private int N; 
private int[][] puzzle; 
private int blankCellX; 
private int blankCellY; 
private int cost; 

Quel Eclipse généré automatiquement pour moi WAS:

public int hashCode() { 
    final int prime = 31; 
    int result = 1; 
    result = prime * result + N; 
    result = prime * result + blankCellX; 
    result = prime * result + blankCellY; 
    result = prime * result + cost; 
    result = prime * result + Arrays.hashCode(puzzle); 
    return result; 
} 

Pensant que cette méthode ne prend pas en compte le contenu du 2- d tableau, je l'ai changé en:

public int hashCode() { 
    final int prime = 31; 
    int result = 1; 
    result = prime * result + N; 
    result = prime * result + blankCellX; 
    result = prime * result + blankCellY; 
    result = prime * result + cost; 
    for (int i = 0; i < N; ++i) 
    result = prime * result + Arrays.hashCode(puzzle[i]); 
    return result; 
} 

Cependant, le problème avec cette méthode est que cela prend trop de temps pour compléter: O (N^2) En outre; la variable 'result' est très susceptible de déborder. Maintenant, ma question est, comment puis-je écrire une méthode de hachage efficace qui ne prend pas trop de temps pour terminer. De plus; insérer ou rechercher un objet dans le HashSet devrait être efficace (temps presque constant).

Dans le pire des cas, N sera 10 et le HashSet contiendra ~ 1000 PuzzleBoards.

Pourquoi je fais tout ça? J'applique une solution pour le problème N-Puzzle en utilisant l'algorithme A *. Donc dans une certaine phase de l'algorithme, étant donné le nœud actuel (configuration de la carte), je déplace la cellule vide vers le haut, le bas, la droite ou la gauche pour générer de nouveaux nœuds enfants. Pour cette raison, les configurations de puzzle diffèrent généralement par 1 ou 2 cellules. Je stocke tous les nœuds explorés dans un HashSet.

Merci à l'avance =)

Answer 1

codes de hasch ne pas besoin être unique, il est juste mieux si elles sont. Puisque vous avez un nombre relativement faible d'éléments dans le HashSet (~ 1000), vous pouvez choisir une petite quantité de données appropriées à hacher ensemble. Par exemple, vous n'avez peut-être besoin que de la première ligne de la table 'puzzle', ou peut-être que la variable 'cost' est suffisamment différente pour les différentes instances que vous pouvez utiliser comme une bonne source de différence.

Peu importe si le résultat déborde: tout ce que vous voulez, c'est que des objets différents renvoient différents codes de hachage si possible. La valeur réelle du hachage n'est pas importante.

Answer 2

cette méthode ne prend pas en compte le contenu du tableau 2-d

Vous pouvez également utiliser util.Arrays#deepHashCode().

Cependant, le problème avec cette méthode est qu'il prend trop de temps pour terminer: O (N^2)

Vous ne pouvez pas aller plus vite si vous voulez hacher tous les N^2 ints dedans? Si N est au maximum de 10, qu'en est-il de la notation Big-O? O(n^2) ne signifie pas lent. Je ne pense pas que votre méthode hashCode soit inefficace. L'inefficacité ou certains O(n^2) est très probablement ailleurs ... Toujours si cette méthode est appelée souvent (et que PuzzleBoard est immuable), vous pouvez mettre en cache la valeur hashCode.

La variable 'result' est très susceptible de déborder.

Pas de problème! Les débordements sont définis en Java.

De plus; insérer ou rechercher un objet dans le HashSet devrait être efficace (temps presque constant).

L'insertion est probablement seulement amortie temps constant. Lorsque le HashSet est plein, un nouveau HashSet plus grand sera créé. Tous les éléments sont copiés, tous les hashCodes devront être calculés à nouveau. Essayez de définir une capacité initiale pour le HashSet?

result = prime * result + cost; 

Êtes-vous sûr de vouloir le coût (je suppose qu'il est la profondeur) à inclure dans égaux et hashCode? Deux configurations sont les mêmes, peu importe le nombre de pas qu'il m'a fallu pour y arriver, n'est-ce pas?

~ 1000 PuzzleBoards

Si je me souviens bien, la dernière fois que je résolu ce casse-tête que j'avais beaucoup plus de 1000 configurations.