The idea of Cuckoo hashing is to resolve collisions by using two hash functions instead of only one. 
In the basic variant of Cuckoo hashing, we use two hash tables $$T_1$$ and $$T_2$$ of equal size $$N$$, and we index each key $$k$$ with the hash functions $$H_1(k)=k \% N$$, respectively $$H_2(k)= \lfloor \frac{k}{N} \rfloor \% N$$. 

Here are the main operations:

• Search: an element $$x$$ can exist in one of two locations: in $$T_1$$ at position $$H_1(x)$$ or in $$T_2$$ at position $$H_2(x)$$. Check both locations.
• Delete: we look at the two possible locations, and if the element is there, delete it.
• Insert: we put $$x$$ in $$T_1[H_1(x)]$$. If there was some element $$y$$ stored in that location, $$y$$ must be evicted (i.e. transfered to the second table) (thus the name "cuckoo" hashing). We put $$y$$ in its other valid location $$T_2[H_2(y)]$$. If that location is occupied by some element $$z$$, we have to evict $$z$$ and insert it in its other valid location $$T_1[H_1(z)]$$. We continue like this until we find an empty place and the process finishes, or until we give up because it starts to take too long (perhaps because we ran into a loop). If the latter happens, we conclude that insert failed, we stop.
  
  

Consider the following example:
Let $$N=11$$, $$H_1(k)=k \% 11$$ and $$H_2(k)= \lfloor \frac{k}{11} \rfloor \% 11$$.
Let the keys be the following, along with their hashing values:

\begin{array}{| c | c | c |}\hline
k & H_1(k) & H_2(k) \\ \hline
20 & 9 & 1 \\ \hline
50 & 6 & 4 \\ \hline
53 & 9 & 4 \\ \hline
75 & 9 & 6 \\ \hline
72 & 6 & 6 \\ \hline
\end{array}

Insertion of 20:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9&10 \\ \hline
T_1 & & &&&&&&&&20& \\ \hline
T_2 & & &&&&&&&&& \\ \hline
\end{array}

Insertion of 50:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9&10 \\ \hline
T_1 & & &&&&&50&&&20& \\ \hline
T_2 & & &&&&&&&&& \\ \hline
\end{array}

Insertion of 53:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9&10 \\ \hline
T_1 & & &&&&&50&&&53& \\ \hline
T_2 & & 20 &&&&&&&&& \\ \hline
\end{array}

Insertion of 75:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9&10 \\ \hline
T_1 & & &&&&&50&&&75& \\ \hline
T_2 & & 20 &&&53&&&&&& \\ \hline
\end{array}

Insertion of 72:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9&10 \\ \hline
T_1 & & &&&&&72&&&53& \\ \hline
T_2 & & 20 &&&50&&75&&&& \\ \hline
\end{array}

In the following, consider that all keys are $$\geq$$ 0.

1. Write a function that checks whether an element $$x$$ belongs to such hash tables.
2. Write a function that deletes an element $$x$$ from such hash tables.
3. Write a function that inserts an element $$x$$ into such hash tables.

typedef struct
{
	element T1[N];
	element T2[N];
} Hash;

Hash Create()
{
	Hash h;
	int i;
	for(i=0;i<N;i++)
	{	
		h.T1[i]=-1;
		h.T2[i]=-1;
	}
	return h;
}

int belong(Hash h, element e)
{
	int v1, v2;
	v1=hash1(e);
	v2=hash2(e);
	return( h.T1[v1]!=-1 && h.T1[v1]==e || h.T2[v2]!=-1 && h.T2[v2]==e);
}

int deleteh(Hash *h, element e)
{
	int v1, v2;
	v1=hash1(e);
	v2=hash2(e);
	if(h->T1[v1]!=-1 && h->T1[v1]==e)
		h->T1[v1]=-1;
	else 
		if(h->T2[v2]!=-1 && h->T2[v2]==e)
				h->T2[v2]=-1;
		else 
			return 0;
	return 1;
}

int insert(Hash *h, element e)
{
	int i=1; 
	int pass=1;
	element el=e,temp;

	if(belong(*h,e))
		return 0;

	while(i<2*N)  
	{
		if(pass==1) 
		{
			if(h->T1[hash1(el)]==-1)
			{
				h->T1[hash1(el)]=el;
				return 1;
			}
			temp=h->T1[hash1(el)];
			h->T1[hash1(el)]=el;
			el=temp;
			pass=2;
		}
		else  
		{
			if(h->T2[hash2(el)]==-1)
			{
				h->T2[hash2(el)]=el;
				return 1;
			}
			temp=h->T2[hash2(el)];
			h->T2[hash2(el)]=el;
			el=temp;
			pass=1;
		}
		i++;
	}
	return 0;
}