Performance: Creating an ArrayList from HashMap.values()

Question

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.

Answer 1

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.

Answer 2

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 )