Quelle fonction de hachage Java utiliser par défaut et peut-on remplacer le comportement par défaut?

Je suis passer par la Introduction d'Algorithmes par Cormen et al vidéo et il traite de plusieurs fonctions de hachage . Je veux savoir quelle fonction de hachage Java utiliser par défaut?La fonction de hachage différents pour différents types d'objets qui sont utilisés comme clés? Est-il une api dans les Collections cadre qui nous permettent d'écrire notre propre algorithme de hachage ?

D'autres ont donné de très bonnes réponses à cette question. Je vais juste ajouter que, grâce à la fonction de hachage d'un attribut de l'objet de type plutôt que de la collection, il vous permet de ré-utiliser les mêmes types dans de nombreuses collections, et pour les collections pour gérer tous types arbitraires sans avoir à connaître la façon de hachage de chaque type qu'ils pourraient rencontrer.
Aussi: toujours remplacer la valeur par défaut hashcode lorsque vous effectuez un nouveau type d'objet, si c'est possible, il pourrait être utilisé dans une collection. La valeur par défaut hashcode est basée sur l'identité de l'objet, de sorte que les différentes instances de donner différents hashcodes même si tous les champs sont identiques.
Double Possible de Pourquoi Java est hashCode() en Chaîne de caractères utilisez 31 comme un multiplicateur? je reconnais que ce n'est pas à proprement parler un duplicata; cependant, je crois que un bon réponse à cette question serait d'inclure la réponse à la question précédente.

OriginalL'auteur Geek | 2012-08-16

hash java

7

Chaque objet en java a un public int hashCode() méthode qui retourne une valeur de hachage. Chaque objet est libre de mettre en œuvre dans sa propre méthode par substitution de cette méthode. Si la méthode n'est pas surchargé, la par défaut #hashCode méthode est utilisé.

Vous pouvez avoir regarder le code source de divers objets pour voir comment il est mis en œuvre dans le JDK. C'est La chaîne de hashCode par exemple (ligne 1494).

Certaines collections peuvent ajouter une couche supplémentaire de hachage sur le dessus de l'objet, méthodes hashCode. Par exemple, la table de hachage n'est que pour améliorer les performances lorsqu'un objet est hashCode n'est pas bien réparti.

Intéressant, ne savais pas que les propos de table de hachage. Mais je suppose que le comportement est différent de celui fourni par l'utilisateur de hachage que l'OP demande?
C'est lié. HashMap fondamentalement hache le hachage. Voir HashMap.de hachage.

OriginalL'auteur assylias
2

Vous pouvez toujours le remplacer dans l'un de vos classes...
Comme
```
 @override
 public int hashCode()
 { 
 //new implementation 
 }
```
http://mindprod.com/jgloss/hashcode.html

La valeur par défaut hashCode() la méthode utilise la version 32 bits internes de la JVM (Java Virtual Machine) l'adresse de l'Objet en tant que son hashCode.

Toutefois, si l'Objet est déplacé dans la mémoire lors de la collecte des ordures, le hashCode reste constante. Ce défaut hashCode n'est pas très utile, car pour rechercher un Objet dans une table de hachage, vous avez besoin exactement le même Objet clé par lequel la paire clé/valeur a été déposée à l'origine.

Normalement, quand vous allez chercher, vous n'avez pas la clé d'origine de l'Objet lui-même, juste quelques données pour une clé. Donc, sauf si votre clé est une Chaîne de caractères, presque toujours, vous devrez mettre en place un hashCode et equals méthode sur votre touche de classe.

Objet.hashCode() est une méthode native.

OriginalL'auteur Shark
1

Cela dépend du type d'objet que vous utilisez. Pour tout objet que vous mettre en œuvre dans vos propres classes, vous pouvez toujours remplacer la valeur par défaut hashCode() méthode.

Note, vous devez toujours respecter le contrat entre hashCode() et equals() comme mentionné dans le hashCode() javadoc:

Si deux objets sont égaux selon la equals(Object) méthode, puis en appelant la méthode hashCode sur chacun des deux objets doit produire le même résultat sous forme d'entier.

Pour plus d'informations lire cette entrée.

En fait, si vous avez l'intention de stocker vos objets dans la table de hachage ou similaire, vous devrait (près de doit) remplacer hashCode() et equals()
Yep, j'ai mis à jour mon post avec un certain des informations supplémentaires.

OriginalL'auteur matsev

Chaque type en Java a hashCode() définition de la méthode, c'est dans le Object. hashCode() renvoie une int. Et dans HashMap mise en œuvre, il hache le résultat de nouveau et de prendre uniquement les bits de poids faible dans la gamme de 0 à size-1. Remarque dans le JDK Sun, la taille est toujours 2^x, où x est un nombre entier.

Bibliothèque Java est open source et vous avez probablement une copie sur votre machine de dev.

Dans Sun JDK 6, le second hachage je l'ai mentionné ci-dessus est

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    //This function ensures that hashCodes that differ only by
    //constant multiples at each bit position have a bounded
    //number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Vous pouvez trouver la première de hachage en regardant le hashCode() fonction de la catégorie qui vous intéresse.

OriginalL'auteur Haozhun

0

Toutes les classes en Java hériter de java.lang.Object, et, ce faisant, ils héritent de la méthode hashCode() qui renvoie un int.
Par défaut, la méthode retourne quelques (plus ou moins) valeur unique créé par la machine virtuelle (pensez à l'adresse mémoire de l'objet, même si ce n'est pas tout à fait correct). Lorsque vous mettez en œuvre vos propres classes, vous pouvez remplacer cette méthode pour faire ce que vous voulez. Vous devez toutefois faire attention à ce que votre hashCode et equals méthodes sont compatibles, et vous devez être conscient qu'en général, les codes de hachage ne sont pas uniques, donc que ce soit vous, attendez-vous à des collisions entre des codes de hachage de différents objets.

Les Collections cadre utilise généralement le hashhCode() méthode de hachage choses pour les tables de hachage etc. Il est concevable que d'autres structures de données dans d'autres bibliothèques d'utiliser des fonctions de hachage, mais cela ne se produit pas dans les Collections cadre.

"par défaut, La méthode renvoie une valeur unique": par défaut hashcodes ne sont pas nécessairement unique.
Vrai, même si Object.hashCode sur toute mise en œuvre, je ne sais. J'espère que mon édition précise.
hashcode est un int, donc sur une machine 64 bits, il y a (potentiellement) plus d'adresses de mémoire qu'un int peut contenir par exemple.

OriginalL'auteur Jochen

Vous devez vous connecter pour publier un commentaire.