Android TreeMap blues... Are there alternatives?

Question

I've been trying to use TreeMaps on Android and ran into the following two issues:

1. Missing methods on older Android systems:
   When I try to run my app on my Android 2.2.2 test-device, it greets me with
   java.lang.NoSuchMethodError: java.util.TreeMap.lowerEntry
   Why? According to the documentation, TreeMap should be supported since API 1, no?
2. Absolutely abysmal performance on other devices (NOT TRUE, SEE UPDATE!):
   Even on very small trees with only 100 elements or so, operations take on the order of milli-seconds (!) to complete. Ouch...

Basically, I need a data structure that provides a super-fast map, "indexed" by a sparse integer-key (e.g. it contains entries for keys 2, 100, 29392, 399391, ...). It needs to be able to quickly perform the following operations:

• Add an entry to the map associated with an arbitrary integer key
• Find the entry associated with some integer key (or null if none found)
• Remove the key-entry pair from the map for a given key
• Iterate over the entries in the map
• Clear the map
• Return the entry corresponding to the largest key less than (or equal to) some number
• Return the entry corresponding to the smallest key bigger than or equal to some number

So, basically I need TreeMap's get, put, remove, values, clear, ceilingEntry or higherEntry, and lowerEntry or floorEntry. (For the last two either option is ok as one can be turned into the other simply by incrementing or decrementing the reference key by 1)

Are there any alternatives to TreeMap that perform well and are available either on all Android devices or I can include in my app?

UPDATE: I need to apologize to Android or whoever was involved in building the TreeMap: Due to some stupid logic-mistake, I was calling the TreeMap methods a whole bunch more times than I thought. The performance is actually perfectly fine. I was just being retarded... So, point 2 no longer is a concern. Leaves point 1. Sorry, everyone...

Answer 1

You can emulate some of the NavigableMap methods with some trickery. For example, ceilingEntry is approximately equivalent to tailMap(key).entrySet().iterator().next(), though it'll throw if there is no entry instead of returning null. (Just use hasNext() on the iterator to work around that.)

lowerEntry is harder; you can do headMap(key).lastKey() and call get on that to get the whole entry. higherEntry and floorEntry are harder still, but you've said that's not strictly necessary.