CODEWITHSUNDEEP
javaperformancecollectionsarraylisthashmap
beginner_
beginner_

Reputation: 331

Performance: Creating an ArrayList from HashMap.values()

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.

Upvotes: 22

Views: 43505

Answers (5)

Bozho
Bozho

Reputation: 597106

You can use an Iterator to skip elements - just call next() many times.

Creating a list of any collection has a linear complexity.

Upvotes: 3

Buhake Sindi
Buhake Sindi

Reputation: 89169

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.

Upvotes: 42

Peter Lawrey
Peter Lawrey

Reputation: 533520

To elaborate on @Bozho's solution you can just do.

int count = 0;
for(Value value: map.values())
   if(count++ % 5 == 0)
     // do something.

Upvotes: 3

Peter Knego
Peter Knego

Reputation: 80340

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
)

Upvotes: 9

luckyluke
luckyluke

Reputation: 1563

You can create Your own HashMap, that holds the Arraylist collection of values directly (i do not believe that HashMap does it for free, the data structure for it is different). But this requires some additional coding from Your side.

Upvotes: 0

Related Questions