This question requires you to create a python function to add keys to a hash table.
Execute the code in the next cell and then read the instructions below.
Here is an example input:
python
["+1","+4","+10","+20","-1","+17","-7","+4"]
And the task
Edit the next code to provide your solution.
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None self.tail = None self.size = 0 def check(self, data_list): contents = [] node = self.head while node != None: contents += [node.data] node = node.next return contents == data_list class Hash_Table(): "implements a hash table of size k with all entries empty linked lists for a Hash_Table h: h.lookup (pos) returns the linked list in position pos h.check(data) checks that the current content is the same as data h.print_table prints a representation of h def __init__(self, k): self. table = [] self._size = k for idx in range(k): L = LinkedList() self._table += [L] def lookup(self, pos): return self._table[pos] def _contents(self): buckets = [] for idx in range(self._size): bucket - [] node = self._table[idx].head while node != None: bucket += [node.data] node = node.next buckets += [bucket] return buckets def check(self, data): if len(data) != self._size: return false for idx in range(self._size): bucket = self._contents([idx][:] bucket.sort (0) bucket2 = data[idx][:] bucket2.sort() if bucket != bucket2: return false return True def print_table(self): print (self._contents()) You must create a function hash that creates a hash table of size 13, accepts as input a list of operations, returns the hash table after these operations have been applied. Here is an example input: ["+1","+4","+10","+20","-1", "+17","-7","+4"] Each item in the input is a string whose first character is either ' t' or ' -'. The remainder of the string is a key which be should be added or removed to the hash table if the first character is ' t' or ' -' respectively. So with the example input, the keys 1 and 4 are added and then 1 is removed. Then 6 is added, 7 is removed and 4 is added. Note that if a key not in the table is asked to be removed, then the table should not be altered and the function should continue to read the rest of the input, if a duplicate key is asked to be added, then the table should not be altered and the function should continue to read the rest of the input You can assume that the keys are positive integers. The hash function to be used for a key k is 2k + 4 mod 13. As mentioned, the linked lists in the buckets are to allow separate chaining to handle collisions. So each key must be added to the linked list in the bucket given by the hash function. Although in the lectures we suggested that new keys are always added to the tail of the list, the order of the keys within the same list is not important. A sketch of what is needed using the example input ["+1", " +4", "+10", " +20", "-1", " +17", "-7", " +4"]. We must create a table h. First 1 is added to the table. As 2k + 4 mod 13 = 6 when k = 1, it is added to the linked list in bucket 6. Then 4 is added to bucket 12, 10 is added to bucket 9 and 20 is added to bucket 5. Now 1 is deleted from bucket 6. As 2k + 4 mod 13 = 12 when k = 17, 17 is added to bucket 12 (so now the linked list there contains two nodes). Nothing happens in response to "-7" as 7 is not in the table so cannot be deleted. Nothing happens in response to " +4" as 4 is already in the table so does not need to be added. If we now obtained a representation of h using the method print_table() we would obtain [[], [], [], [], [], [20], [], [], [], [], [], [10], [4, 17]] But note this is just a representation as the objects in the buckets are linked lists. Note we could write, for example, h.lookup (12) head.next. data and this would return 17. def hash(d): - "given a list d of instructions to add or delete keys to a hash table returns the hash table after these instructions have been applied using hash function h(K) = 2k + 4 mod 13 the instructions are either '+k' or '-k' for some positive integer k to indicate that k is to be added or deleted separate chaining is used for collision handling h = Hash_Table(13) #initialize table #READ AND APPLY INPUT return h 0.35 def test_hash(): assert hash(['+','+1','+2','+3','+4','+5', '+6','+7', '+8','+9','+10', '+11','+12']).check([[11], [5], [12], [6], [0], [7], [1], [8], [2], [9], [3], [10], [4]]) assert hash(['+1', '+32', '-32']).check([[], [], [], [], [], [], [1], [], [], [], [], [], []]) assert hash(["+1", "+2","-3","+14","-2","+15","-1","+28","-7","+8"]).check([[], [], [], [], [], [], [14], [8], [15, 28], [], [], [], []]) print ("all tests passed")
