Problème de comparaison de hash

Question

J'ai la liste d'un objet qui est appelé règle dans notre cas, cet objet est une liste de champs pour lesquels je dois faire une comparaison de hash, car nous ne pouvons pas dupliquer la règle dans le système .

i.e. Disons que j'ai deux règles R1 et R2 avec des champs A & B.

Maintenant, si les valeurs de A & B dans R1 sont respectivement 7 et 2.

Et dans R2, il est 3 et 4, respectivement, alors le processus j'ai utilisé pour vérifier la fausseté de règles dans le système qui est la comparaison de hashcode échoue

la méthode que je l'ai utilisé est

for(Rule rule : rules){ 
changeableAttrCode=0; 

fieldCounter=1; 

attributes = rule.getAttributes(); 

for(RuleField ruleField : attributes){ 

changeableAttrCode = changeableAttrCode + (fieldCounter * ruleField.getValue().hashCode()); 

fieldCounter++; 

} 
parameters = rule.getParameters(); 

for(RuleField ruleField : parameters){ 

changeableAttrCode = changeableAttrCode + (fieldCounter * ruleField.getValue().hashCode()); 

fieldCounter++; 

} 

changeableAttrCodes.add(changeableAttrCode); 

ici changeableAttrCodes où nous stockons le hashcode de toutes les règles.

peut donc s'il vous plaît me suggérer une meilleure méthode afin que ce genre de problème ne se pose pas à l'avenir ainsi que la duplicité des règles dans le système peut être vu.

Merci à l'avance

Answer 1

• Mettre en œuvre hashCode et equals dans la classe Règle.
• La mise en œuvre de equals doit comparer ses valeurs.

Ensuite, utilisez un HashSet<Rule> et demander if(mySet.contains(newRule))

HashSet + équivaut à la mise en œuvre résout le problème de la non-unicité du hachage. Il utilise le hachage pour la classification et la vitesse, mais il utilise égal à la fin pour s'assurer que deux règles avec le même hachage sont la même règle ou non.

Plus d'informations sur hash: si vous voulez le faire à la main, utilisez le nombre premier sudggestion, et passez en revue le code JDK pour les hashcodes string. Si vous voulez faire une implémentation propre, essayez de récupérer le hashcode des éléments, créez une sorte de tableau d'ints et utilisez Arrays.hashCode (int []) pour obtenir un hashcode pour la combinaison de ces éléments.

Answer 2

Mise à jour votre algorithme de hachage ne produit pas une bonne diffusion des valeurs de hachage - il donne la même valeur (7, 2) et (3, 4):

1 * 7 + 2 * 2 = 11 
1 * 3 + 2 * 4 = 11 

Il donnerait également la même valeur pour (11, 0), (-1, 6), ... et on peut trivialement constituer un nombre infini de classes d'équivalence similaires basées sur votre algorithme actuel.

Bien sûr, vous ne pouvez pas éviter les collisions - si vous avez assez d'instances, la collision est inévitable. Cependant, vous devriez viser à minimiser les risques de collision. Les bons algorithmes de hachage s'efforcent de répartir les valeurs de hachage de manière égale sur un large éventail de valeurs. Une façon typique d'y parvenir est de générer la valeur de hachage pour un objet contenant n des champs indépendants en tant que n - nombre de chiffres avec une base suffisamment grande pour contenir les différentes valeurs de hachage pour les champs individuels.

Dans votre cas, au lieu de multiplier par fieldCounter, vous devez multiplier par une constante principale, par ex. 31 (ce serait la base de votre numéro). Et ajoutez une autre constante principale au résultat, par ex. 17. Cela vous donne une meilleure répartition des valeurs de hachage. (Bien sûr, la base concrète dépend de quelles valeurs peuvent vos champs prendre -. Je n'ai pas d'information à ce sujet)

Aussi, si vous implémentez hashCode, il est vivement conseillé de mettre en œuvre equals aussi bien - et en fait, vous devez utiliser le dernier à tester pour l'égalité. Il s'agit d'un article sur implementing hashCode.

Answer 3

Je ne comprends pas ce que vous essayez de faire ici. Avec la plupart des scénarios de fonction de hachage, la collision est inévitable, car il y a beaucoup plus d'objets à hacher que de valeurs de hachage possibles (c'est un principe de pigeonhole).

Il est généralement le cas que deux objets différents peuvent avoir la même valeur de hachage. Vous ne pouvez pas compter uniquement sur les fonctions de hachage pour éliminer les doublons.

Certaines fonctions de hachage sont meilleures que d'autres pour minimiser les collisions, mais elles sont toujours inévitables.

---

Cela dit, il existe quelques directives simples qui donnent généralement une bonne fonction de hachage. Joshua Bloch donne ce qui suit dans son livre Effective Java 2e édition:

• magasin une valeur constante non nulle, disons 17, dans un appelé result variables int.
• Compute un int hashcode c pour chaque champ:
  • Si le champ est un boolean, calculer (f ? 1 : 0)
  • Si le champ est un byte, char, short, int, calculer (int) f
  • Si le champ est un long, calculer (int) (f^(f >>> 32))
  • Si le champ est float, calculer Float.floatToIntBits(f)
  • Si le champ est double, calculez Double.doubleToLongBits(f), puis hachez le résultat long comme ci-dessus.
  • Si le champ est une référence d'objet et que la méthode equals de cette classe compare le champ en appelant de manière récursive equals, appelez récursivement hashCode sur le champ. Si la valeur du champ est null, renvoyez 0.
  • Si le champ est un tableau, traitez-le comme si chaque élément est un champ distinct. Si chaque élément d'un champ de tableau est significatif, vous pouvez utiliser l'une des méthodes Arrays.hashCode ajoutées dans la version 1.5.
• Combine la hashcode c dans result comme suit: result = 31 * result + c;

Answer 4

hashcode() n'est pas destiné à être utilisé pour vérifier l'égalité. return 42; est une implémentation parfaitement valide de hashcode(). Pourquoi ne pas écraser equals() (et hashcode() d'ailleurs) dans les objets rules et l'utiliser pour vérifier si deux règles sont égales? Vous pouvez toujours utiliser le hashcode pour vérifier les objets que vous devez étudier, car deux objets equal() doivent toujours avoir le même hashcode, mais il s'agit d'une amélioration des performances dont vous pouvez avoir besoin, selon votre système.

Answer 5

J'ai commencé à écrire que la seule façon de réaliser ce que vous voulez est avec Perfect Hashing.

Mais j'ai pensé au fait que vous avez dit que vous ne pouvez pas dupliquer des objets dans votre système.

Modifier basé sur le commentaire qui suscite la réflexion de HELIOS:

Votre solution dépend de ce que vous vouliez dire lorsque vous avez écrit que vous « ne pouvez pas dupliquer les règles ». Si vous vouliez dire littéralement que vous ne pouvez pas, qu'il y a une seule instance d'une règle avec un ensemble particulier de valeurs, alors votre problème est trivial: vous pouvez faire une comparaison d'identité, auquel cas vous pouvez faire comparaison d'identité en utilisant ==. D'autre part, vous vouliez dire que vous ne devrait pas pour une raison quelconque (performance), alors votre problème est également trivial: faites simplement des comparaisons de valeurs. Compte tenu de la façon dont vous avez défini votre problème, vous ne devez en aucun cas considérer l'utilisation de hashcodes comme un substitut à l'égalité. Comme d'autres l'ont noté, les hashcodes par leur nature produisent des collisions (fausse égalité), sauf si vous allez à une solution Perfect Hashing, mais pourquoi dans ce cas?