This exercise asks me to write a linear probe function and quadratic probe function, then insert 1000 random generated elements into the hash table and record how many collisions have occured for both function.

1. So far I have implemented the linear & quadratic probe functions, but I don't know how to record the collisions in a professional way.

2. I have tried to record the collisions by using global variables (i remove these codes because it is bad practice), and found out that my quadratic probe function does not reduce collisions. Please correct my probe functions.

Thank you

===========================

import random class HashTable: def __init__(self, size=1009): self.size = size self.table = [None for x in range(size)] def hash(self, data): start_position = data%self.size return start_position def linearProbe(self, start, attemptNumber = 0 ): # Recusion is easier here   insert_position = ( start + attemptNumber) % self.size if self.table[insert_position]!=None: attemptNumber+=1 return self.linearProbe(start,attemptNumber) else: return insert_position def quadraticProbe(self, start, attemptNumber = 0): # Recusion is easier here  # the quadratic probing formula: slot = (home + i ** 2) % M  # slot = insert_position; home = start_position; i = attemtNumber; M = size of the hash table  insert_position = ( start + attemptNumber**2) % self.size if self.table[insert_position]!=None: attemptNumber+=1 return self.quadraticProbe(start,attemptNumber) else: return insert_position # linear probe = 1, quadratic probe = 2  def insert(self, data, probe): start_position = self.hash(data) if probe == 1: insert_position = self.linearProbe(start_position) self.table[insert_position] = data if probe == 2: insert_position = self.quadraticProbe(start_position) self.table[insert_position] = data return  # template to be used to compare both lists that record the collisions, 0 = no collision, 1 = collision def comp_lists(list1, list2): def comp_elem(elem1, elem2): return 1 if elem1 < elem2 else 2 return map(comp_elem, list1, list2) # to generate two hash tables, and call comp_lists to compare def compareCollisions(output=True): linearTable = HashTable() quadraticTable = HashTable() a_table = random.sample(range(10000),1000) for items in a_table: linearTable.insert(items,1) print(linearTable.table) for items in a_table: quadraticTable.insert(items, 2) print(quadraticTable.table) compareCollisions()