de Javadoc: Si c'est le cas, alors pourquoi ne fournit-il pas l'accès objet comme une liste de java,
list.get (index);
J'avais mis en œuvre le cache LRU en utilisant LinkedHashMap. Mon algorithme m'a demandé d'accéder à l'objet LRU depuis le cache. C'est pourquoi j'ai besoin d'un accès aléatoire, mais je pense que cela me coûtera de mauvaise performance, j'ai donc changé la logique et j'accède à l'objet LRU juste lorsque le cache est plein ... Utilisation de refugeLDestEntry ()
Merci à tous ...
Tableau de hachage et mise en oeuvre de la liste liée de l'interface de la carte, avec ordre d'itération prévisible. Cette implémentation diffère de HASHMAP en ce sens qu'elle conserve une liste doublement liée à travers toutes ses entrées.
6 Réponses :
a) strong> car les entrées sont liées, non accessibles au hasard. La performance serait misérable, b) strong> car il n'y a pas d'interface pour sauvegarder cette fonctionnalité. Donc, le choix serait d'introduire une interface dédiée juste pour cette implémentation (mal interprétant) ou de demander aux clients de programmer des classes de mise en œuvre au lieu d'interfaces p> BTW avec O (n) code> si je ne suis pas en erreur.
Iterables.get(map.values(), offset);
Merci Sean. J'utilise LinkedHashMap pour la mise en œuvre de Cache LRU ... et je voulais une fonctionnalité à l'objet de la LRU peek ... mais je suppose que itération sur la carte serait très mauvaise performance ... Connaissez-vous toute autre structure de données pour une telle fonctionnalité?
+1, bonne réponse. Cependant, il convient de noter que cela ne serait pas pire que la performance fournie par, disons, linkedlist , donc je ne vois donc pas vraiment l'argument.
@Eternal noob, il dit dans les docs: Ce type de carte est bien adapté à la construction de caches Lru. et, itération sur la carte est aussi efficace que possible (Au))
@AIOOOBE C'est pourquoi LinkedList ne met pas en œuvre randomaccess
Il fournit une interface itérateur , chaque nœud de la liste est lié à celui avant de cela et après elle. Avoir une méthode Si vous avez besoin de cette capacité qui n'est pas très performante, je suggère d'étendre vous-même la carte vous-même get (i) ne serait pas différent de l'itération sur tous les éléments de la liste, car il n'y a pas de matrice de support (identique que LinkedList ).
Donc, dans la liste liée, chaque fois que nous accédons au dernier élément, list.get (liste.Size () - 1), est-ce un accès aléatoire ou O (n) (tous les éléments sont itérais)?
Il fournit une interface itératrice qui n'est pas correcte. L'entrée de la carte () fournit l'itérateur, pas la carte elle-même (mais en dehors de cela, vous avez raison)
@Eternalnoob C'est un ancien commentaire, mais pour les futurs lecteurs, il convient de répondre à votre ancienne question: la linkedlist connaît sa taille et ira déterrer en arrière lorsque vous accédez à un index d'élément supérieur à la moitié de la liste. Ainsi, l'accès au dernier élément est aussi bon marché pour accéder au premier élément. Seuls les éléments au milieu ont les dépenses d'itération.
Veuillez regarder Apache Commons LinkedMap
C'est bien de connaître ces collections personnalisées, mais elles sont rarement utiles. Si vous en avez besoin, vous avez généralement une faille de conception dans votre code quelque part :-)
Pendant que vous pêchez sur Apache Commons, pour une carte LRU, essayez Lrumap.
Etant donné que peut-être pas très efficace (surtout de mémoire) , mais il devrait être BTW, je pense que la question est légitime pour tous les i Déterminé à faire un c'est juste Une réflexion, et honnêtement, je trouve aussi gênant que le valeurs () fournit une collection de support des valeurs, vous pouvez le résoudre comme ceci: o (n) comme vous pouvez vous attendre à ce que ce soit.
Liste < / code> opérations. (Il ne devrait pas être plus lent que linkedlist quand même, non?) linkedhashmaplist qui étendue le linkedhashmap < / code> et implémenté l'interface list . Étonnamment, il semble impossible de faire, en raison de l'affrontement pour enlever. La méthode existante Supprimer renvoie l'objet mappé précédemment, tandis que la liste list.remove.remove doit renvoyer un booléen . linkedhashmap ne peut pas être traité plus comme un linkedlist .
Ya, j'ai vu ça aussi ... Supprimer () La méthode de LinkedHashMap est originaire de HASHMAP, car LinkedHashMap étend HASHMAP ... et cela est conflictuel avec la suppression de la liste () ...
Si vous voulez un accès aléatoire, vous pouvez faire
Map<K,V> map = new LinkedHashMap<K,V>(); Map.Entry<K,V>[] entries = (Map.Entry<K,V>[]) map.toArray(new Map.Entry[map.size()]); Map.Entry<K,V> entry_n = entry[n];
Il n'y a pas de problème réel pour créer une carte avec logement (n) efficacité de l'accès par index. Si vous utilisez un arbre noir rouge et que vous magasinez pour chaque nœud, le nombre d'éléments dans l'arborescence commence à ce nœud, il est possible d'écrire une méthode Obtenir (Int Index) qui connecte (n).
Cela ne semble pas répondre à la question.