Disons que je dois faire un mappage de chaîne code> à un entier. Les entiers sont uniques et forment une plage continue à partir de 0. C'est-à-dire: List<String> list = ...
int integer = list.indexOf(string); // Plus maybe check for -1.
6 Réponses :
Vous avez raison: une liste serait O (n), un hashmap serait O (1), donc un hashmap serait plus rapide pour n assez grand de sorte que le temps nécessaire pour calculer le hachage ne faisait pas ma liste. recherche linéaire.
Je ne connais pas la taille de seuil; C'est une question d'expérimentation ou d'analyses de meilleure qualité que je ne peux me rassembler en ce moment.
Les hashmaps ne sont pas O (1), car vous pouvez avoir plusieurs valeurs ayant la même valeur de hachage.
@ Thorbjørn Ravn Andersen: Oui, mais si vous choisissez soigneusement la fonction de hachage, vous pouvez le réduire au minimum.
@ Thorbjørn Ravn Andersen - ils sont généralement décrits comme O (1) en moyenne, mais le pire cas est o (n) . Sauf si vous avez une mauvaise fonction de hash, la probabilité du pire des cas devient trop petite que n augmente.
@Stephen La fonction O ne décrit pas la moyenne, mais le pire des cas.
@Chii, et cela nécessite donc de savoir le jeu de données à l'avance, oui?
@ Thorbjørn Ravn Andersen - pas vrai. Il décrit ce qu'il décrit. Par exemple: EN.Wikipedia.org/wiki/QuickSort#Avoirement_complexité
@Stephen, veuillez relier le lien vers les informations correctes. en.wikipedia.org/wiki/big_o_notation . "Big O Notation (également connu sous le nom de Big Oh Noter, la notation Landau, la notation Bachmann-Landau et la notation asymptotique) décrit le comportement limitant d'une fonction lorsque l'argument a tendance à une valeur particulière ou à une infinie". Tout en fonction de la valeur de n (que la taille du godet de hachage) est supérieure à O (1)
@ Thorbjørn Ravn Andersen HASHMAP possède une fonction de hachage améliorée interne qui empêche la collision et la tombe dans le même seau pour différentes clés.
@ Thorbjørn Ravn Andersen - Java.Util.HashMap redimensionne la carte en utilisant un facteur de charge. Cela réduit la moyenne Nombre de collisions par godet à une valeur indépendante du nombre d'entrées de carte n . D'où le O (1) temps par lookUp à l'aide de hachap .
Votre question est totalement correcte sur tous les points:
hashmap s est meilleur (ils utilisent un hash)
- Benchmarking Code Java est dur
Mais à la fin de la journée, vous allez simplement avoir à comparaître votre application particulière. Je ne vois pas pourquoi les hashmaps seraient plus lents pour de petits cas, mais le benchmarking vous donnera la réponse si elle est ou non.
Une autre option, un Treemap < / Code> est une autre structure de données de carte qui utilise un arbre par opposition à un hachage d'accès aux entrées. Si vous faites référence à une analyse comparative, vous pourriez aussi bien comparer cela.
En ce qui concerne l'analyse comparative, l'un des principaux problèmes est le collecteur des ordures. Cependant, si vous faites un test qui n'alloue pas d'objet, cela ne devrait pas être un problème. Remplissez votre carte / liste, puis écrivez simplement une boucle pour obtenir n éléments aléatoires, puis il doit être raisonnablement reproductible et donc informatif.
Votre trie a fusionné certaines des lettres dans un seul noeud (une trie avec une lettre par nœud aurait un O (longueur de chaîne) heure de recherche) - ça va être un cauchemar à écrire (Chaque insert devra se fusionner / élargir les nœuds comme il a cherché le bon endroit)!
Hum, non, peut-être que l'image ressemble à cela, mais le texte du nœud décrit simplement la chaîne de la racine à ce nœud.
@AIOOBE J'ai la même tendance à utiliser des essais pour ces scénarios, mais ils ne sont pas thread-coffre-fort. Comment pouvez-vous utiliser des essais et obtenir toujours les avantages de l'utilisation d'une structure de données hautement concurrente telle que ConcourshashMap?
De ce que je peux me rappeler, la méthode de liste sera O (n), mais il serait rapide d'ajouter des éléments, car aucun calcul n'a lieu. Vous pouvez obtenir ce bassin O (journal N) si vous avez implémenté une recherche B ou d'autres algorithmes de recherche. Le hash est O (1), mais sa plus lente d'insérer, car le hachage doit être calculé à chaque fois que vous ajoutez un élément.
Je sais dans .NET, theres une collection spéciale appelée hybriddictionnaire, cela fait exactement cela. Utilise une liste sur un point, puis un hachage. Je pense que le croisement est d'environ 10 ans, il peut donc s'agir d'une bonne ligne dans le sable.
Je dirais que vous êtes correct dans votre déclaration ci-dessus, bien que je ne sois pas sûr à 100% si une liste serait plus rapide pour les petits ensembles, et où le point de croisement est.
Malheureusement, vous allez devoir faire référence à cela vous-même, car les performances relatives dépendront de manière critique sur les valeurs de chaîne réelles, ainsi que sur la probabilité relative que vous testez une chaîne qui ne figure pas dans votre mappage. Et bien sûr, cela dépend de la manière dont Dans le cas d'un dans le cas d'une liste , une recherche appellera En plus du TRIE Alternative suggérée par @aioobe, vous pouvez également implémenter une chaîne spécialisée Entier Hashmap à l'aide d'une soi-disant fonction de hachage parfaite . Cela correspond à chacune des chaînes clés réelles à un hachage unique dans une petite gamme. Le hachage peut ensuite être utilisé pour indexer un tableau de paires de clé / valeur. Cela réduit une recherche exactement à un appel à la fonction de hachage et à un appel à La difficulté de l'approche de hachage parfaite consiste à trouver une fonction qui fonctionne pour l'ensemble des clés dans la cartographie et n'est pas trop coûteuse pour calculer. AFAIK, cela doit être fait par essai et par erreur.
Mais la réalité est que simplement à l'aide d'un (fwiw, mon devinez est que le point mort-même où string.equals () et string.hashcode () sont implémentés, ainsi que les détails du hashmap et list classes utilisés.
HASHMAP , une recherche impliquera généralement le calcul du hachage de la chaîne de clé, puis comparant la chaîne de clé avec une ou plusieurs chaînes de clé d'entrée. Le calcul de code HASHCODE regarde tous les caractères de la chaîne et dépend donc de la chaîne de clés. Les opérations équivalent généralement examineront généralement tous les caractères lorsque est égal à renvoie true et considérablement moins quand il renvoie false . Le nombre réel de fois que est égal à est appelé pour une chaîne de clé donnée dépend de la manière dont les chaînes de clé hachée sont distribuées. Normalement, vous vous attendriez à une moyenne de 1 ou 2 appels à égaler pour un "coup" et peut-être jusqu'à 3 pour une "Miss".
égale pour une moitié de la moitié des chaînes de clé d'entrée dans le cas d'un "hit" et tous dans le cas d'une "Miss". Si vous connaissez la distribution relative des touches que vous recherchez, vous pouvez améliorer les performances dans le cas «Hit» en commandant la liste. Mais le cas "Miss" ne peut pas être optimisé.
string.equals . (Et si vous pouvez supposer que la clé fournie sera toujours l'une des chaînes mappées, vous pouvez vous dispenser avec l'appel à égale .)
hashmap est une option sûre, car elle donne O (1) performance avec une constante de proportionnalité relativement petite (à moins que l'entrée Les clés sont pathologiques).
hashmap.get () devient meilleur que list.Contains () est inférieur à 10 en supposant que les chaînes ont une longueur moyenne de 5 à 10 .)
Vous pouvez ajouter que le nombre de «hits» et des «raques» peuvent être modifiés en définissant le facteur de charge.
@aioobe - qui modifie le nombre de collisions de hashtable. Mes "hits" et "rats" sont sur la question de savoir si la chaîne d'entrée peut être mappée (un coup) ou non (une miss). Le ratio Hit / Miss est en fait plutôt important si une liste est utilisée.
Je pense qu'un Lorsque vous faites Comme la mise en œuvre de la liste est Notez que vous pouvez définir hashmap sera toujours meilleur. Si vous avez n cordes chacune de la longueur au plus l , puis string #cockode et string # égale sont les deux O (l) (dans la mise en œuvre par défaut de Java, de toute façon).
Liste # indexof Il itière via la liste ( O (n) ) et effectue une comparaison sur chaque élément ( O (L) < / code>), pour donner o (nl) performance.
hashmap a (disons) r des godets, et chaque godet contient une liste liée. Chacune de ces listes est de longueur O (n / r) (en supposant que la méthode Hashcode distribue les cordes uniformément entre les godets). Pour rechercher une chaîne, vous devez calculer le hashcode ( o (l) ), recherchez le godet ( O (1) - un, pas l ) et itérer à la liste liée de ce godet ( O (n / r) éléments) faisant un O (l) comparaison sur chacun. Cela donne une heure de recherche totale de O (l + (nl) / r) .
o (nl) et la mise en oeuvre de hashmap est o (nl / r) (je dépose le premier l Comme il est relativement insignifiant), les performances de la recherche doivent être équivalentes lorsque r = 1 et le hashmap sera plus rapide pour toutes les valeurs plus grandes de R . .
R lorsque vous construisez le hashmap à l'aide de Ce constructeur (définissez le InitialCapacité sur R < / code> et le loadfactor argument sur n / r pour votre n et choisi r ).
Vous voudrez peut-être passer à
HASHMAP dans l'extrait de code exemple.Troisième option: Utilisez une énumération ( Stackoverflow.com / Questions / 604424 / ... ) et reportez-vous à la conjecture de la mise en œuvre sur laquelle est plus rapide (ou sa mise en œuvre interne hyper-optimisée, qu'elle peut ou non).
@AIOOBE: Merci, clarifié cela. @ T.J: Enum est une bonne idée, mais ne fonctionne que lorsque le mappage est déjà connu à la compilation.
Si vous utilisez les mêmes objets de chaîne dans l'application, String.Intern () et IdentityHashMap fourniront de bonnes performances. Cependant, vous doit stagiaire à vos chaînes et cette technique n'a de sens que si votre application vous permet de conserver ces références de chaîne afin que vous n'ayez besoin que de les internerez une fois que chacun.
@ide: interne (ou utiliser des littéraux à chaîne - ils sont automatiquement internés) est un point important. Si, maintenant que je regarde la mise en œuvre de HASHMAP, Equals () Vérifiez si seulement utilisé si S1.HASHCODE () == S2.HASHCODE && S1! = S2, un cas relativement rare (collision de hachage) si S1 et S2 sont internés. De plus, des instances de chaîne calculent leur code de hachage une seule fois et les cacheront par la suite. Ainsi, un hashmap ordinaire devrait fournir de très bonnes performances pour les chaînes internes.
Et à ajouter au précédent: au moins ArrayList # IndexOf () utilise toujours des égaux (), et bien que la chaîne # égale () a une vérification d'identité rapide pour la même identité (objets internes), tout ce qui est sans identité est soumis à une comparaison de caractères coûteuse. Se référant à ma question initiale, je pense que nous pouvons conclure qu'un hashmap est presque toujours un meilleur choix qu'une liste (tableau).
Mis à part: le coupable n'est pas seulement égal () - vous souhaitez éviter les appels HashCode () et peut-être la mémoire de mémoire de tous ces codes de hachage en cache. En pratique, j'ai mesuré une amélioration de 15% de la vitesse en commutant de hachemin à ItalyHashMap, mais il y a peu d'applications dans lesquelles il est applicable.