Also for most reasonable data structures, especially on a mobile phone, the difference between O(N) and O(log(N)) is just not that much. In fact, I would argue that for most typical uses it will be far made up for by the much less complicated code and internal data structure (another advantage of SparseArray -- it doesn't need to allocate an extra entry object for every mapping it contains, nor resize a hash table as the amount of items changes).
Then again, I've always been very partial to ordered arrays over hash maps. :) On Tue, May 19, 2009 at 4:47 PM, Romain Guy <[email protected]> wrote: > > HashMap can indeed be faster than SparseArray. However, and this is > very important, SparseArray does not require boxing/unboxing of > primitive types which prevents allocations and thus prevents the GC to > stop your games for hundreds of milliseconds. That is much more > valuable :) > > On Tue, May 19, 2009 at 3:04 PM, TjerkW <[email protected]> wrote: > > > > I need a map from int to certain objects. I wanted to use the HashMap, > > but in the documentation of SparseArray > > it says that SparseArray is intented to be *more efficient*: > > http://developer.android.com/reference/android/util/SparseArray.html > > > > However i think the documentation is not entirely correct and needs > > more info: > > When reviewing the sourcecode of SparseArray and comparing it with the > > HashMap i come to the following conclusion > > > > Source code of Sparse Array: > > > http://android.git.kernel.org/?p=platform/frameworks/base.git;a=blob_plain;f=core/java/android/util/SparseArray.java;hb=HEAD > > > > For SpareArray: > > Time complexity for reads and writes on a map of size N is log2(N) + > > 1, > > > > However the time complexity for a HashMap of size N is C*N (where C is > > a constant) > > (according to the javadoc > http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashMap.html) > > > > So maybe SparseArray is more efficient with respect to space > > complexity it is not for time complexity. > > So for programs that need high performance a HashMap may be better. > > > > At least thats what i think. Am i right? Am i wrong? > > I need a very fast implementation for my game :-) > > > > > > > > > > > -- > Romain Guy > Android framework engineer > [email protected] > > Note: please don't send private questions to me, as I don't have time > to provide private support. All such questions should be posted on > public forums, where I and others can see and answer them > > > > -- Dianne Hackborn Android framework engineer [email protected] Note: please don't send private questions to me, as I don't have time to provide private support, and so won't reply to such e-mails. All such questions should be posted on public forums, where I and others can see and answer them. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/android-developers?hl=en -~----------~----~----~----~------~----~------~--~---
