$2.$ Using the Linear Probing code in tpython as a base, write insert, search and delete functions for:

a$.$ A hashtable that implements Quadrating Probing

b$.$ Implements Double hashing, where the secondary hash function is an argument to Hashtable

constructor

class linearprobing:

def $\_\_$init$\_\_($self$,$ n$)$:

self.table $=[$None$]*$ n

self.n $=$ n

def insert$($self$,$ key, value$)$:

i $=$ hash$($key$)\%$ self.n

misses $=0$

new$\_$i $=($i $+$ misses$)\%$ self.n

while self.table$[$new$\_$i$]$ is not None:

k$,$ v $=$ self.table$[$new$\_$i$]$

if k $==$ key:

break

misses $+=1$

new$\_$i $=($i $+$ misses$)\%$ self.n

self.table$[$new$\_$i$]=($key$,$ value$)$

def search$($self$,$ key$)$:

i $=$ hash$($key$)\%$ self.n

misses $=0$

new$\_$i $=($i $+$ misses$)\%$ self.n

while self.table$[$new$\_$i$]$ is not None:

k$,$ v $=$ self.table$[$new$\_$i$]$

if k $==$ key:

return v

misses $+=1$

new$\_$i $=($i $+$ misses$)\%$ self.n

return None

def delete$($self$,$ key$)$:

i $=$ hash$($key$)\%$ self.n

misses $=0$

new$\_$i $=($i $+$ misses$)\%$ self.n

while self.table$[$new$\_$i$]$ is not None:

k$,$ v $=$ self.table$[$new$\_$i$]$

if key $==$ k:

self.table$[$new$\_$i$]=$ None

prev $=$ new$\_$i

curr $=$ misses $+1$

new$\_$i $=($i $+$ curr$)\%$ self.n

while self.table$[$new$\_$i$]$ is not None:

self.table$[$prev$]=$ self.table$[$new$\_$i$]$

prev $=$ new$\_$i

curr $+=1$

new$\_$i $=($i $+$ curr$)\%$ self.n

retur

misses $+=1$

new$\_$i $=($i $+$ misses$)\%$ self.n