CODEWITHSUNDEEP
hashlanguage-agnostichashmaphashtable
user2005643
user2005643

Reputation:

I'm having difficulty understanding a concept in Hash Tables

I understand the allure of hash tables is that you get O(1) lookup times, but I'm having difficulty understanding how the storage component works.

I understand Hash Tables use a key-value pair, where given a certain key you can get its particular value back. So if I wanted to associate a name with a phone number, I could have "Paul" as the key, and the phone number as the value I then receive. I understand that much.

Upvotes: 0

Views: 141

Answers (2)

David Cary
David Cary

Reputation: 5490

if there's multiple phone numbers stored at "Paul"'s hashed index, how do I know which one is actually Paul's?

The items stored in a hash table bucket include more than the phone number (the value). The hash table stores both the key and the value.

So does it work in that at the array index that "Paul" get hashed to (say, 3), the value there will be a phone number, thus the O(1) lookup time?

Yes, when "Paul" gets hashed to "3", usually the item at hash_table[3] stores both the name "Paul" and Paul's phone number -- usually there is no collision. But occasionally there is a collision, and the first item at hash_table[3] stores some other name. The main difference between different hash table algorithms is how they handle collisions (their "collision resolution strategy"), where the lookup("Paul") function looks next for Paul's name and phone number.

Upvotes: 0

Ry-
Ry-

Reputation: 224867

if there's multiple phone numbers stored at "Paul"'s hashed index, how do I know which one is actually Paul's?

Generally, each entry would be checked for equality individually after that, in the same way as a regular search across a linked list.

So does it work in that at the array index that "Paul" get hashed to (say, 3), the value there will be a phone number, thus the O(1) lookup time?

Pretty much! The hashed value is usually first converted to a bucket number somehow, since hash results can exceed a reasonable size for a lookup table (e.g. four billion).

Upvotes: 1

Related Questions