What is a Hash Table?

A hash table is a data structure optomized for searches.
With a hash table search times are improved when compared to a linked list or even a binary tree structure.
Inserts and space required are compromised to improve search times.
A hash table is an array implementation in which we decrease the size of the array by allowing for collisions.
To reduce the number of collisions, the number of elements in the array should be twice the size of the elements we wish to track.

cellIndex = value % tableSize;

We can then handle collisions by chaining (duplicates are put into a linked list) or by linear probing or quadratic probing (since values often group together).
When doubling the array size we must also remap the previously inserted values according to the new table size.

linear probing:
cellIndex = Hash(X) % tableSize;
cellIndex = Hash(X)+1 % tableSize;
cellIndex = Hash(X)+2 % tableSize;
cellIndex = Hash(X)+3 % tableSize;
...
quadratic probing cellIndex = value % tableSize;...
cellIndex = Hash(X) % tableSize;
cellIndex = Hash(X)+(1^2) % tableSize;
cellIndex = Hash(X)+(2^2) % tableSize;
cellIndex = Hash(X)+(3^2) % tableSize;
...

In summary, most databases (large ones) use hash table data structures.