HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Why is a (collision-less) hashtable lookup really O(1)?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whyreallycollisionhashtablelesslookup

Problem

Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for.

My question is: why is collision-less lookup O(1) in the first place?

Let's assume I have this hashtable:

Hash  Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6


Now I'm looking for the key k where the hash function h(k) gives h(k) = mkwer. But how does the lookup "know" that the hash mkwer is at position 5? Why doesn't it have to scroll through all keys in O(n) to find it? The hashes can't be some kind of real hardware addresses because I'd lose the abbility to move the data around. And as far as I know, the hashtable is not sorted on the hashes (even if it was, the search would also take O(log n))?

How does knowing a hash help finding the correct place in the table?

Solution

The hash function doesn't return some string such as mkwer. It directly returns the position of the item in the array. If, for example, your hash table has ten entries, the hash function will return an integer in the range 0–9.

Context

StackExchange Computer Science Q#52488, answer score: 24

Revisions (0)

No revisions yet.