Menu
Hi I got a question on whether to use an ArrayList or HashMap.
I am trying to build a Paint program.
Each drawn object will be assigned a unique object ID.
If I want a fast retrieval speed when I click on an object, should I be using an arraylist or hashmap?
In general hashmap has O(1) while arraylist has O(n) retrieval speed.
However, I think for my case, since when I click on an object, I'll get the ID, hence the index of the array and I can do something like ArraylistObject.get(ithElement); , so in this case this will also be a O(1) retrieval process?
any inputs?
Thanks!
631
ArrayList stores the elements only as values and maintains internally the indexing for every element. While HashMap stores elements with key and value pairs that means two objects. So HashMap takes more memory comparatively.
The ArrayList has O(n) performance for every search, so for n searches its performance is O(n^2). The HashMap has O(1) performance for every search (on average), so for n searches its performance will be O(n). While the HashMap will be slower at first and take more memory, it will be faster for large values of n.
Array List can be converted into HashMap, but the HashMap does not maintain the order of ArrayList. To maintain the order, we can use LinkedHashMap which is the implementation of HashMap.
As a conclusion, we can learn, that the contains() method works faster in HashSet compared to an ArrayList. As usual, the complete code for this article is over on GitHub project.
If objects have an ID that can be mapped 1-to-1 to an array than that will be O(1) access as well, and in practice will be slightly faster than a hashmap lookup (you don't have to compute the hash).
However, the issue will be what happens when you delete an object. You will be left with a hole in the list. When creating new objects you can then keep appending to the list and leave it to get slowly more fragmented or try and find a spare slot in which case you'll be doing an O(n) search for a spare space.
In short - a hashmap is probably more appropriate.
184
On the plus side, you might be able to squeeze out a little extra performance by doing ArrayLists just right. But deleting objects is going to be a royal pain - as Paolo and Anurag said, you'll either have to put an empty placeholder (null ?) or to renumber some other other object to fill the gap. This is likely to result in performance bugs and plain old bugs.
HashMaps, on the other hand. Simple to use, decent performance guaranteed (unless you allocate your ids really badly).
And retrieving objects by id might not turn out to be your application's bottleneck at all. As the saying goes, premature optimization is the root of all evil.
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
