Can you help me with this PYTHON problem. Please answer with code

Overview

For this assignment you will complete the implementation of a hashtable data structure, which exposes an API mirroring that of the built-in Python dict.

A hashtable is conceptually a two-tiered data structure, where keys are initially mapped via their hash values to slots in a "buckets" array, each of which in turn contain singly-linked (non-circular) lists of key/value pairs (known as "chains"). The hope is that by keeping the number of collisions i.e., instances where keys map to the same bucket low, key-based lookups can be performed very quickly. The essential operations on a hashtable h are listed alongside their behavior/mechanics below:

Operation	Description
h[k] = v	The key k's hash value is used to locate the appropriate slot in the array of buckets. If the bucket entry is None, a new linked list is created with k & v as the first entry and the head of the list is placed in the bucket. Otherwise, the list is searched for a node containing key k; if found the node's value will be updated with v, else a new node containing key k & value v is appended to the list. Note that this implies a given key has a unique mapping in a hashtable.
h[k]	The key k's hash value is used to locate the appropriate slot in the array of buckets. If the bucket entry is not None, the linked list at that location is searched for a node containing k; if found, the corresponding value is returned. If the bucket is empty or the list does not contain a node with key k, a KeyError is raised.
del h[k]	The key k's hash value is used to locate the appropriate slot in the array of buckets. If the bucket entry is not None, the linked list in the bucket is searched for a node with key k; if found, it is deleted. If either the bucket is empty or the list doesn't contain key k, a KeyError is raised.
k in h	Returns True if key k is found in a list in the appropriate bucket.
len(h)	Returns the number of keys stored across all buckets.
iter(h)	Returns an iterator over all the keys in the hashtable.
h.keys()	Returns an iterator over all the keys in the hashtable (the same as above).
h.values()	Returns an iterator over all the values in the hashtable.
h.items()	Returns an iterator over all the key/value pairs (as tuples) in the hashtable.
h.setdefault(key, default)	If key is in the dictionary, return its value. If not, insert key with a value of default and return default. default defaults to None.

Your hashtable will be provided with the initial number of buckets on creation (i.e., in __init__), which will be used to create an array with that size (where each slot contains None). Because the hash value of a given key can exceed the number of buckets, hash values will be mapped to buckets using the modulus operator; i.e., hash(k) % len(self.buckets) will return the index of the appropriate bucket for key k.

In [ ]:

class Hashtable: 

 class Node: 

 """Instances of this class will be used to construct the linked lists (chains) 

 found in non-empty hashtable buckets.""" 

 def __init__(self, key, val, next=None): 

 self.key = key 

 self.val = val 

 self.next = next 

 def __init__(self, n_buckets=1000): 

 self.buckets = [None] * n_buckets # initially empty buckets array 

 self.count = 0 

 def __getitem__(self, key): 

 # YOUR CODE HERE 

 raise NotImplementedError() 

 def __setitem__(self, key, val): 

 # YOUR CODE HERE 

 raise NotImplementedError() 

 def __delitem__(self, key): 

 # YOUR CODE HERE 

 raise NotImplementedError() 

 def __contains__(self, key): 

 # YOUR CODE HERE 

 raise NotImplementedError() 

 def __len__(self): 

 return self.count 

 def __iter__(self): 

 # YOUR CODE HERE 

 raise NotImplementedError() 

 def keys(self): 

 return iter(self) 

 def values(self): 

 # YOUR CODE HERE 

 raise NotImplementedError() 

 def items(self): 

 # YOUR CODE HERE 

 raise NotImplementedError() 

 def setdefault(self, key, default=None): 

 # YOUR CODE HERE 

 raise NotImplementedError() 

. . .

In [ ]:

# (4 points) Basic tests 

from unittest import TestCase 

import random 

tc = TestCase() 

class MyInt(int): 

 def __hash__(self): 

 """MyInts hash to themselves  already current Python default, 

 but just to ensure consistency.""" 

 return self 

def ll_len(l): 

 """Returns the length of a linked list with head `l` (assuming no sentinel)""" 

 c = 0 

 while l: 

 c += 1 

 l = l.next 

 return c 

ht = Hashtable(10) 

for i in range(25): 

 ht[MyInt(i)] = i*2 

tc.assertEqual(len(ht), 25) 

for i in range(5): 

 tc.assertEqual(ll_len(ht.buckets[i]), 3) 

for i in range(5, 10): 

 tc.assertEqual(ll_len(ht.buckets[i]), 2) 

for i in range(25): 

 tc.assertTrue(MyInt(i) in ht) 

 tc.assertEqual(ht[MyInt(i)], i*2) 

. . .

In [ ]:

# (4 points) Iterator testing 

from unittest import TestCase 

import random 

tc = TestCase() 

ht = Hashtable(100) 

d = {} 

for i in range(100): 

 k, v = str(i), str(random.randrange(10000000, 99999999)) 

 d[k] = v 

 ht[k] = v 

keys = set(ht.keys()) 

tc.assertEqual(len(keys), 100) 

for k in keys: 

 tc.assertTrue(k in ht) 

 tc.assertEqual(ht[k], d[k]) 

tc.assertEqual(sorted(ht.values()), sorted(d.values())) 

for k,v in ht.items(): 

 tc.assertEqual(d[k], v) 

. . .

In [ ]:

# (4 points) Deletion testing 

from unittest import TestCase 

import random 

tc = TestCase() 

ht = Hashtable(100) 

d = {} 

for i in range(100): 

 k, v = str(i), str(random.randrange(10000000, 99999999)) 

 d[k] = v 

 ht[k] = v 

for _ in range(50): 

 k = str(random.randrange(100)) 

 if k in d: 

 del d[k] 

 del ht[k] 

tc.assertEqual(len(ht), len(d)) 

for k,v in ht.items(): 

 tc.assertEqual(d[k], v) 

. . .

In [ ]:

# (4 points) Setdefault testing 

from unittest import TestCase 

import random 

tc = TestCase() 

ht = Hashtable(100) 

d = {} 

tc.assertEqual(ht.setdefault('1', '2'), '2') 

ht['3'] = '4' 

tc.assertEqual(ht.setdefault('3', '5'), '4') 

del ht['3'] 

tc.assertEqual(ht.setdefault('3', '6'), '6') 

tc.assertEqual(ht.setdefault('7'), None) 

ht['7'] = '8' 

tc.assertEqual(ht.setdefault('7'), '8') 

. . .

In [ ]:

# (4 points) Stress testing 

from unittest import TestCase 

import random 

tc = TestCase() 

ht = Hashtable(100000) 

d = {} 

for _ in range(100000): 

 k, v = str(random.randrange(100000)), str(random.randrange(10000000, 99999999)) 

 d[k] = v 

 ht[k] = v 

for k,v in d.items(): 

 tc.assertTrue(k in ht) 

 tc.assertEqual(d[k], ht[k])