https://kotlinlang.org
Join Slack
Hi everyone! I'm looking for some advice about choosing collection data structure. So I'm trying to ...
# general-advice
s
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?
e
as of https://developer.android.com/jetpack/androidx/releases/collection#1.3.0-alpha03 androidx.collection is available for non-android targets
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
s
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.
e
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
take your pick
(perfect hashing wastes no space and is optimally fast, but requires pre-computation)
👍 1
s
Looking to TIntObjectMap I found this https://github.com/vigna/fastutil repo. Looks very interesting
3 Views
Open in Slack
PreviousNext
Powered by

kotlinlang

A modern programming language that makes developers happier.

Powered by