Re: Sort Map on Value
On Tue, 25 Aug 2009, Wojtek wrote:
I have a Person object. It contains a pKey (unique) and a name (may
repeat, ie John Smith). The Person object will be held in a collection.
New (or old) people will be added in any order, however I want the
output to be sorted by name. Since the name can repeat I cannot use it
as a key, instead I want to use the pKey.
Normally (sorted on the key) I would use a TreeMap, but I want to use
the key to find a Person, yet sort on the Perons name:
TreeMap<String,Person> people = new TreeMap<String,Person>();
...
Person addPerson(String pKey, String name)
{
Person person = people.get(pKey);
if ( person == null )
{
person = new Person(pKey,name);
people.put(pKey,person);
}
return person;
}
I thought of creating my own Comparitor, however the TreeMap insists that the
comparitor needs to sort on the String (pKey) rather than the value (Person).
I know I can:
- use two collections, one which is used for lookup the other for sorting
- ignore the TreeMap and use a simple Map, then array sort the
values().toArray(). (Thanks Roedy)
- make a key which is the (name + pKey) but this would create large keys.
They wouldn't be large - you could write a little class which holds a
reference to a pKey and a name; since these are both part of the Person
anyway, the overhead of the key object is just an object header and two
pointers. Cheap as chips!
The problem is that there's no way to do lookups just by pKey - you'd need
to know the name to be able to make a key to do a lookup. Since the
comparison would have to be by name, with ties being broken by pKey,
there's no way to cheat and do a lookup just with the pKey (without doing
a linear search).
I was hoping there was a more elegant way.
Do you allocate the pKeys? If there was a way to allocate them such that
they were monotonic with the names, then you could just use the pKeys as
keys, and a map sorted by pKey would be sorted by name too. A simple way
to do this would be to make the pKeys a name with a per-name counter
appended to the end. If you're worried about size, compress the name
somehow (i posted a funky coding scheme that is basically order-preserving
Huffman a while ago), although this may be too complicated. Or just use
the little pair class mentioned above.
You could copy and paste LinkedHashMap, and modify it to keep its linked
list in sorted order (using a supplied Comparator), rather than insertion
order. That would involve an O(n^2) sort, though, which would lose heavily
if you do a large proportion of puts.
tom
--
There are many ways of going crazy, but the most valuable of them is
this one which makes a genius out of an ordinary man. -- Claudio Grondi