Operations on Hash Tables

In this problem, you will implement a data structure for hashing with linear probing. Assume

that we have functions for insertions, deletions, and finds. Define four functions as per

description. Assume the keys are non$-$negative integers, which are hashed into a table of size

maxSize. An empty table entry can be indicated using $-2.$ Use $-1$ in a location to indicate that

the entry formerly in the location has been deleted. Use hash function key$\%$maxSize.

a$.$ Find$($x$)$ which returns the index of where x is stored if it is in the hash table and $-1$

otherwise.

b$.$ Insert$($x$)$ which inserts x into the hash table with the precondition that x is not currently in

the table. Naturally, a location with a $-1$ in it can be used to place a newly inserted item.

Your algorithm should indicate when the hash table is full and x cannot be inserted.

c$.$ Delete$($x$)$ which removes x from the hash table using lazy deletion.

d$.$ Print$()$ which prints all the valid items in the hash table.

e$.$ Rehash$()$ which returns a new table of the same size maxSize which contains all the items

of the old table, but has no items marked as deleted. $[$Hint$.$ Create a new object of

HashTable, insert all the valid items from the current HashTable to the newly created one$]$