I have a use case for a `Map<Int, String>`. ...

# getting-started

[Klitos Kyriacou]

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?

[Ruckus]

Have you tried it yet to see if there is an issue with the map implementation? This sounds like the kind of thing you should just implement in the most straight forward way, and only worry about changing if problems manifest.

[Ruckus]

If memory does become a concern, it wouldn't be too hard to roll your own implementation that is essentially a list of entries (class Entry(val index: Int, val value: String)). If the number of entries is small, a simple linear search for access should be good enough. Otherwise, you could manually keep it sorted by index and do a binary search.

[mkrussel]

Android has https://developer.android.com/reference/android/util/SparseArray

You could take inspiration from that for building your own.

[Youssef Shoaib [MOD]]

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

[Klitos Kyriacou]

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.

[Youssef Shoaib [MOD]]

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.