Iterator VS HashMap<String, Object> in JAVA

Question

Lets say that we have a collection of items. Which of the two is faster?

HashMap<String, ObjectFoo> hashmap = new HashMap<String, ObjectFoo>();
/* .... add elements .... */
ObjectFoo theElement = hashmap.get("nameOfObject");

Or

ArrayList<ObjectFoo> arraylist = new ArrayList<Object>();
/* .... add elements .... */
Iterator<ObjectFoo> itFoo = arraylist.iterator();
ObjectFoo obj;
while(itFoo.hasNext()) {
  obj = itFoo.next();
  if (obj.name.equals("nameOfObject")) return obj;
}

Suppose that:

public class ObjectFoo {
  public String name;
}

The only reason hashtables exist is the speed of random access. So take a guess. — Marko Topolnik
– Marko Topolnik, Commented Aug 30, 2015 at 13:22

Sharon Ben Asher · Accepted Answer · 2015-08-30 13:09:37Z

2

The HashMap is (alsmost always) faster. If you know Big O notation then using HashMap is O(1) while using (unsorted) ArrayList is O(n)

answered Aug 30, 2015 at 13:09

Sharon Ben Asher

14.5k6 gold badges35 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Pshemo · Accepted Answer · 2015-08-30 13:31:50Z

1

HashMap stores key-value paris in buckets based on hashcode of key. Buckets are organized with array and accessing array is O(1).

So when you call hashmap.get("nameOfObject"); it calculates hashcode of key and then picks bucket with elements containing pairs where key has same hashcode as hascode of key used as argument.

Sometimes there will be more few key-value pairs which key has same hashcode. In that cases map will need to iterate over them and check if our key is equal to key in that pair, but since number of elements with same hashcode is very small iterating over them is way faster than iterating over all elements stored in map.

edited Aug 30, 2015 at 13:31

answered Aug 30, 2015 at 13:18

Pshemo

125k26 gold badges194 silver badges280 bronze badges

Collectives™ on Stack Overflow

Iterator VS HashMap<String, Object> in JAVA

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related