Comparison of ArrayList and HashMap

[Jitesh Sinha]

Why is retrieval from HashMap supposed to be faster than that from ArrayList?Here we are trying to compare HashMap.get(keyobject) and ArrayList.get(index).
The complexity of HashMap retrieval is o(1)(I really do not know how;am certainly interested in knowing that) while I do not know about ArrayList.
Since ArrayList is based on arrays, it has random access available to it.How anything can be faster than that,beats me.
I have been asked this question several times and have not been able to find out.I have searched on this site also but could not get the exact answer.
Thanks for help.
-Jitesh

[Pat Farrell]

You are missing a subtlety of the access.

Accessing any element of a HashMap is O(1) but the constant can be large. Accessing the general n'th element of an ArrayList is advertised as being potentially slower O(n/2), as the list is allowed to be fragmented. Accessing the first or last element of an ArrayList is fast. Still O(1), but with a very small constant. get(0) and get(size()-1) are both very efficient.

Adding a general element to a HashMap is fast. Adding an element in the middle of an ArrayList can be slow, since the list may have to be reallocated, copied and the element added.

For small lists, ArrayList is nearly always faster for everything.

The definition of "small" is subjective and left as an exercise to the reader.

[Jim Yingst]

Adding to Pat's answer...

[Jitesh]: Why is retrieval from HashMap supposed to be faster than that from ArrayList?

Where did you hear that? I don't think it's true at all. To retrieve from an ArrayList is a very simple operation. You can look at the source code in src.jar and see just what it does, and compare it to the code in HashMap. The former merely looks up an element in an array and returns it; the latter must calculate a hashcode, use it to look up an element in an array, follow a (hopefully short) linked list of entries and compare them with equals(). There may be some circumstance for which retrieval from a HashMap is faster than from an ArrayList - but I assure you, that would be very rare.

[Jitesh]: The complexity of HashMap retrieval is o(1)... while I do not know about ArrayList.

Accessing any element of an ArrayList is also O(1). As it happens, it's generally a smaller O(1) than for HashMap. But the point of using big-O notation is generally to overlook such considerations anyway. They're both O(1); that's enough info for most purposes, I think.

[Henry Wong]

The complexity of HashMap retrieval is o(1)(I really do not know how;am certainly interested in knowing that)

A hash is an mathematical operation on a object that has an O(1). From this hash, a hashmap can get to a bucket, which if it is an array, also has an O(1). This means that given any object as a key, it can get to the pair value in an O(1).

Since ArrayList is based on arrays, it has random access available to it.How anything can be faster than that,beats me.

A array list is based on an array which has an O(1).


But this is not the point. The point is... a hashmap can get to any value based on any key. For example, if I want the color of a car, I can use the "color" key to get a string that returns the color. Same for "engine", "tires", etc.

If I want to do this with an array list -- and keep an O(1) -- I have to assign 0 to color, 1 to engine, etc. Of course, I can use two arraylists, one to hold the key and the other to hold value, but searching it won't be O(1). I have to find "color" in the first array, to find the index, so I can find the color value.

Henry
[ October 05, 2007: Message edited by: Henry Wong ]

[Pat Farrell]

Yes, Henry wrote a critical item that I thought of overnight.
With a HashMap, the key can be anything, not just an integer. And searching for an arbitrary Object in an ArrayList has to do a linear search, O(n/2)

So if you want to index by a value, there is no comparison.

[Ilja Preuss]

As an aside:

O(n/2) = O(n)

[Jitesh Sinha]

Guyz,thanks for your informative replies.I looked at the Hashing functionality which is performed by java internally.
Regarding "which one is faster :ArrayList or HashMap",whenever I say it is arraylist,I get the reply "Don't you think Hashmap is faster?".It has thrice in a space of 10 days ;that created a lot of confusion.I guess ,I need to give a detailed reply which should include the way the two data structures are going to be used.

[Jim Yingst]

[Jitesh]: Regarding "which one is faster :ArrayList or HashMap",whenever I say it is arraylist,I get the reply "Don't you think Hashmap is faster?"

It sounds like whoever is asking you this is very confused. Aside from the fact that get() from an ArrayList is faster than get() from a HashMap, more important is the fact that the two data structures solve different problems. I think you first need to determine whether you need a List or a Map (forgetting about the implementation details). If you need a List then the speed of a HashMap is irrelevant; if you need a Map, the speed of an ArrayList is irrelevant. Just about the only time that you could use either one is when you have "keys" that are all consecutive (or nearly cosecutive) integers. If that's the case, then ArrayList is probably faster. In any other case, the question is probably irrelevant. It's like deciding if you want a hammer of a fishing pole - you need to ask, to do what?

[Justin Chu]

Depends on the context.

Suppose you have a telephone book worth of names to phone numbers. It is a better choice to use HashMap to support O(1) lookup for the name "John Doe" to get to his phone number.

To implement the same feature using only arrays, you'll need two arrays, one for names, and the other for phone numbers, and their index corresponds. Assuming the names are sorted, the fastest lookup for "John Doe" is O(log n).

This boils down to the definition of your "retrieval", if it is finding arbitrary object A in an array list vs hashmap/set, a hashmap/set will be faster (asymptotically).
If you are referring to indexed random access, obviously Array list will be more efficient because you skip the step of converting the "external index" to an internal index through the process of hashing. But you lose the advantages of a hash map.

In my opinion, you won't get fired by using HashMap when arrays sufficed. But the other way round is more damaging.

Read this book if you have the time
[ October 08, 2007: Message edited by: Chu Tan ]