22

Perhaps there's a name for what I want, but I'm not aware of it. I need something similar to a LinkedHashMap in Java, but where it returns the 'previous' value if there's no value at the specified key.

That is, I have a list of objects stored by an integer key (which is in units of time in my case):

; key->value
10->A
15->B
20->C

So, if I were to query for a value for key 0-9, it would return null. The special part is if I queried for something 10 <= i <= 14 it would return A. Or, for i >= 20, it would return C.

Is there a data structure for this?

Improve this question
2
  • I don't know if there is an implemented one but you could probably extend the existing one to do this. Whether it will meet your performance goals or not without a rewrite I don't know...
    – Rig
    Oct 3, 2013 at 19:11
  • 1
    +1 for the great question. Most people with three low-digit rep ask the "please do my homework" type of question. Not the case here.
    – Tulains Córdova
    Oct 3, 2013 at 19:30

2 Answers 2

Reset to default
33

You are looking for a NavigableMap. This is a subtype of SortedMap that also has some functions available besides the nature of the map being sorted. Note that the Navigable map "is intended to supersede the SortedMap interface." (Java SE 6 Collections Framework Enhancements). Everything that currently implements SortedMap implements NavigableMap and this is likely to remain true.

In particular, the method floorKey(K key) which "returns the greatest key less than or equal to the given key, or null if there is no such key.

This is just one of many methods that allow you to get specific keys or submaps of the map.

  • ceiling / floor (the entry that is higher / lower than the parameter)
  • access of keys or map in descending order
  • head / tail (the entries less / greater than a given key)
  • higher / lower (the next key that is higher or lower than parameter)
  • submap (given two keys, return the map that is between the two keys)

Java has two implementations of the NavigableMap - the TreeMap and the ConcurrentSkipListMap.

If you look at the idea/implementation of a skip list you will see why it would work really well with such a structure and its queries.

Improve this answer
6
  • 1+ great answer. Never thought such an specific Map existed in the Java API.
    – Tulains Córdova
    Oct 3, 2013 at 19:31
  • @user61852 My favorite datatype is the skip list and I poked around with it. When I saw it implemented in 1.6 I looked into what all it provided and noticed the interfaces that it had and thus my familiarity with it.
    – user40980
    Oct 3, 2013 at 19:33
  • That's the kind of things that convince me Java is one of the best designed languages you can find.
    – Tulains Córdova
    Oct 3, 2013 at 19:35
  • 1
    Note that while this appears to address OP's issue, it doesn't act like the LinkedHashMap that he mentions. Neither TreeMap nor ConcurrentSkipListMap are ordered by insertion time like LinkedHashMap, rather they are ordered by a Comparator or the key's Natural Ordering if they implement Comparable.
    – MikeFHay
    Oct 4, 2013 at 12:02
  • 1
    Very good point. The floor operation is what I was looking for, the comparator I can add easily. And in my case it works out much nicer to implement the comparator instead of reinventing the wheel. Thanks.
    – Nick
    Oct 4, 2013 at 12:58
1

What you are looking for is a symbol table that supports ordered operations. And in your case it is the floor operation.

The hash implementation of a symbol table is the fastest, but it doesn't offer those ordered operations.

But tree implementation of symbol tables does. An example of that in Java is the TreeMap class

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.