Consider a hash table T[m] in which collisions are treated as follows: when there is a collision on a cell of index v, we try to use the cell of index v + 1, then v + 4 then v + 9 ... v+$$i^{2}$$ ... where i is the iteration number, until an empty cell is found (success) or up to m/2 iterations (failure, even if free cells remains). The table is traversed in a circular manner; and when we reach the end of the table (m-1), we start at the beginning (0).

We assume the existence of a hash function h, and that elements in the table are of type t_Element, and that 2 elements can be compared using comparison operators associated to numbers ($$<, >, ==, ...$$).

• Assume that m = 12, give the contents of the table T[m], assumed initially empty, after adding the following elements in order : e, i, q, M, b, Y, n, J, such that h(e) = 5, h(i) = 9, h(q) = 5, h(M) = 5, h(b) = 2, h(Y) = 5, h(n) = 2, h(J) = 2.
• Write a function that tests if an element belongs to such a hash table.

******* HASH TABLE *******
0  
1  
2 : data=M 
3 : data=b 
4  
5 : data=e 
6 : data=q 
7  
8  
9 : data=i 
10  
11 : data=n 


******* END HASH TABLE *******
Y can't be added
J can't be added


int search(hash h, element e, int size)
{
    int i, nb ,step;
    int	vhash = hashfunction(e,size);
    nb=1;
	step=0;
	while(nb<(size/2))
	{
	    if(h[(vhash+step*step)%size] == e)
		    return 1;
	    step++;
	    nb++;
	}
	return 0;
}