-1

What's the fastest way how to iterate over linked hash map, I need 100 last keys and first 20 keys. The size of this map will be in most cases over 500-1500, thanks

 LinkedHashMap<Integer, Float> doc_1 = service5.getMatchingValue(query);
marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
Daniela Agelova
  • 53
  • 2
  • 7
  • 1
    possible duplicate of [How do I iterate over each Entry in a Map?](http://stackoverflow.com/questions/46898/how-do-i-iterate-over-each-entry-in-a-map) – Luiggi Mendoza Oct 27 '13 at 18:01
  • 1
    If you are concerned about speed you shouldn't be iterating over a HashMap. That is not what they are designed for. Use a collection like List instead. BTW I wouldn't use `float` or `Float` if you can help it. `double` or `Double` has 9 digits more precision. – Peter Lawrey Oct 27 '13 at 18:02
  • 1
    How often will you be replacing this map? Is it a retrieve once and iterate x times kind of operation? – arynaq Oct 27 '13 at 18:09
  • you need [thread](http://arashmd.blogspot.com/2013/06/java-threading.html) dude. –  Oct 27 '13 at 18:17
  • @user2511414 using a thread would be too overkill for this problem =\ – Luiggi Mendoza Oct 27 '13 at 18:20
  • @PeterLawrey: I've always found it strange that LinkedHashMap didn't provide useful iteration methods though, since it already maintains a doubly linked list. It could easily provide a reverse-order entry iterator, but doesn't. Any thought about that? – JB Nizet Oct 27 '13 at 18:20
  • @JBNizet It appears to me that it could support ListIterator. The problem is that LHM does give you any iterator. It is Collection which gives this and you would need to provide a special ListSet or ListCollection or something equally bizarre to return a ListIterator. – Peter Lawrey Oct 27 '13 at 18:24
  • @LuiggiMendoza prove me I'm wrong buddy. –  Oct 27 '13 at 18:24
  • 1
    @user2511414 Using thread rarely speeds up simple tasks. esp if they have no level of inherent concurrency. There is no reason to suspect threads would help so you would have to clarify what approach you propose and why. It is very easy to provide a slow solution if it is not optimal so this is not a proof. – Peter Lawrey Oct 27 '13 at 18:27
  • @PeterLawrey: I was thinking about something simpler, like `Iterator> reverseEntryIterator()` and `Iterator reverseKeyIterator()`. You can iterate through the list in normal using `map.keySet().iterator()` and `map.entrySet().iterator()`, but there is no way to iterate in reverse order (AFAIK). – JB Nizet Oct 27 '13 at 18:36
  • @JBNizet Agreed. Even reverseValuesIterator(), however ListIterator would be more powerful. – Peter Lawrey Oct 27 '13 at 18:49

1 Answers1

2

If you iterate over a HashMap you still would have O(n) runtime, as you would iterating over any other datastructure...

Iterating over a HashMap is just as time consuming as iterating over any DS.

If you only need specific entries of a hashmap, you might want to keep information on the required keys and only loop over those keys. Access to an element in a HashMap using its key is O(1) (or atleast amorized), accessing M entries (by their keys) using direct access results thus in O(M) runtime with O(M) << O(N).

You could perhaps keep the last 100 keys in a cache and just loop over (a copy) of the cache to have the best possible access (in terms of performance) in combination with your HashMap.

Madsen
  • 396
  • 1
  • 2
  • 12