Menu
Question is how much it costs to create an ArrayList from a HashMap.values() Collection? Or creating the values Collection alone? Assuming Map.size() > 100k. Objects could also be held in ArrayList (instead of HashMap) all the time which has implications in other parts (modifications of elements, easy by key). The ArrayList is used to iterate over every n-th element. (That's why the values collection can't be used directly). No modifications are done during the iteration.
220
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.
A HashMap contains key-value pairs, there are three ways to convert a HashMap to an ArrayList: Converting the HashMap keys into an ArrayList. Converting the HashMap values into an ArrayList.
The reason that HashMap is faster than HashSet is that the HashMap uses the unique keys to access the values. It stores each value with a corresponding key and we can retrieve these values faster using keys during iteration. While HashSet is completely based on objects and therefore retrieval of values is slower.
In order to optimize the performance of ArrayLists, it is advisable to set a large enough initial capacity when initializing an ArrayList to incorporate all your data. This will allocate a large enough chunk of memory so that you will probably not need to perform the allocation process again.
HashMap.values() doesn't return an ArrayList of values but a Values Collection.
Source:
public Collection<V> values() { Collection<V> vs = values; return (vs != null ? vs : (values = new Values())); } Values is an AbstractCollection. The reason for values is just to reference HashMap's iterator.
Your question:
Question is how much it costs to create an ArrayList from a HashMap.values() Collection?
That's a linear complexity (as Bozho said) since
ArrayList<V> valuesList = new ArrayList<V>(hashMap.values()); the ArrayList, valuesList calls the collection hashMap toArray() method which essentially does a for loop from 0..N (size) element in the collection.
Hope this helps.
114
HashMap internally stores values in a Collection values. Take a look at the source code of AbstractMap, the parent of HashMap.
So HashMap.values() directly returns a Collection. There is no computation or data copying done. It's as fast as it can be.
Just get the values and then do a for loop:
int n = 5; // every 5th element Object[] values = hashMap.values().toArray(); int size = values.length; for (int i = 0; i < size; i += n){ values[i]; // do something ) 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
