I have a use case for a

Map<Int, String>

. Each map has only a small handful of entries. I need to keep many thousands of these maps in memory. 99% of the time the

Int

key is small, between 1 an 10. If it was guaranteed to always be that small, the most efficient implementation of such a map would use an

Array<String?>

. However, 1% of the time there would be a key that would be a very large integer, so a simple array is unusable. Yet if I use a

HashMap

or

TreeMap

I would be wasting memory for 99% of the time by using a sub-optimal implementation. Is there any specialized Map that uses a strategy of changing internal implementation depending on the value of the key?

Android has https://developer.android.com/reference/android/util/SparseArray You could take inspiration from that for building your own.

Are you going to be reading from it a lot more than inserting? I think there could be a simple solution utilising multiple lists

Thanks, everyone, for your replies, all of which are helpful. I had already thought of sparse arrays but only in passing, dismissing them as being typically implemented using a map anyway. But Android's implementation is indeed more memory-efficient. Youssef, I would indeed be reading a lot more than inserting: in fact, they're immutable maps, creating them once and storing them in a cache and never changing them again. So a solution using multiple lists would indeed be good. Are you thinking of a list of Int keys and a list of String values at the corresponding indices? I would consider that, if measured footprint of the cache becomes an issue.

Yep indeed I was trying to design such a solution with a list of strings and then a list of the "true" Int keys after the first 10. If it's immutable that simplifies the implementation a lot actually. I'll polish up what I have so far and post it here.