Ordered list in HashMap Java

Question

I am in need of a data structure, like:

Map<String, List<Profile>> profilePool;

What I need is the list to each key should be sorted. I can do it manually while doing profilePool.put() using some compare objecst on some attribute to keep the list ordered against the key. But can we have a compare function attached to the List<> so that whenever a object is inserted into the list, it should place it at a specific index, maintaining the order?

Or do we have any other data structure, easy to use and does the same task?

When you don't have duplicate elements, a `TreeSet` might work — SilverNak, Jul 11 '17 at 14:21
[Why is there no sorted list in Java?](https://stackoverflow.com/questions/8725387/why-is-there-no-sortedlist-in-java) — Andy Turner, Jul 11 '17 at 14:21
@SilverNak Thanks. But unfortunately I can have duplicate elements. — impossible, Jul 11 '17 at 14:23

davidxxx · Answer 1 · 2017-07-11T15:09:55.343

3

Java doesn't provide it out of the box.
If it is worthy, you could create your own wrapper SortedList class that implements List.

At each time you add an element in it, you could identify the insertion position to use with a binary search and push the new value into this position.

edited Jul 11 '17 at 15:09

answered Jul 11 '17 at 14:25

davidxxx

125,838
23
214
215

"Java doesn't provide it out of the box" If this is the case then, I got my answer. I would have to either implement `List` or find out some other way to do it. Thanks. – impossible Jul 11 '17 at 14:28
@GhostCat You are right. It would not be as much as efficient to sort it even if `Collection.sort()` should be relatively fast as the List is already sorted. – davidxxx Jul 11 '17 at 15:11
Well, reality is again complicated. See https://stackoverflow.com/questions/168891/is-it-faster-to-sort-a-list-after-inserting-items-or-adding-them-to-a-sorted-lis for example. – GhostCat Jul 11 '17 at 15:13
@Impossible, You are welcome. You could also use a `TreeSet` if the `Set` interface and constraints suit to your requirement. – davidxxx Jul 11 '17 at 15:15
plus one for suggesting to implement List using a wrapper instead of extending ArrayList – JacksOnF1re Jul 11 '17 at 15:16

score 1 · Answer 2 · answered Jul 11 '17 at 19:16

If duplicate elements (based on .equals()) are fully interchangeable, you could use Guava's SortedMultiset. It only stores one instance of each duplicate element, and the iterator will return that same instance multiple times. That technicality aside, it can function the same as a SortedList.

Map<String, SortedMultiset<Profile>> profilePool;

Ordered list in HashMap Java

2 Answers2