4

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.

Improve this question
7
  • Of course, that's equivalent to looking up in an array when one has the index. Commented Jul 30, 2019 at 20:59
  • HashMap is not considered to be more efficient than direct array indexing. It is more efficient than searching an array for a particular key though Commented Jul 30, 2019 at 21:04
  • Why isn't it? The efficiency for searching a specific key or value in a hashmap is O(n) Commented Jul 30, 2019 at 21:22
  • 1
    It's the same with the examples that you give, but a hashmap allows you to choose what you index on. So, pick a relevant index for your use-case and get that o(1) complexity. Arrays are like integer-indexed, restricted to a contiguous [0,n] space, which is useless in many of the real-world use cases and hence are mostly not used as an indexed set. Commented Jul 30, 2019 at 21:37
  • 1
    Of course if you have a use-case where indexing on [0,n] makes sense, then yes, an array might be (at least) as performant as a hashmap. Commented Jul 30, 2019 at 21:45

2 Answers 2

Reset to default
2

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.

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

3 Comments

I think I get it. Hashmap lookup is not faster in itself, but there are cases such as yours where using it would make it easier (what you suggested could be still implemented with an array and in O(1) by naming the students with indexes, e.g. Michael -> 0, Greg -> 1 etc.). However, I still don't feel comfortable with how in tutorials I am told that hashmaps are so useful because they make many cases much more efficient, I feel like something is still missing.
Yes, I can see you still have some confusion. If a program wants to found the score of "Greg", how will it know that it has to look at 1st index? Somewhere you will need to store that mapping that Greg is stored at 1st index.
If your lookup key is an Incremental counter then you can use an array and get similar O(1) complexity, anything other than that Map will be better.
2

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).

Improve this answer

1 Comment

But why is a hashmap considered faster for a lookup?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.