Task 1 [7 marks]

Implement a complete version of a hash table using Linear Probing to resolve collisions. Include implementations for the following 4 functions:

__getitem__(self, key): Returns the value corresponding to key in the hash table. Raises a KeyError if key does not exist in the hash table. Called by table[key]

__setitem__(self, key, value): Sets the value corresponding to key in the hash table to be value. Raise an exception if the hash

fit1008 intro to computer science assessed prac 3 weeks 11 and 12 2

table is full and the key does not exist in the table yet. Called by table[key] = value

__contains__(self, key): Returns True if key is in the table and False otherwise.

hash(self, key): Calculates the hash value for the given key. Use the hash function given below.

def hash_value(self, key):

a = 101

h=0

for c in key:

h = (h * a + ord(c)) % self.table_size

return h

Task 1 used as reference. Need help with Task 3. Thank you :)

nation of values takes too long. In total you should consider 15 possibilities (3 files for each table size). In this task you use the word as both, key and data Task 3 l3 marks] Modify your hash table implementation to now track the number of collisions, the load, as well as the average probe length. For the latter, it is advisable to track the total probe length in an instance variable The average probe length is the total probe length divided by the number of items on the table. Using collisions, probe length and wall time, choose appropriate values of a (in your hash function) and table size. You want to find values that perform well across all three files. For this task use a maximum table size of 400000. You should try at least 1o values, and explain your choice by presenting all data behind d your reasoning recorded in a table Just for fun we'll collect the best performer in each lab class nation of values takes too long. In total you should consider 15 possibilities (3 files for each table size). In this task you use the word as both, key and data Task 3 l3 marks] Modify your hash table implementation to now track the number of collisions, the load, as well as the average probe length. For the latter, it is advisable to track the total probe length in an instance variable The average probe length is the total probe length divided by the number of items on the table. Using collisions, probe length and wall time, choose appropriate values of a (in your hash function) and table size. You want to find values that perform well across all three files. For this task use a maximum table size of 400000. You should try at least 1o values, and explain your choice by presenting all data behind d your reasoning recorded in a table Just for fun we'll collect the best performer in each lab class