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

Problem Detail: 

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?

Asked By : Foo Bar

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52488