Question Pourquoi String.hashCode () dans Java a-t-il de nombreux conflits? [fermé]


Pourquoi String.hashcode () a-t-il autant de conflits?

Je lis le String.hashCode () dans jdk1.6, ci-dessous sont les codes

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

Cela me semble assez déroutant car il y a tellement de conflits; Bien qu'il ne soit pas obligatoire d'être unique (nous pouvons toujours compter sur les égaux ()), moins de conflits signifie de meilleures performances sans visiter les entrées d'une liste chaînée.

Supposons que nous ayons deux caractères, alors tant que nous pouvons trouver deux chaînes correspondant à l'équation, alors nous aurons le même hashcode ()

a * 31 +b = c * 31 +d

Il sera facile de conclure que (a-c) * 31 = d-b Prenons un exemple simple: a-c = 1 et d-b = 31; donc j'ai écrit ci-dessous les codes pour le test simple

public void testHash() {
    System.out.println("A:" + (int)'A');
    System.out.println("B:" + (int)'B');
    System.out.println("a:" + (int)'a');

    System.out.println("Aa".hashCode() + "," + "BB".hashCode());
    System.out.println("Ba".hashCode() + "," + "CB".hashCode());
    System.out.println("Ca".hashCode() + "," + "DB".hashCode());
    System.out.println("Da".hashCode() + "," + "EB".hashCode());        
}

il affichera ci-dessous les résultats, ce qui signifie que toutes les chaînes ont le même hashcode (), et qu'il est facile de le faire en boucle.

A:65 
B:66
a:97
2112,2112
2143,2143
2174,2174
2205,2205

pire encore, supposons que nous avons 4 caractères dans la chaîne, selon l’algorithme, supposons que les 2 premiers caractères produisent a2, que les 2 autres caractères produisent b2; le hashcode sera toujours a2 * 31^2 + b2 ainsi, avec a2 et b2 égaux entre 2 chaînes, nous aurons plus de chaînes avec un conflit de hashcode (). ces exemples sont "AaAa", "BBBB" et ainsi de suite; nous aurons alors 6 caractères, 8 caractères ......

supposons que la plupart du temps nous utilisons des caractères dans une table ascii dans une chaîne qui sera utilisée dans un hashmap ou une table de hachage, alors le nombre premier 31 choisi ici est nettement trop petit;

Une solution simple consiste à utiliser un nombre premier plus grand (heureusement, 257 est un nombre premier), ce qui permet d'éviter ce conflit. bien sûr, choisir un nombre trop grand entraînera le débordement de la valeur int si la chaîne est très longue, mais je suppose que la plupart du temps, la chaîne utilisée comme clé n'est pas si grande? Bien sûr, cela pourrait encore générer une valeur longue pour éviter cela.

ci-dessous est ma version modifiée de betterhash () qui peut résoudre facilement de tels conflits en exécutant les codes, il imprime les valeurs ci-dessous, ce qui est efficace pour résoudre ce problème.

16802,17028
17059,17285
17316,17542
17573,17799

mais pourquoi jdk ne le répare pas? THX.

@Test
public void testBetterhash() {
    System.out.println(betterHash("Aa") + "," + betterHash("BB"));      
    System.out.println(betterHash("Ba") + "," + betterHash("CB"));
    System.out.println(betterHash("Ca") + "," + betterHash("DB"));
    System.out.println(betterHash("Da") + "," + betterHash("EB"));
}

public static int betterHash(String s) {
    int h = 0;
    int len = s.length();

    for (int i = 0; i < len; i++) {
        h = 257*h + s.charAt(i);
    }
    return h;
}

23
2018-02-23 03:34


origine


Réponses:


Je viens de hacher 58 mille mots en anglais (trouvés ici), à la fois en minuscule et avec la première lettre en majuscule. Savoir combien sont entrés en collision? Deux: "frères et soeurs" et "Téhéran" (une orthographe alternative de "Téhéran").

Tout comme vous, j'ai pris un sous-domaine (dans mon cas, probablement un sous-domaine) de chaînes possibles et analysé le taux de collision hashCode associé, et je l'ai trouvé exemplaire. Qui peut dire que votre sous-domaine arbitraire de chaînes possibles est un meilleur choix à optimiser que le mien?

Les personnes qui ont écrit cette classe ont dû le faire, sachant qu'elles ne pouvaient pas prédire (ni donc optimiser) le sous-domaine dans lequel leurs utilisateurs utiliseraient des chaînes comme clés. Ils ont donc choisi une fonction de hachage qui distribue uniformément sur la tout domaine des chaînes.

Si vous êtes intéressé, voici mon code (il utilise Guava):

    List<String> words = CharStreams.readLines(new InputStreamReader(StringHashTester.class.getResourceAsStream("corncob_lowercase.txt")));
    Multimap<Integer, String> wordMap = ArrayListMultimap.create();
    for (String word : words) {
        wordMap.put(word.hashCode(), word);
        String capitalizedWord = word.substring(0, 1).toUpperCase() + word.substring(1);
        wordMap.put(capitalizedWord.hashCode(), capitalizedWord);
    }

    Map<Integer, Collection<String>> collisions = Maps.filterValues(wordMap.asMap(), new Predicate<Collection<String>>() {
        public boolean apply(Collection<String> strings) {
            return strings.size() > 1;
        }
    });

    System.out.println("Number of collisions: " + collisions.size());
    for (Collection<String> collision : collisions.values()) {
        System.out.println(collision);
    }

modifier

Par ailleurs, si vous êtes curieux de voir que le même test avec votre fonction de hachage a eu 13 collisions par rapport à String.hashCode's 1.


37
2018-02-23 04:09



Je suis désolé, mais nous devons jeter de l'eau froide sur cette idée.

  1. Votre analyse est trop simpliste. Vous semblez avoir choisi un sous-ensemble de chaînes conçu pour prouver votre point de vue. Cela ne prouve pas que le nombre de collisions est (statistiquement) plus élevé que prévu dans le domaine de toutes les chaînes.

  2. Personne dans leur esprit ne serait attendre String.hashCode pour être hautement exempt de collision. Il n'est tout simplement pas conçu dans cet esprit. (Si vous voulez un hachage sans collision, utilisez un algorithme de hachage crypto ... et payez le coût.) String.hashCode () est conçu pour être raisonnablement bon dans le domaine de toutes les chaînes ... et vite.

  3. En supposant que vous puissiez faire valoir un argument plus fort, ce n’est pas le lieu de le dire. Vous devez soulever ce problème avec les personnes qui comptent - l'équipe d'ingénierie Java d'Oracle.

  4. L'équipe d'ingénierie Java va évaluer les avantages d'une telle modification par rapport aux coûts de mise en œuvre, pour eux, et pour tout autre utilisateur de Java. Le dernier point est probablement suffisant pour tuer cette idée morte de pierre.


("Le hachage sans collision" est une idée / un terme que j'ai sorti des ondes pour cette réponse. Désolé. Cependant, l'essentiel est que la probabilité d'une collision de hashcode pour 2 chaînes devrait être indépendante de ils sont. Ainsi, par exemple, "AA" et "bz" sont liés en raison de la même longueur. Évidemment, cette idée a besoin de plus de réflexion. Et il est également évident que la "parenté" dans le sens dont je parle est pas mesurable ... un peu comme Kolmogorov Complexité.)


11
2018-02-23 04:16



Les collisions sont inévitables lors du hachage. le hashCode() method renvoie un entier qui est utilisé comme index dans un tableau qui est un compartiment pour tous les objets avec le même code de hachage. le equals(Object) Cette méthode permet de comparer l'objet cible à chacun des éléments du compartiment afin d'identifier l'objet correspondant, s'il existe.

En fin de compte, le hashCode() la méthode doit juste être vite et pas trop faible (c'est-à-dire causant trop de collisions), où trop faible est une métrique assez floue.


7
2018-02-23 03:40



C'est plutôt efficace mais aussi simple. Tous les mots minuscules (ASCII) possibles, jusqu'à six lettres ou tous les nombres jusqu'à six chiffres, ont un hashCode () unique. c'est-à-dire que le hashCode est comme un nombre de base 31. L'utilisation d'un plus grand nombre a ses propres problèmes. Un facteur de 257 laisserait chaque bit 8 pas particulièrement aléatoire car tous les caractères ASCII ont un bit supérieur. Un facteur plus important résulterait en des codes de hachage en double pour les mots de cinq et six chiffres / lettres.

Quel est peut-être le plus gros problème si vous ne pouvez pas modifier l'algorithme de hachage. Quelle que soit l’approche que vous prenez, il peut s’agir d’un cas où ce choix est très mauvais et qui risque d’être sous-optimal pour votre cas d’utilisation.

Le plus gros problème est peut-être celui des attaques par déni de service qui rendent les cas pathologiques, très rares en règle générale, assez courants. Par exemple, un moyen d’attaquer un serveur Web consiste à remplir un cache avec des clés ayant toutes le même hashCode, par ex. 0 qui est calculé à chaque fois. HashMap dégénère en une liste chaînée.

Un moyen simple de contourner cela consiste à rendre l’algorithme de hachage inconnu, éventuellement en train de changer. En l'état, le mieux pourrait être d'utiliser un TreeMap (qui prend en charge la comparaison personnalisée, bien que la valeur par défaut soit correcte dans ce cas)


0
2018-02-23 08:46