Is it inefficient to use nested Maps to sort and group data?

Question

I have a bunch of objects that I want to group (by category) and sort (by label). Would it be a bad idea to do something like this?

Map<String,Map<String,MyObject>> objMap = new HashMap();
for (MyObject o : getMyObjects()) {
    if (!objMap.containsKey(o.getCategory())) {
        objMap.put(o.getCategory(), new TreeMap());
    }
    objMap.get(o.getCategory()).put(o.getLabel(), o);
}

I like this because it is simple, but is there a better way?

EDIT: changed HashMap to TreeMap.

Maps are typically unsorted, unless you use something like a `TreeMap`. You could use a HashMap that contains a SortedSet/TreeSet and just pass in a `Comparator` that sorts the objects by label. — Marc Baumbach, Sep 02 '14 at 14:33
you could try some libraries too http://stackoverflow.com/questions/10804825/querying-in-memory-collection — Leo, Sep 02 '14 at 14:35
As far as grouping by category goes, that should be fine. However, HashMaps don't maintain ordering so you'll have to sort the labels manually unless you use a TreeMap or something. — Submersed, Sep 02 '14 at 14:35

score 1 · Answer 1 · answered Sep 02 '14 at 14:36

1

Since you mentioned you want the object to be sorted by labels

Map<String,Map<String,MyObject>> objMap = new HashMap();
for (MyObject o : getMyObjects()) {
    if (!objMap.containsKey(o.getCategory())) {
        objMap.put(o.getCategory(), new TreeMap());
    }
    objMap.get(o.getCategory()).put(o.getLabel(), o);
}

answered Sep 02 '14 at 14:36

bpgergo

15,669
5
44
68

Thanks. My original code was supposed to use `TreeMap`. – BLuFeNiX Sep 02 '14 at 14:39

score 1 · Answer 2 · edited May 23 '17 at 12:21

Whilst it doesn't directly answer your question with code, I think you should give a brief look as to when you should use Map VS List - There are multiple questions that kind of address this.

Option A: With List you have full control of your elements which would be much better for your case, all you have to do(if you even have to do so..) is implement your own grouping method for specific fields inside MyObject

Option B: Would be to use HashMap as it has it's own sorting methods to sort your objects label.

There are alot of options, however I'd like to clarify that Maps at essence, are unsorted, then there are variations such as TreeMap

Bottom-line is that this is a relatively broad question, you have multiple ways of doing it so experiment with ways that you find best, do note that if you wish to use Option B then you have to manually order your objects

Hope to have helped in some way or another

score 1 · Accepted Answer · answered Sep 02 '14 at 14:39

1

The inner map seems to be entirely useless, it should be a simple List:

Map<String, List<MyObject>> categoryMap = new HashMap<>();
for (MyObject o : objects) {
    String category = o.getCategory();
    List<MyObject> list = categoryMap.get(category);
    if (list == null) {
         list = new ArrayList<>();
         catgeoryMap.put(category, list);
    }
    list.add(o);
}

Note that I cleaned up your main loop to not look up category twice. For actually sorting the category lists, use a comparator that operates on label.

answered Sep 02 '14 at 14:39

Durandal

19,919
4
36
70

Thanks, `List` is a good idea. Also, `getCategory()` just returns a `String`, so I think using a temporary variable is less efficient. – BLuFeNiX Sep 02 '14 at 14:44
Actually, after some testing (http://ideone.com/MrlujS), you seem to be right that using the temporary variable is better. I thought it was better to just use a getter if it did nothing but return a value, but that doesn't seem to be the case. – BLuFeNiX Sep 02 '14 at 15:21
@BLuFeNiX Uhm, I don't think thats a really reliable benchmark (as most microbenchmarks); see how much it varies when you execute it repeatedly: http://ideone.com/HMVVmd – Durandal Sep 02 '14 at 16:11
I just ran it several times on a couple different machines. – BLuFeNiX Sep 02 '14 at 17:08

Kevin Workman · Answer 4 · 2014-09-02T14:49:19.077

Your question is "is there a better way?" and of course the only answer is: it depends. What are you trying to improve?

If you're trying to improve the time it takes to retrieve a particular MyObject, then using Maps is a fine way to go.

If you're trying to improve the memory usage, then there are several techniques you could use. You could stick with the Maps and use String interning as well as setting the size of the Maps, but that will only work if you know certain things ahead of time. You could get rid of the maps and use arrays instead, but then you sacrifice the ease of lookup time.

You could also use something like an in-memory Derby database, but that might be overkill for small tasks.

Have you actually encountered a problem with this code? If not, then you probably shouldn't worry too much about it, as premature optimization is the root of all evil.

The other thing to keep in mind is the ease of maintenance. If you switch to a multidimensional array, you might save a bunch of memory, but your code will be much more difficult to understand, maintain, and improve upon later.

In the end it's always a series of trade-offs, so whether you can "improve" this code depends entirely on what you want to improve.

Is it inefficient to use nested Maps to sort and group data?

4 Answers4