Can hash tables really be O(1)?

Question

It seems to be common knowledge that hash tables can achieve O(1), but that has never made sense to me. Can someone please explain it?

Answer 1

Hi, Danny - good question - and yes, an achievable O() goal for hash tables/maps is 1!

The basic approach with a hash table structure revolves around sacrificing space for time ;-)

We create a 'key=value' pair table that's typically nX the expected number of elements that we expect to store there. It's also a really good idea to size the hash table to a prime number, rather than a base 10 or base 2 number we might be accustom to assigning as a data structure size.

Why? Because the key/value positional scheme is based on modulo (remainder) arithmetic performed on the hash number value generated from the key value, and the size of the table (remainder of key hash value / table size) - that is, the key/value pair is placed in the hash table position dictated by that calculation.

So we're less likely to generate a duplicate value (aka, a collision) across these modulo operations:

hash value [key 1] % table size, hash value [key 2] % table size, hash value [key 3] % table size ... hash value [key n] % table size

when table size is a prime-number.

For example: if I'm expecting to store 15-20 items in a given hash table, I might choose to set the initial size of that table to 113 (rather than 100, 128, ... ).

When I go to find a given key/value pair, the same computation is used to determine if we're currently storing that key/value pair at position N where N is key hash value % table size.

There's a deeper science here than I'm letting on to ...

In actually, "collisions" can and do occur ... a good hash table implementation deals with that gracefully (details not provided here).

But the details provided above describe why hash table element access is indeed a O(1) algorithm.

Clear?

Good luck!

--Lou