Peut de Java hashCode produire la même valeur pour les différentes chaînes?

OUI. Beaucoup.

Regarder la suite de la paire de

• "FB" et "Ea"

peut revenir même code de hachage, même si les caractères ne sont pas les mêmes.

Fondamentalement, c'est la somme des caractères dans une chaîne, multiplié par un nombre entier.

si c'est possible, alors quel est le % de ses possibilités?

Qui n'est pas particulièrement significative question.

Toutefois, sauf s'il existe un biais systémique dans le String::hashcode de la fonction ou de la façon dont vous êtes la génération de la String objets, la probabilité que deux différents (non égal) String objets ont le même code de hachage sera de 1 à 2³².

Cela suppose que les Cordes sont choisis au hasard à partir de l'ensemble de toutes les valeurs de Chaîne. Si vous restreindre le jeu de différentes manières, la probabilité varie de numéro ci-dessus. (Par exemple, l'existence de la "FB" /"Ea" collision signifie que la probabilité de collision dans le jeu de tous les 2 chaînes de lettres est plus élevée que la norme.)

---

Une autre chose à noter est que la chance de la 2³² différentes chaînes de caractères choisis au hasard (à partir d'un beaucoup plus impartiale ensemble de chaînes n'ayant pas de collisions de hachage est extrêmement petit. Pour comprendre pourquoi, lire la page de Wikipedia sur le Le Paradoxe D'Anniversaire.

En réalité, la seule façon que vous allez obtenir pas de collisions de hachage dans un ensemble de 2³² différentes chaînes est si vous sélectionnez ou de générer des chaînes de caractères. Même formant l'ensemble en sélectionnant généré de façon aléatoire des chaînes va être gourmand en ressources. Pour produire un tel ensemble de manière efficace, vous avez besoin pour exploiter les propriétés de la String::hashCode algorithme, qui (heureusement) est spécifié.

Oui, il est possible pour les deux Chaînes ont le même hashcode - Si vous prenez un coup d'oeil à la Article de Wikipedia, vous verrez que les deux "FB" et "Ea" ont le même hashcode. Il n'y a rien dans la méthode du contrat de dire un hashCode() devraient être utilisées pour comparer l'égalité, vous souhaitez utiliser equals() pour que.

Depuis Java 1.2, la Chaîne met en œuvre hashCode() par à l'aide d'un produit algorithme de somme sur l'ensemble du texte de la chaîne.

Le pourcentage de collisions pour aléatoire chaînes devraient être minimes. Toutefois, si vous hachage des chaînes à partir de sources externes, un attaquant pourrait facilement créer des centaines de milliers de chaînes ayant le même hashcode. Dans une java HashMap tous ces carte pour le même seau et effectivement faire tourner la carte dans une liste chaînée. Les temps d'accès à la carte serait alors proportionnelle à la taille de la carte au lieu de la constante, entraînant un déni de service (ddos).

Voir cette page sur Efficace DoS d'attaques contre les Applications Web Plattforms pour plus d'informations, des liens vers la présentation.

//Vous pouvez exécuter le code ci-dessous avec -Xmx2100m et peut obtenir plusieurs résultats, assez 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"); 
    }
}

`