1

I have a HashMap.

It has 100s of millions of observations.

What's the best way to iterate over the elements of the HashMap, in numerical order of the keys?

I considered changing to TreeMap, but did not do that since it may actually increase the load in creating the Map (as TreeMap is O(n), HashMap is O(1)).

KalEl
  • 8,978
  • 13
  • 47
  • 56
  • 2
    This problem is pretty complicated: (1) `HashMap` is unordered; you'll probably want `TreeMap` or create your own structure (2) hundreds of millions of observations is likely to blow past the memory you have in a single system. In choosing a data structure, consider which operations you'll be performing most often and optimize for those cases. Keep in mind - unless your data is already sorted, you'll never get sorting O(1) – Krease Jan 23 '15 at 19:33
  • 1
    Are the keys consecutive numbers? If not, then you'll have to do something sorting-shaped, which is going to cost no matter what. – Louis Wasserman Jan 23 '15 at 19:34
  • You want a LinkedHashMap. See here: http://stackoverflow.com/questions/3478061/does-javas-linkedhashmap-maintain-the-order-of-keys – Jared Burrows Jan 23 '15 at 20:07

3 Answers3

5

With Java 8 you could use something similar to the following:

import static java.util.Comparator.comparing;

map.entrySet().stream()
   .sorted(comparing(Entry::getKey))
   .forEach(e -> doSomethingWithTheEntry(e));

That will obviously involve sorting the unsorted keys, which will come at a cost. So you need to decide whether you want to pay the cost upfront with a TreeMap or when required and keep using a HashMap.

assylias
  • 321,522
  • 82
  • 660
  • 783
  • Thanks... This looks like a viable solution. I evaluated both, and looks like TreeMap doesn't really have much performance hit, so finally ended up using that. – KalEl Jan 23 '15 at 20:40
3

You can't iterate over a HashMap in order. You'll have to use TreeMap for that. If you use a LinkedHashMap, you can iterate in the order the keys were inserted to the Map, but it's still not what you want (unless you insert the keys in numerical order).

Magnilex
  • 11,584
  • 9
  • 62
  • 84
Eran
  • 387,369
  • 54
  • 702
  • 768
2

If your insertion order is the same order as your keys, then you could use a LinkedHashMap.

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)

NESPowerGlove
  • 5,496
  • 17
  • 28