6.006 Lec 4: Hashing

In the comparison model, the items themselves do not matter ( their value ), but we use only comparison operations on them to differentiate them ( and sort them )

Every single one of the algorithms found in lecture 3 were following that model.

The decision tree is a binary tree, with each node representing a comparison operation and creating a branch for each of the possible outcomes of the comparison.

In the decision tree, the leaves are the possible output values of the function, which in our case, since we search for a value in a \(n\) sized array, are \(n+1\), representing each value stored in the array and null for when the value we search for does not exist in the data structure.

We can easily visualize ( take a tree with 1 comparison, count leaves, move on to a tree with 3 comparisons etc ) that for the binary tree to have \(n+1\) different leaves it needs to have a minimum length³ of at least \(\lg{n+1}\), which means that the shortest path that one can take from the root to a leaf is \(\lg{n+1}\) and thus we have \(\Theta(\lg{n})\)

Sadly, that means that a faster than \(O(\lg{n})\) algorithm can not exist in the comparison model.

In this course this technique is often referred to as Direct Access Array

We know from the RAM model that access to any specific index in a static array takes constant time ( O(1) ). If, when dealing with sets, we create an array in which every item with key \(k\) gets stored at \(x[k]\), find(k) will work at \(O(1)\).

With relatively no extra work we have managed to implement find(k) at \(0(1)\)… But at what cost?

An example of a hash function is the following:

\begin{equation} h(k) = k\mod{m} \end{equation}

This is the deterministic approach to hashing, because the function is already hard coded and there will, unfortunately, be a certain type of input for which the function will not perform well

Instead of using a single function, it is possible to fix a family of them, something that we refer to as a UHF⁶, to avoid the error presented above: having a predefined particular set of inputs that breaks our program.

For \(a,b\in \{0,\cdots,p-1\}\), an improved hashing function would be:

\begin{equation} h_{ab}(k)=(((ak+b)\mod{p})\mod{m}) \end{equation}

And the family that we could use would be:

\begin{equation} H(p,m)=\{h_{ab}(k)|a,b\in\{0,\cdots,p-1\}, a\neq0\} \end{equation}

The universal part means that the collision probability is reduced and therefore, the chain lengths are kept sort. More specifically, if we use the boolean \(X_{ij}\) to inform us whether \(h(k_{i})=h(k_{j})\), the expected chain length will be given by, and \(X_{i}\) to be the length of the chain:

\begin{align} Pr_{h\in H}\{h(k_i)&=h(k_j)\} \leq \frac{1}{m} \forall k_i\neq k_j\\ E_{h\in{H}}\{X_{i}\} &= E_{h\in{H}}\sum_{j=0}^{n-1}X_{ij} = \cdots \leq 1+\frac{n-1}{m} \end{align}