File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Comparison of ArrayList and HashMap Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Comparison of ArrayList and HashMap" Watch "Comparison of ArrayList and HashMap" New topic
Author

Comparison of ArrayList and HashMap

Jitesh Sinha
Ranch Hand

Joined: Jun 19, 2004
Posts: 145
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
Rancher

Joined: Aug 11, 2007
Posts: 4646
    
    5

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
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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.


"I'm not back." - Bill Harding, Twister
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18520
    
  40

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 ]

Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4646
    
    5

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
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
As an aside:

O(n/2) = O(n)


The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
Jitesh Sinha
Ranch Hand

Joined: Jun 19, 2004
Posts: 145
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
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[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
Ranch Hand

Joined: Apr 19, 2002
Posts: 209
    
    1
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 ]
 
Don't get me started about those stupid light bulbs.
 
subject: Comparison of ArrayList and HashMap
 
Similar Threads
Why not use an ArrayList for caching instead of HashMap?
Which is better?
What collection api to use for mapping a pair of keys to a value?
Difference between HashMap and arraylist
does retrieval time for hashmap varies based on the size of hashmap