Performance: Creating an ArrayList from HashMap.values()

arraylist, collections, hashmap, java, performance

Solution

`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.

Problem

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.

Original source