Utilisation de la comparaison alternative dans HashSet

Question

Je suis tombé sur ce problème lors de la création d'un HashSet [Array [Byte]] à utiliser dans une sorte de HatTrie.

Apparemment, la méthode standard equals() sur les tableaux vérifie l'identité. Comment puis-je fournir au HashSet un comparateur alternatif qui utilise .deepEquals() pour vérifier si un élément est contenu dans l'ensemble?

Fondamentalement, je veux que ce test réussisse:

describe ("A HashSet of Byte Array") {  

    it("must contain arrays that are equivalent to one that has been added") { 
     val set = new HashSet[Array[Byte]]() 
     set += "ab".getBytes("UTF-8") 
     set must contain ("ab".getBytes("UTF-8"))   
    } 
} 

Je ne peux pas envelopper réalistement Array [Byte] dans un autre objet, car il y a beaucoup d'entre eux. À court d'écrire une nouvelle implémentation de HashSet à cet effet, y a-t-il quelque chose que je puisse faire?

Answer 1

Les structures de données convertibles, telles que les tableaux, sont contre-indiquées pour une utilisation dans les endroits où le code de hachage est utilisé. En effet, la structure des données peut changer, modifiant ainsi le code de hachage des données, rendant ainsi l'accès aux données inexact. Par exemple, disons que j'ai un arbre binaire pour stocker des éléments en fonction de leur code de hachage. Si le hachage est pair, je stocke les données sur le côté gauche, si impair sur le côté droit. Ensuite, je divise le hachage par deux, et répète le processus jusqu'à ce que le hachage soit 0, à quel point je stocke les données dans le nœud. Maintenant, j'utilise cette structure comme base pour HashSet, puis je stocke un tableau dessus. Le tableau a un code de hachage pair, donc il va à la gauche de l'arbre. Ignorons sa position exacte.

Plus tard, je change le tableau, puis le recherche sur l'ensemble. Maintenant, le code de hachage est impair, et je vais regarder sur le côté droit de l'arbre, et je ne peux donc pas le trouver, même s'il est stocké dans l'arbre - juste de l'autre côté. Par conséquent, n'utilisez pas de tableaux avec des collections basées sur le hachage. Ce qui ne répond pas à votre question, bien sûr. En ce qui concerne votre question, vous devez sous-classer HashSet, puis remplacer la méthode equals. Je ne sais pas si HashSet est final ou descendant d'une classe scellée, donc je ne sais pas si c'est viable. Une autre option consisterait à créer une méthode de comparaison alternative - non nommée equals ou "==", basée spécifiquement sur deepEquals, puis en utilisant la méthode Pimp My Class pour l'ajouter à HashSet.

Modifier

Je l'ai HashSet sous-classe moyenne, mais je ne l'ai pas accordé suffisamment d'attention à la question. Je pensais que vous étiez en train de comparer l'ensemble du HashSet, au lieu d'utiliser simplement le contenu. Vous pourriez faire ceci:

class MyHashSet[A] extends scala.collection.mutable.HashSet[A] { 
    override def contains(elem: A): Boolean = elem match { 
    case arr : Array[_] => this.elements exists (arr deepEquals _) 
    case _ => super.contains(elem) 
    } 
} 

Ceci ne fonctionne pas réellement ici, car le premier cas n'est pas suivi. Je suis vraiment perdu ici, comme de simples tests sur REPL semble indiquer qu'il devrait fonctionner. Je pense que ça a peut-être quelque chose à voir avec la boxe, mais je ne suis pas très clair sur quoi - ou je le ferais fonctionner. :-)