A hash table is basically an array of small lists. The array is numbered 0 to size-1. For each key, the corresponding array item number is calculated using a hash function. This is a function that gives a seemingly random number to a key. How it is computed is not important, it's just important that it always returns the same number for the same key and that it maps different keys to different numbers as much as possible.

As long as each key has it's own space, lookups and writes are fast: compute hash index from key (some bit shifts and a modulo operation) and getting the n'th item from an array is fast too. Basically this always takes the same amount of time, irrespective of the number of items involved...

The problems begin when multiple keys map to the same array item. Then a little list is made inside that array item that has all entries that map to that number. For a lookup, those entries are parsed sequentially, check first item, then second etc until the correct item is found. The time taken to do this depends of the number of items in that list. Generally, going over 10 or 20 items doesn't take much time, so that why you can put 10 times as many items in a hash table as the size.

However, if you make the table way too small (or have the hash function return the same number(s) for abbout all keys), then each array item has a list of 1000s of entries, and that may take a noticable time to go through...

So, how does this hash function work? Usually it takes the word as a number, then does a bitshift or 2 and then takes the remainder after division by a prime number (preferrably close to the size of the hash table). You should realize that if the hash function