CODEWITHSUNDEEP
javahashmap
David
David

Reputation: 179

Difference between a hashmap and an array in time complexity of a lookup

If I have to know the key to get the value in a hashmap (for time complexity O(1)), why is it any different than getting a value inside an array when knowing the index (O(1) as well)?

In other words, a hashmap is considered having O(1) complexity for a lookup, but this is because the key is known. This is the same with an array when the index is known--if I don't know the index it would be O(n) which is the same as not knowing the key and then it's O(n) for the hashmap as well (containsValue(Object value) method).

Therefore, I don't understand why a hashmap is considered to be more efficient for lookups.

Upvotes: 4

Views: 1697

Answers (2)

Luke
Luke

Reputation: 848

Knowing the index of an array is not the same as knowing the key of a hashmap.

In an array, you don't store indices within the contents of the array. This would look like 

i[0] = 0, i[1] = 1, i[2] = 2, etc...

In actuality it looks more like 

i[0] = 20, i[1] = 100, i[2] = 5, etc..

or 

i[0] = 'dog', i[1] = 'cat', i[2] = 'parrot', etc...

In order to know the index of the array containing whatever element you are looking for, you would either be storing an array of indexes (i.e. the odd example I mentioned first above), or you would have a separate in memory tool that was mapping indices to the correct element within the array (which is in essence a hashmap).

A hashmap allows you to, in 0(1) time, find an element within an array (without needing a separate in memory object to map indices to elements, and for arrays that contain contents other than just the indices of the array).

Upvotes: 2

Abhishek Garg
Abhishek Garg

Reputation: 2288

I think a good way to understand this is by using an actual use-case. Let's say you want to store a student name and his marks.

So there are 2 fields.

String name
Integer marks

Now you want to lookup marks based on student name.

In the array way, you will be creating a class which holds both the info and put them in an array.

Now to check the marks of a student name, either you need to iterate the whole array or you need to know that at what index a particular name is stored. Both of these are O(N) complexity.

Or you can store it in a map with key as name and value as marks. You can look up into the map by name in O(1) complexity.

TL;DR; You need to see your usecase and then decide if you can work with Arrays(Lookup based on Ordered Index) or you actually need a Map for the lookups.

Upvotes: 2

Related Questions