utilité - méthode equals java




Le hashCode de Java peut-il produire la même valeur pour différentes chaînes? (8)

Est-il possible d'avoir le même hashcode pour différentes chaînes en utilisant la fonction de hashcode de java ou s'il est possible alors quel est le% de sa possibilité?


si c'est possible alors quel est le% de sa possibilité?

Ce n'est pas une question particulièrement significative.

Toutefois, sauf en cas de biais systémiques dans la fonction String::hashcode ou dans la manière dont vous générez les objets String , la probabilité que deux objets String différents (non égaux) aient le même code de hachage sera de 1 sur 2. 32

Cela suppose que les chaînes sont choisies au hasard parmi l'ensemble de toutes les valeurs de chaîne possibles. Si vous limitez le jeu de différentes manières, la probabilité sera différente du nombre ci-dessus. (Par exemple, l’existence de la collision "FB" / "Ea" signifie que la probabilité d’une collision dans l’ensemble des chaînes de 2 lettres est supérieure à la norme.)

Une autre chose à noter est que la chance de 2 32 chaînes différentes choisies au hasard (à partir d'un ensemble de chaînes non biaisé beaucoup plus grand) n'ayant aucune collision de hachage est extrêmement faible. Pour comprendre pourquoi, lisez la page Wikipedia sur le paradoxe de l' anniversaire .

En réalité, la seule façon de ne pas avoir de collisions de hachage dans un ensemble de 2 32 chaînes différentes est de sélectionner ou de générer les chaînes. Même former l'ensemble en sélectionnant des chaînes générées aléatoirement sera coûteux en calcul. Pour produire efficacement un tel ensemble, vous devez exploiter les propriétés de l'algorithme String::hashCode , qui (heureusement) est spécifié.


// Vous pouvez exécuter le code ci-dessous avec -Xmx2100m et obtenir plusieurs résultats, suffisamment pour remplir votre console.

`

import java.util.HashMap;

public class TestHashCollision {
        public static void main(String[] args) {
        final String TEXT = "was stored earlier had the same hash as";
        HashMap<Integer,String> hs=new HashMap<>();
        long t1=System.currentTimeMillis();
        long t2=System.currentTimeMillis();
        for(long l=0;l<Long.MAX_VALUE;l++) {
            String key="d"+l;
            if(hs.containsKey(key.hashCode())) {
                System.out.println("'"+hs.get(key.hashCode())+"' "+TEXT+" '"+key+"'");//System.exit(0);
            } else {
                hs.put(key.hashCode(),key);
            }
            t2=System.currentTimeMillis();
            if(t2-t1>10000) {
                t1=System.currentTimeMillis();
                System.out.println("10 seconds gone! size is:"+hs.size());
            }
        }
        System.out.println("Done"); 
    }
}

`


Le pourcentage de collisions pour des chaînes aléatoires devrait être minimal. Cependant, si vous utilisez des chaînes de hachage provenant de sources externes, un attaquant pourrait facilement créer des centaines de milliers de chaînes ayant le même code de hachage. Dans un HashMap java, ils seraient tous mappés dans le même seau et transformeraient efficacement la carte en une liste chaînée. Les temps d’accès à la carte seraient alors proportionnels à la taille de la carte et non constants, menant à une attaque par déni de service.

Voir cette page sur les attaques DoS efficaces contre les plates-formes d'applications Web pour plus d'informations sur les liens vers la présentation.


OUI. Beaucoup.

Regardez la paire suivante

  • "FB" et "Ea"

peut retourner le même code de hachage même si les caractères qu'il contient ne sont pas identiques.

Fondamentalement, il s'agit de la somme des caractères d'une chaîne multipliée par un entier.


Oui, c'est possible, car l'un des contrats entre equals () et la méthode hashCode () de la classe Object est .......... Si deux objets ne sont pas égaux selon la méthode equals (), il n'y a pas de garantie que leur hashCode soit identique, le hashCode peut ne pas être égal. c'est-à-dire que si obj1.equals (obj2) renvoie false, alors obj1.hashCode () == obj2.hashCode () peut / ne peut pas renvoyer true. Exemple:

    String str1 = "FB";
    String str2 = "Ea";
    System.out.println(str1.equals(str2));// false
    System.out.println(str1.hashCode() == str2.hashCode()); // true

Oui, c'est tout à fait possible. La probabilité qu'une chaîne (ou un autre type d'objet - en supposant que vous utilisiez des chaînes dans cet exemple) ayant le même hashcode qu'une autre chaîne d'une collection, dépend de la taille de cette collection (en supposant que toutes les chaînes dans cette collection sont uniques). Les probabilités sont réparties comme suit:

  • Avec un ensemble de taille ~ 9 000, vous aurez 1% de chances que deux chaînes entrent en collision avec un dièse dans l'ensemble
  • Avec un ensemble de taille ~ 30 000, vous aurez 10% de chances que deux chaînes entrent en collision avec un dièse dans l'ensemble
  • Avec un ensemble de taille ~ 77 000, vous aurez 50% de chances que deux chaînes entrent en collision avec un dièse dans l'ensemble

Les hypothèses retenues sont:

  • La fonction hashCode n'a pas de biais
  • Chaque chaîne de cet ensemble est unique

Ce site l'explique clairement: http://eclipsesource.com/blogs/2012/09/04/the-3-things-you-should-know-about-hashcode/ (Regardez "la deuxième chose que vous devriez savoir")


Oui, par définition du concept de pigeon-trou, deux chaînes différentes peuvent produire le même hashcode et le code doit toujours être écrit pour répondre à de telles conditions (généralement, en ne cassant pas.)


Un code de hachage Java est 32bits. Le nombre de chaînes possibles qu'il hache est infini.

Alors oui, il y aura des collisions. Le pourcentage n'a pas de sens - il existe un nombre infini d'éléments (chaînes) et un nombre fini de hachages possibles.





hashcode