Pourquoi hashCode() renvoient la même valeur pour les différents objets en Java?

de hachage un objet signifie "de trouver une bonne valeur descriptive (nombre) qui peuvent être reproduites par la même instance, encore et encore". Parce que des codes de hachage à partir de Java Object.hashCode() sont de type int, vous ne pouvez avoir 2^32 des valeurs différentes. C'est la raison pour laquelle vous avez soi-disant "collisions", selon l'algorithme de hachage, lorsque deux Objets distincts produire le même hashCode.

Généralement, cela ne produit pas tous les problèmes, car hashCode() est principalement utilisé avec equals(). Par exemple, un HashMap appellera hashCode() sur ses clés, à savoir si les touches peut-être déjà contenues dans la table de hachage. Si la table de hachage ne trouve pas le code de hachage, il est évident que la clé n'est pas contenue dans la table de hachage encore. Mais s'il le fait, il aura à vérifier toutes les clés ayant le même code de hachage à l'aide de equals().

I. e.

A.hashCode() == B.hashCode() //does not necessarily mean
A.equals(B)

Mais

A.equals(B) //means
A.hashCode() == B.hashCode()

Si equals() et hashCode() sont mis en œuvre correctement.

Pour une description plus précise de la générale hashCode contrat, voir la Javadoc.

OriginalL'auteur Lukas Eder

L'idée d'une table de hachage est que vous voulez être en mesure de réaliser un discbased appelé dictionnaire de manière efficace. Un dictionnaire est un magasin de clé/valeur, c'est à dire, vous voulez être en mesure de stocker certains objets sous une certaine touche et, plus tard, être en mesure de récupérer à nouveau à l'aide de la même clé.

L'un des moyens les plus efficaces pour les valeurs de l'accès est de les stocker dans un tableau. Par exemple, nous avons pu réaliser un dictionnaire qui utilise des entiers pour les clés et les Chaînes de valeurs comme suit:

String[] dictionary = new String[DICT_SIZE];
dictionary[15] = "Hello";
dictionary[121] = "world";

System.out.println(dictionary[15]); //prints "Hello"

Malheureusement, cette approche n'est pas très général: l'index d'un tableau doit être une valeur entière, mais, idéalement, nous aimerions être en mesure d'utiliser arbitraire sortes d'objets pour nos clés, non seulement des nombres entiers.

Maintenant, la façon de résoudre ce point est d'avoir un moyen de la cartographie de l'arbitraire des objets de valeurs entières, à qui nous avons pu ensuite utiliser que des clés de notre tableau. En Java, c'est ce que hashCode(). Alors maintenant, nous pourrions essayer de mettre en œuvre une Chaîne de caractères->String dictionnaire:

String[] dictionary = new String[DICT_SIZE];
//"a" -> "Hello"
dictionary["a".hashCode()] = "Hello";

//"b" -> "world"
dictionary["b".hashCode()] = "world";

System.out.println(dictionary["b".hashCode()]); //prints world

Mais hé, si il y a un objet qui nous aimerions utiliser comme une clé, mais son hashCode méthode renvoie une valeur qui est supérieure ou égale à DICT_SIZE? Ensuite, nous aurions une ArrayIndexOutOfBoundsException et qui ne serait pas souhaitable. Donc, nous allons juste faire aussi grand que nous le pouvons, droite?

public static final int DICT_SIZE = Integer.MAX_VALUE //Ooops!

Mais cela signifierait que nous aurions à allouer ginormeous quantités de mémoire pour notre tableau, même si nous avons l'intention de stocker quelques éléments. Donc ça ne peut pas être la meilleure solution, et en fait, nous pouvons faire mieux. Supposons que nous avions une fonction h que pour tout DICT_SIZE cartes arbitraire entiers dans la gamme [0, DICT_SIZE[. Alors nous pourrions l'appliquer h quelle que soit la hashCode() méthode d'un objet clé retourne et soyez certains que nous restons dans les limites de la sous-matrice.

public static int h(int value, int DICT_SIZE) {
    //returns an integer >= 0 and < DICT_SIZE for every value.
}

Que la fonction est appelée fonction de hachage. Maintenant, nous pouvons adapter notre dictionnaire en œuvre pour éviter la ArrayIndexOutOfBoundsException:

//"a" -> "Hello"
dictionary[h("a".hashCode(), DICT_SIZE)] = "Hello"

//"b" -> "world"
dictionary[h("b".hashCode(), DICT_SIZE)] = "world"

Mais qui introduit un autre problème: que faire si h cartes deux principaux indices de la même valeur? Par exemple:

int keyA = h("a".hashCode(), DICT_SIZE);
int keyB = h("b".hashCode(), DICT_SIZE);

peut produire les mêmes valeurs pour keyA et keyB, et dans ce cas nous écraser accidentellement une valeur dans notre tableau:

//"a" -> "Hello"
dictionary[keyA] = "Hello";

//"b" -> "world"
dictionary[keyB] = "world"; //DAMN! This overwrites "Hello"!!

System.out.println(dictionary[keyA]); //prints "world"

Bien, vous pouvez dire, ensuite, nous avons juste à nous assurer de mettre en œuvre h d'une manière telle que cela ne se produise jamais. Malheureusement, ce n'est pas possible en général. Considérons le code suivant:

for (int i = 0; i <= DICT_SIZE; i++) {
    dictionary[h(i, DICT_SIZE)] = "dummy";
}

Cette boucle magasins DICT_SIZE + 1 valeurs (toujours la même valeur, en fait, à savoir la Chaîne "dummy") dans le dictionnaire. Mhh, mais le tableau ne peut stocker que de DICT_SIZE entrées différentes! Cela signifie que, lorsque nous utilisons h, nous écraser (au moins) une entrée. Ou en d'autres termes, h mappe les deux clés différentes pour la même valeur! Ces "collisions" ne peut pas être évitée: si n pigeons essayer d'aller en n-1 pigeon trous, au moins deux d'entre eux ont d'aller dans le même trou.

Mais ce que nous pouvons faire est d'étendre notre mise en œuvre, de sorte que l'ensemble peut stocker plusieurs valeurs sous le même index. Ceci peut être facilement fait en utilisant les listes. Ainsi, au lieu de l'aide:

String[] dictionary = new String[DICT_SIZE];

nous écrire:

List<String>[] dictionary = new List<String>[DICT_SIZE];

(Côté remarque: notez que Java n'autorise pas la création de tableaux de types génériques, de sorte que la ligne ci-dessus ne serait pas de compilation -- mais vous voyez l'idée).

Qui va changer l'accès au dictionnaire comme suit:

//"a" -> "Hello"
dictionary[h("a".hashCode(), DICT_SIZE)].add("Hello");

//"b" -> "world"
dictionary[h("b".hashCode(), DICT_SIZE)].add("world");

Dans le cas de notre hashfunction h renvoie des valeurs différentes pour l'ensemble de nos clés, cela va se traduire, dans une liste avec un seul élément de chaque, et de récupération des éléments est très simple:

System.out.println(dictionary[h("a".hashCode(), DICT_SIZE)].get(0)); //"Hello"

Mais nous savons déjà qu'en général h sera la carte de clés différentes pour le même entier, parfois. Dans ces cas, les listes contiendront plus d'une valeur. Pour la récupération, nous avons à parcourir toute la liste pour trouver la valeur "correct", mais comment aurions-nous la reconnaître?

Bien, au lieu de stocker la valeur seul, on peut toujours stocker les complet (clé,valeur) paire dans les listes. Puis recherche serait effectuée en deux étapes:

1. Appliquer la hashfunction pour récupérer la liste correcte de la pile.
2. Itérer sur toutes les paires stockés dans l'extrait de la liste: si la paire avec la touche souhaitée est trouvée, renvoyer la valeur de la paire.

Maintenant l'ajout et la récupération sont devenues tellement complexes qu'il n'est pas indécent de traiter nous-mêmes méthodes distinctes pour ces opérations:

List<Pair<String,String>>[] dictionary = List<Pair<String,String>>[DICT_SIZE];

public void put(String key, String value) {
    int hashCode = key.hashCode();
    int arrayIndex = h(hashCode, DICT_SIZE);

    List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
    if (listAtIndex == null) {
        listAtIndex = new LinkedList<Pair<Integer,String>>();
        dictionary[arrayIndex] = listAtIndex;
    }

    for (Pair<String,String> previouslyAdded : listAtIndex) {
        if (previouslyAdded.getValue().equals(value)) {
            return; //the value is already in the dictionary;
        }
    }

    listAtIndex.add(new Pair<String,String>(key, value));
}

public String get(String key) {
    int hashCode = key.hashCode();
    int arrayIndex = h(hashCode, DICT_SIZE);

    List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
    if (listAtIndex != null) {
        for (Pair<String,String> previouslyAdded : listAtIndex) {
            if (previouslyAdded.getKey().equals(key)) {
                return previouslyAdded.getValue(); //entry found!
            }
        }
    }

    //entry not found
    return null;
}

Donc, pour que cette approche fonctionne, nous avons besoin de deux opérations de comparaison: la méthode hashCode pour trouver la liste dans le tableau (ce qui fonctionne rapidement si hashCode() et h sont à la fois rapides) et un equals méthode dont nous avons besoin, quand nous allons à travers la liste.

C'est l'idée générale de hachage, et vous reconnaîtrez la put et get méthode de java.util.Map. bien sûr, la mise en œuvre est une simplification excessive, mais il doit illustrer l'essentiel de tout cela.

Naturellement, cette approche n'est pas limitée à des Chaînes, il fonctionne pour tous les types d'objets, depuis les méthodes hashCode() et equals sont membres de haut niveau de la classe java.lang.Objet et toutes les autres classes héritent de cette.

Comme vous pouvez le voir, il n'a pas vraiment d'importance si les deux objets distincts retourner la même valeur dans leur hashCode() méthode: l'approche ci-dessus fonctionnera toujours! Mais encore, il est souhaitable qu'ils retournent des valeurs différentes pour diminuer les risques de collisions de hachage produit par h. Nous avons vu que celles-ci ne peuvent être évitées 100% en général, mais le moins de collisions, plus efficace notre table de hachage devient. Dans le pire des cas, toutes les clés de la carte pour le même index de tableau: dans ce cas, toutes les paires sont stockées dans une liste et de trouver une valeur qui deviendra alors une opération avec des coûts linéaire en la taille de la table de hachage.

OriginalL'auteur Thomas

Que je comprends, le travail de la méthode hashcode est de créer des seaux pour le hachage des éléments, de Sorte que la récupération peut être plus rapide. Si chaque objet sera de retour même valeur, ce n'est pas de faire de hachage.

OriginalL'auteur Vishwanath