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

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?

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.

• Thanks. :) My mistake was thinking of a hashtable hash function like MD5 or SHA. But a hash can of course be an integer position, which I didn't thought about. Now that I know what to look for, I even quickly found a good example: the hash function of PHP: github.com/php/php-src/blob/PHP-5.6.10/Zend/zend_hash.h#L237 – Foo Bar Jan 30 '16 at 20:23
• @FooBar: MD5 and SHA also calculate single numbers out of the input, it's just so common to talk about the hashes in hex form. Just like memory addresses rarely are considered in decimal. – souser12345 Jan 30 '16 at 21:14
• Plus, MD5 etc. are too long to be used as an array index directly. It would be possible to use some part of the hash, like the lower n bits. – chirlu Jan 31 '16 at 5:16

Hash function calculates array position from given string. If this is perfect hash it means that there are for sure no collisions, the most probably array is at least twice bigger than number of elements.

For example I will give very poor hash for letters, just to ilustrate mechanism:
0) $x = 0;$
1) for each character in string take ascii value, subtract 'a' if it is lower case, subtract 'A' if upper case, add value to x. $x = x mod 52$
2) the resulting number e.g. 15 is index of array.

This very simple hash (limited and prone to collisions) differs from other hashes in mechanism of hashing, does not consider given input. In more advanced scheme the hash is bigger number, adjusted to number of elements. Perfect hash is generated for all inputs to guarantee no collisions.

This is $O(1)$ because calculating hash from string depends on how sophisticated is function computed, but does not depend on number of elements.

In case of perfect hash, when elements are added $h(k)$ is recalculated, the simpler case with collisions when array load is big the array size increases, function takes bigger modulo of output, and elements are shifted to the new places.

Array is continous memory fragment, to get $n-th$ element you take address of the first element (array start) and then add to this address $n * (size of element)$ so you have explicit memory cell.

• And how does the lookup know where in the table is the hash? It's neither ordered nor hardware addresses. – Foo Bar Jan 30 '16 at 19:52
• You give some string e.g. "xcnvb", $h("xcnvb") = 8$ so the calculated hash gives index of array, "xcnvb" is your element to lookup, 8 is index in the table. It is nod ordered, hash returns the place to retreive element. This element was put there by the very same function. Hardware has nothing to do here. You provide array, hash function and compute hash to get index in array, the same in retreival. Array is not sorted, also it is never full. – Evil Jan 30 '16 at 19:55
• But not every index will be filled. If I have hash 1, 4, 8, 90 and 223 filled with data, how does a lookup find the correct place? In thsi case index "90" is at position 4 because most other indexes don't exist. And an empty hashtable is not of infinite size having all possible positions!? – Foo Bar Jan 30 '16 at 19:58
• Yes, the array let us assume 512 elements long, 9 bits used for hash function, and you have only 4 elements. Index 90 has position 90 in the array, as in example - almost all cells are empty. If your array is $Ha$ you index it $Ha(h("xcnvb")) = Ha[90]$ = your data for "xcnvb" – Evil Jan 30 '16 at 20:01
• The hash function doesn't return an index into the array. Instead, it returns a predictable number that can be mapped into the array. That's usually done using the modulus operator with the number of hash table buckets as the other operand. – Christopher Schultz Feb 1 '16 at 14:13

To expand on David Richerby's answer, the term "hash function" is a little overloaded. Often, when we talk about a hash function we think of MD5, SHA-1, or something like Java's .hashCode() method, which turns some input into a single number. However the domain of this number (i.e. is maximum value) is very unlikely to be the same size as the hashtable you're trying to store data in. (MD5 is 16 bytes, SHA-1 is 20 bytes, and .hashCode() is an int - 4 bytes).

So your question is about that next step - once we have a hash function that can map arbitrary inputs to numbers, how do we put them into a data structure of a particular size? With another function, also called a "hash function"!

A trivial example of such a function is modulo; you can easily map a number of arbitrary size to a specific index in an array with modulo. This is introduced in CLRS as "the division method":

In the division method for creating hash functions, we map a key $k$ into one of $m$ slots by taking the remainder of $k$ divided by $m$. That is, the hash function is

$h(k) = k$ mod $m$.

...

When using the division method we usually avoid certain values of $m$. For example, $m$ should not be a power of 2, since if $m = 2^p$ then $h(k)$ is just the $p$ lowest-order bits of $k$.

~Introduction to Algorithms, §11.3.1 - CLRS

So modulo isn't a great hash function, since it restricts what sizes we can safely use for our underlying data structure. The next section introduces a slighly more complex "multiplication method", which also uses modulo but is advantageous because "the value of $m$ is not critical". It however works best with some prior knowledge of "characteristics of the data being hashed" - something we often don't know.

Java's HashMap uses a modified version of the division method that does a pre-processing step to account for weak .hashCode() implementations so that it can use power-of-two sized arrays. You can see exactly what's happening in the .getEntry() method (comments are mine):

 // hash() transforms key.hashCode() to protect against bad hash functions
int hash = (key == null) ? 0 : hash(key.hashCode());
// indexOf() converts the resulting hash to a value between 0 and table.length-1
for (Entry<K,V> e = table[indexFor(hash, table.length)];
...


Java 8 brought along a rewrite of HashMap which is even faster, but a little harder to read. It uses the same general principle for index lookup, however.