Hi everyone! I'm looking for some advice about cho...

# general-advice

[Stanislav Maksimov]

Hi everyone! I'm looking for some advice about choosing collection data structure. So I'm trying to figure out which data structure could I use instead of HashMap. Right now I have HashMap with several thousand elements in it. Map is created once and after that there are no modifications on it. Also final map size is known during compilation. My biggest problem with it right now is I have Int keys, so a lot of boxing happens. Main priority for usage is lookup performance. Maybe someone knows some clever algorithm or data structure for lookup table with integer keys?

[ephemient]

https://developer.android.com/reference/androidx/collection/SparseArrayCompat

[ephemient]

as of https://developer.android.com/jetpack/androidx/releases/collection#1.3.0-alpha03 androidx.collection is available for non-android targets

[ephemient]

in the pure Java world, there's also https://trove4j.sourceforge.net/javadocs/gnu/trove/map/TIntObjectMap.html

[ephemient]

also, if your keys are all known in advance, search "perfect hashing". I haven't seen an implementation for Kotlin but the language doesn't really matter

[Stanislav Maksimov]

Know about SparseArray. I'm somewhat concerned about this paragraph from documentation

The implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary search and adds and removes require inserting and deleting entries in the array.

[ephemient]

right, android's SparseArray a packed binary search tree, which minimizes space at some time cost. whereas TIntObjectHashMap is a hashmap, which wastes space to save time

[ephemient]

take your pick

[ephemient]

(perfect hashing wastes no space and is optimally fast, but requires pre-computation)

[Stanislav Maksimov]

Looking to TIntObjectMap I found this https://github.com/vigna/fastutil repo. Looks very interesting