1

I need a data structure that will perform both the role of a lookup map by key as well as be able to be convertable into a sorted list. The data that goes in is a very siple code-description pair (e.g. M/Married, D/Divorced etc). The lookup requirement is in order to get the description once the user makes a selection in the UI, whose value is the code. The sorted list requirement is in order to feed the data into UI components (JSF) which take List as input and the values always need to be displayed in the same order (alphabetical order of description).

The first thing that came to mind was a TreeMap. So I retrieve the data from my DB in the order I want it to be shown in the UI and load it into my tree map, keyed by the code so that I can later look up descriptions for further display once the user makes selections. As for getting a sorted list out of that same map, as per this post, I am doing the following:

List<CodeObject> list = new ArrayList<CodeObject>(map.values());

However, the list is not sorted in the same order that they were put into the map. The map is declared as a SortedMap and implemented as a TreeMap:

SortedMap<String, CodeObject> map = new TreeMap<String, CodeObject>().

CodeObject is a simple POJO containing just the code and description and corresponding getters (setters in through the constructor), a list of which is fed to UI components, which use the code as the value and description for display. I used to use just a List and that work fine with respect to ordering but a List does not provide an efficient interface for looking up a value by key and I now do have that requirement.

So, my questions are:

  1. If TreeMap is supposed to be a map in the ordered of item addition, why isn's TreeMap.values() in the same order?
  2. What should I do to fulfill my requirements explained above, i.e. have a data structure that will serve as both a lookup map AND a sorted collection of elements? Will TreeMap do it for me if I use it differently or do I need an altogether different approach?
Community
  • 1
  • 1
amphibient
  • 29,770
  • 54
  • 146
  • 240
  • 5
    I think you are confusing `TreeMap` with `LinkedHashMap`. – davide Mar 18 '15 at 20:40
  • 2
    TreeMaps aren't ordered by insertion order. – user2357112 Mar 18 '15 at 20:40
  • I was always told that TreeMap guarantees the order of entries in which they were added – amphibient Mar 18 '15 at 20:40
  • "If TreeMap is supposed to be a map in the ordered of item addition", how did you reach that conclusion? – the8472 Mar 18 '15 at 20:40
  • @T.J.Crowder -- how is "addition" different from "insertion" ? – amphibient Mar 18 '15 at 20:45
  • 1
    @amphibient: What I meant was that the order `TreeMap` guarantees isn't the order of addition/insertion/whatever you want to call it. At all. `TreeMap` sorts by the *natural order of the keys* -- that is, `compareTo`-style. So say your keys are strings. The sort will be (largely) alphabetic. Or say they're numeric: The sort will be by number. – T.J. Crowder Mar 18 '15 at 20:48
  • well, that is not the order in which they were added. but i get it – amphibient Mar 18 '15 at 20:50
  • 1
    @amphibient: My original comment above (now deleted) was really poorly-phrased. Sorry for the confusion. What I meant was that it guarantees **an** order, but the order it guarantees is not the order of addition/insertion. – T.J. Crowder Mar 18 '15 at 20:55
  • I figured. Thanks for the clarification – amphibient Mar 18 '15 at 21:03
  • @amphibient If you were always told that, you were misinformed. I suggest you misunderstood, or got confused with LinkedHashMap. If TreeMap was meant to behave as you describe, it would be documented, and it isn't. – user207421 Mar 18 '15 at 21:17

3 Answers3

4

TreeMap maintain's the key's natural order. You can even order it (with a bit more manipulation and custom definition of a comparator) by the natural order/reverse order of the value. But this is not the same as saying "Insertion order". To maintain the insertion order you need to use LinkedHashMap. Java LinkedHashMap is a subclass of HashMap - the analogy is the same as LinkedList where you maintain the trace of the next node. However, it says it cannot "Guarantee" that the order is maintained, so don't ask your money back if you suddenly see an insertion order is maintained with HashMap

ha9u63a7
  • 6,233
  • 16
  • 73
  • 108
3

TreeMap's documentation says:

The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

So unless you're providing a Comparator and tracking the insertion order and using it in that Comparator, you'll get the natural order of the keys, not the order in which the keys were inserted.

If you want insertion order, as davide said, you can use LinkedHashMap:

Hash table and linked list implementation of the Map interface, with predictable iteration order...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.

Community
  • 1
  • 1
T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
3

What you need is LinkedHashMap See another question as well.

Community
  • 1
  • 1
Piotr Gwiazda
  • 12,080
  • 13
  • 60
  • 91