CODEWITHSUNDEEP
javaperformancearraylisthashmap
Ankur
Ankur

Reputation: 51100

HashMap vs ArrayList performance am I correct

I currently believe that:

Am I generally correct? Are there situations where this is not correct?

Upvotes: 37

Views: 82409

Answers (6)

stolsvik
stolsvik

Reputation: 5341

A Map is a map, or "associative array". It has a key->value layout. A List is on the other hand a list, which is an ordered collection of elements.

A more direct comparison would possibly be between Set and List: Both these hold values, where the list is explicitly ordered (you can get element # x), and the set is (typically) not ordered (well, unless it is an SortedSet, in which case iteration order will be ordered by a Comparator).

The two most common implementations for Set and List is HashSet and ArrayList. To check if an element belongs in an arraylist (contains(element)), the implementation iterate over all the elements of it, checking whether one have found the element using the equals() method. To check if an element belongs in a hashset, first the element's hashCode() is calculated, then one goes "directly" to the position where this element should reside, and checks if it is there.

Thus, a significant difference between ArrayList and HashSet is the speed of contains().

On a list, you can ask for element# x, in addition to what you can do on a set, which is add, remove, ask-whether-present (contains), and iterate over all elements.

On a map, you can ask for an element by its key, instead of by its index as you do with a list.

A HashSet is currently implemented simply by a HashMap where the value part of the key->value relationship is not used. This is completely absurd and has no use whatsoever other than wasting at least 4 bytes, on could argue 12, for every and all elements inserted in the HashSet.

Upvotes: 51

aberrant80
aberrant80

Reputation: 12997

I would say that you're generally correct, but not entirely accurate. You use a HashMap for data retrieval, but not always randomly. You use an ArrayList for iteration but you can also use it for lookups via the index.

More generally, you use a Map implementation when you need to efficiently retrieve items by lookup, i.e. retrieving something based on the key - such as dictionaries, caches, repositories, etc.

You use a List implementation when you just want a data structure where you can iterate over your data, usually when you want them in a predetermined and/or predictable order.

In other words, you use Maps as an indexing data structure, and you use Lists as you would usually use arrays.

Upvotes: 11

Kendall Helmstetter Gelner
Kendall Helmstetter Gelner

Reputation: 75058

Don't forget it's also much faster to get to one specific item with a map (if you have the key) than it is from an array (unless you have an index, but a key will always get you the right value whereas having an index may not work if new elements are inserted or older ones removed).

Upvotes: 5

CPerkins
CPerkins

Reputation: 9018

I'd disagree slightly. For me it depends more on how I want to retrieve the items. If I want to do so based on something like their order (by index, to be precise) I would tend to use a linear structure like an ArrayList (or even an array). If I need to look up items, I'd use a map structure like the HashMap.

Another complicating factor has to do with insertions and order, as dan pointed out.

Upvotes: 2

dan gibson
dan gibson

Reputation: 3665

For me, it's more whether I care about the ordering of the items in the collection. If you do care about the order then use the ArrayList. If you don't care about the order (you just want to store a bunch of items) then you can use a HashMap.

Upvotes: 4

harto
harto

Reputation: 90493

Generally, yes, you are correct. There's also a combined data structure, the LinkedHashMap, which offers fast access to arbitrary elements as well as predictable ordering.

However, it's worth noting that ArrayList and HashMap are only two implementations of the List and Map interfaces, respectively. There are other implementations of each that might be more suitable for more specific requirements. For example, a LinkedList might provide higher performance than an ArrayList for certain queueing/dequeueing requirements.

Upvotes: 35

Related Questions