Je lisais les documents de l'API Java sur la classe Hashtable et je suis tombé sur plusieurs questions. Dans le doc, il dit "1
3
6 Réponses :
Un hachage est une fonction calculée qui mappe un objet ("un" ou "deux" dans votre échantillon) à (dans ce cas) un entier. Cela signifie qu'il peut y avoir plusieurs valeurs qui correspondent au même entier (un entier a un nombre fini de valeurs autorisées alors qu'il peut y avoir un nombre infini d'entrées). Dans ce cas, "est égal" doit pouvoir le dire à ces deux personnes. Donc, votre exemple de code est correct, mais il peut y avoir une autre clé qui a le même hashcode (et sera placée dans le même godet que "deux")
Non, ce n'est pas ce que l'on entend par "ouvert".
Notez la différence entre une collision clé et une collision hachage .
La haquetable n'autorise pas plus d'une entrée avec la même clé (comme dans votre exemple, vous mettez deux entrées avec la clé "Deux", la deuxième (3) remplaçait le premier (3). (2), et vous avez été laissé avec seulement le second dans la haquetable).
A Hash La collision est lorsque deux touches différentes ont le même hashcode (comme retourné par leur méthode HashCode (). Différentes implémentations de la table de hachages pourraient traiter cela de différentes manières, principalement en termes de mise en œuvre de bas niveau. Être "Open", Hashtable stockera une liste liée d'entrées dont le hachage de clés à la même valeur. Cela peut causer, dans le pire des cas, o (n) performance pour des opérations simples, qui serait normalement O (1) dans une carte de hachage où les hachages étaient principalement des valeurs différentes.
Comment puis-je éviter différentes valeurs hachées à une clé?
Pour faciliter la compréhension: regardez la source à String.HashCode () et imprimez la sortie de "One" .HashCode () et "Deux" .HashCode ()
@Derrdji: En général, HASHCODE () doit être mis en œuvre de manière à ce qu'il est peu probable que des valeurs différentes puissent avoir la même clé. Si vous implémentez vos propres classes sous forme de clés, et surtout si vous remplacez la méthode Equals (), vous devez également fournir une bonne méthode HASHCODE (). Pour plus d'informations sur la théorie des fonctions de hachage, voir: en.wikipedia.org/wiki/hash_functionleight/a >
Notez que si deux valeurs différentes hachées au même code de hachage ou à différents codes de hachage n'ont aucun effet fonctionnel sur votre programme. Une des choses que la hache et le hashmap font pour vous sont gérées dans ce cas dans les coulisses. La seule différence qu'il fait est une différence de performance. Si, dans le pire des cas, chaque touche que vous avez ajoutée à la table de hachage avait le même code de hachage, vous finiriez de rechercher séquentiellement la liste complète de chaque accès plutôt que de sauter au bon endroit, et les performances aspiraient. Mais le programme fonctionnerait toujours.
Objet.hashcode () est une sorte de clé pour la haquetable. Les Docs disent sur la collision de Hashedded HashCode (), qui est plus générale que la simple collision du hashcode ().
Cela signifie que Hashtable utilise Ouvrir le hachage (également connu en tant que chaînage séparé) à traiter avec les collisions de hachage. Si deux touches distinctes ont le même hashcode, les deux seront stockées dans le même godet (dans une liste).
J'ai vérifié le code source et Hashtable et HashMap utilisent la chaînage. C'est en fait l'inverse de «l'adressage ouvert», et chaque HASHCode ne peut occuper qu'une adresse exacte dans le tableau. Un exemple d'adressage ouvert serait une sondage linéaire. FWIW, la terminologie est confuse: le hachage ouvert est le contraire exact de l'adressage ouvert.
@San: C'est déroutant! J'ai corrigé mon erreur. Merci d'avoir laissé un commentaire.
Ouvrir signifie que si deux touches ne sont pas égales, mais ont la même valeur de hachage, alors elles seront stockées dans le même "godet". Dans ce cas, vous pouvez penser à chaque godet en tant que liste liée, de sorte que si beaucoup de choses sont stockées dans le même seau, la performance de recherche diminuera.
godet 0: rien de
Seau 1: Article 1
Seau 2: Item 2 -> Article 3
Seau 3: rien de
Seau 4: Article 4
Dans ce cas, si vous recherchez une clé qui hachage au seau 2, vous devez ensuite effectuer une recherche O (n) sur la liste pour trouver la clé qui est égale à ce que vous recherchez. Si la clé hachée au seau 0, 1, 3 ou 4, vous obtenez une performance de recherche O (1) O (1).
Cela signifie que deux éléments avec des touches dans votre cas Les clés " deux forts>" sont identiques et la deuxième place écrase le premier. p> mais en supposant que vous avez votre propre classe p> et créé plusieurs instances de celui-ci. C'est-à-dire p> et les inséré dans une carte. Ensuite, un seau, c'est-à-dire que le godet contenant le truc avec HASHCode 1 contiendra une liste (chaîne) des trois éléments. P> Map<Thingy, Thingy> map = new HashMap<Thingy, Thingy>();
map.put(a, a);
map.put(b, b);
map.put(c, c);
Une excellente réponse, même sans la "meilleure idée du monde isolé" ironiquement sobre. +1, mais je voterais deux fois s'ils me laissaient. :)
citant de http://www.c2.com/cgi/wiki?hashable - a> cité dans une autre réponse:
Attention: certaines personnes utilisent le terme
"Open hachage" pour dire ce que j'ai
appelé "hachage fermé" ici! le
utilisation ici est conforme à cela
en brefComputerProgrammation et
IntroductionToalgorithmes, les deux
qui sont recommandées références si
Vous voulez en savoir plus sur Hash
Tables.
Par exemple, la page ci-dessus définit "Open hachage" comme suit:
Il y a deux stratégies principales. ouvert
hachage, également appelé adressage ouvert,
dit: lorsque l'entrée de la table dont vous avez besoin
pour une nouvelle paire de clé / valeur est déjà
occupé, trouver une autre entrée inutilisée
en quelque sorte et le mettre là-bas. Fermé
hachage dit: chaque entrée dans la table
est une structure de données secondaire (généralement
une liste liée, mais il y a d'autres
possibilités) contenant le réel
données, et cette structure de données peut être
étendu sans limite.
En revanche, la définition fournie par Wikipedia est:
dans la stratégie connue sous le nom de séparé
chaînage, chaînage direct, ou simplement
enchaînant, chaque emplacement du godet
Array est un pointeur sur une liste liée
qui contient les paires de la valeur clé qui
haché au même endroit. Chercher
nécessite de numériser la liste pour un
entrée avec la clé donnée. Insertion
Nécessite d'ajouter un nouvel enregistrement d'entrée
à la fin de la liste dans le
Slot haché. Suppression nécessite
rechercher la liste et enlever la
élément. ( la technique est également appelée
hachage ouvert ou adressage fermé,
qui ne devrait pas être confondu avec
'Open Adressing' ou 'Fermé
hachage '. )
Si soi-disant "experts" ne peut convenir que le terme "hachage ouvert" signifie, il est préférable d'éviter de l'utiliser.