patternMajor
Why is a (collision-less) hashtable lookup really O(1)?
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
Let's assume I have this hashtable:
Now I'm looking for the key
How does knowing a hash help finding the correct place in the table?
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 Data6Now 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.