************************
:math:`O(1)` Hash Tables
************************

In some application, we want to guarantee a :math:`O(1)` worst-case cost.

Suppose that all :math:`N` items are known in advance.

*  If a separate chaining implementation could guarantee that each list had at most a constant number of items we would be done.
*  We know that as we make more lists, the lists will be shorter on average.
*  If we have enough lists, then we could expect no collisions at all.

This approach creates two problems:

1.  The number of lists might be large.
2.  We could still have collisions.

Perfect Hashing
===============

Perfect hashing was theorized to solve the second problem.

Suppose that we have :math:`TableSize = M`, with :math:`M` sufficiently large to guarantee that the probability fo collision is at least :math:`\frac{1}{2}`.

When there is a collision, we clear out the table and try with another hash function.

If there is another collision, we repeat the process with a third hash function.

Etc...

**The expected number of trials will be at most 2** (since the probability of success is :math:`\frac{1}{2}`).


How large :math:`M` needs to be?
--------------------------------

Remember that :math:`M` is the number of lists/cells in the hash table.

We should have a table of size :math:`M=N^2` to guarantee a probability of :math:`\frac{1}{2}`.

.. admonition:: Theorem
    :class: important

    If :math:`N` balls are placed into :math:`M=N^2` bins, the probability that no bin has more than one ball is less than :math:`\frac{1}{2}`.

.. admonition:: Proof
    :class: note

    *  We call it a collision when two balls :math:`i` and :math:`j` are placed in the same bin.
    *  Let :math:`C_{i,j}` the expected number of collisions produced by any two balls :math:`i` and :math:`j`.

       *  The probability of any two specified balls to collide is :math:`\frac{1}{M}`.
       *  Thus :math:`C_{i,j} = \frac{1}{M}`.
       *  The expected number of collisions in the entire table is :math:`\sum_{(i,j), i<j}C_{i,j}`.
       *  Since there are :math:`N(N-1)/2` pairs it sums to:
       
          .. math::
            
            \frac{N(N-1)}{(2M)} = \frac{N(N-1)}{(2N^2)}< \frac{1}{2}

The only issue is using :math:`N^2` is impractical.

How to solve this issue?
------------------------

Instead of using a linked list in case of collisions, we can use hash tables.

The idea:

*  Is to create a table of size :math:`N`.
*  Each time there is a collision for a cell, creates a hash table quadratic in size.

To illustrate the idea we have the following figure:

.. figure:: ./img/perfect_hashing.png
    :align: center

Each secondary hash table will use a different hashing function.

This strategy is called **perfect hashing**. We need to show that the size of the secondary hash tables is expected to be linear.

.. admonition:: Theorem
    :class: important

    If :math:`N` items are placed into a primary hash table containing :math:`N` bins, then the total size of the secondary hash tables has expected value at most :math:`2N`.

.. admonition:: Proof
    :class: note

    *  We use the same logic as in the previous proof.
    *  The expected number of collisions is :math:`N(N-1)/2N = (N-1)/2`.
    *  Let :math:`b_i` the number of items hashing in the cell :math:`i`.
    *  The size of the secondary table is :math:`b_i^2`.
    *  The number of collisions for the secondary table is :math:`b_i(b_i - 1)/2` called :math:`c_i`.
    *  Thus the amount of space :math:`b_i^2` is :math:`2c_i+b_i`.
    *  The total space is then :math:`2\sum c_i + \sum b_i`.
    *  The total number of collisions is :math:`(N-1)/2`.
    *  So we obtain a total secondary space requirement of :math:`2(N-1)/2 +N < 2N`.


It's all good, but it only works if we know in advance the number of elements.

Cuckoo Hashing
==============

Cuckoo hashing is a table scheme using two hash tables :math:`T_1` and :math:`T_2` each with :math:`N` bins with independent hash functions.


The idea:

*  An item can be stored only one table.
*  The insertion try to insert the element in the first table.
*  If it is occupied, it evicts the existing item.
*  Then it tries to insert the evicted item in the alternative table.
*  If it is occupied, it repeats the process.

.. admonition:: Example
    :class: example
    
    The idea can be illustrated by a small example.

    .. figure:: ./img/cuckoo_01.png
        :align: center
        :width: 70%

        We are inserting A. A can take either the index 0 in :math:`T_1` or 2 in :math:`T_2`.

    .. figure:: ./img/cuckoo_02.png
        :align: center
        :width: 70%

        After inserting :math:`B` it takes the index 0 in :math:`T_1` and move A in :math:`T_2`.

    .. figure:: ./img/cuckoo_03.png
        :align: center
        :width: 70%

        We are inserting :math:`C` without collision.

    .. figure:: ./img/cuckoo_04.png
        :align: center
        :width: 70%

        We are inserting :math:`D` that collide with :math:`C`, then we are inserting :math:`E`.

    .. figure:: ./img/cuckoo_05.png
        :align: center
        :width: 70%

        When inserting :math:`F` it collides with :math:`E`.

    .. figure:: ./img/cuckoo_06.png
        :align: center
        :width: 70%

        We move :math:`E` where :math:`A` is.

    .. figure:: ./img/cuckoo_07.png
        :align: center
        :width: 70%

        It moves :math:`A` to the position of :math:`B`.

    .. figure:: ./img/cuckoo_08.png
        :align: center
        :width: 70%

        Finally, we move :math:`B` to :math:`T_2`.


There is one issue with this strategy. 

If the load of the tables is too important, it could create a cycle.

So when inserting, it is important to rehash the tables when they reach a specific load.

.. warning:: 

    Cuckoo hashing is extremely sensitive to the choice of hash functions.