Data Structure can you please explain this program? Thank you

%%file probing_methods.py class probing_methods: """ Collection of probing methods """ @staticmethod def linear_probe( self, key, i ): """ Implements linear probing. Note that linear probing is the same as modified linear probing with c=1. Therefore, this method only calls the method __modified_linear_probe__ with c=1. By reusing an existing method we end up taking advantage of this essential refactoring. Therefore, we will no longer need the following code:

original_hash_val = self.hash( key ) # Original hash value modified_hash_value = (original_hash_val + i) % self.M #print( f"--- original_hash_val: {original_hash_val}" ) return modified_hash_value

Instead all this will be a single line call! """ return probing_methods.__modified_linear_probe__( self, key, i, c=1 )

@staticmethod def __modified_linear_probe__( self, key, i, c ): """ This method will be called from the inner method returned by modified_linear_probe to implment modified linear probing. It will also be called directly by linear_probe() method. """ original_hash_val = self.hash( key ) # Original hash value modified_hash_value = (original_hash_val + i * c) % self.M #print( f"--- original_hash_val: {original_hash_val}" ) return modified_hash_value

@staticmethod def modified_linear_probe( c ): """ Note that we do not call a function here but return an inner function within which the c-value passed to this function will be captured. Note that all probing methods must have the call signature ( self, key, i ). That is, addition parameters must be captured by creating inner methods that will be returned from methods that will return those inner methods. """ def inner( self, key, i ): """ """ return probing_methods.__modified_linear_probe__( self, key, i, c ) return inner

@staticmethod def quadratic_probe( self, key, i ): """ Implements quadratic probing """ original_hash_val = self.hash( key ) # Original hash value modified_hash_value = (original_hash_val + i**2) % self.M #print( f"--- original_hash_val: {original_hash_val}" ) return modified_hash_value

@staticmethod def double_hashing( self, key, i, P=8 ): """ Implements double hashing """ hp = lambda key: 1 + key % P original_hash_val = self.hash( key ) # Original hash value modified_hash_value = (original_hash_val + i * hp( key )) % self.M #print( f"--- original_hash_val: {original_hash_val}" ) return modified_hash_value

#####_______________________________________________________#####

%%file hashtable.py from collections import namedtuple import pandas

pandas.options.display.width = 999 pandas.options.display.max_colwidth = 999

key_value_pair = namedtuple( 'key_value_pair', 'key value' )

class HashTableFullError( Exception ): pass

class hashtable: """ A hash table implementation """ def __init__( self, M, probing_method, null_key='', deleted_key='', table_name="slots" ): """ Intializes the hash table data structures """ self.M = M self.probing_method = probing_method self.n_collisions = 0

self.null_key = null_key self.deleted_key = deleted_key self.table_name = table_name self.table = [key_value_pair( null_key, None )] * M

def hash( self, key ): """ Returns the hash value for the specified key. """ return key % self.M

def is_available( self, index ): """ Returns True if the specified slot at the given slot index is available to store a value/key. If not, it returns False. """ # YOUR CODE HERE raise NotImplementedError() def set_value( self, index, key, value ): """ Sets the value of the slot at the given index to the provivded value. """ # YOUR CODE HERE raise NotImplementedError() def get_key( self, index ): """ Returns the key at the given index in the hash table """ # YOUR CODE HERE raise NotImplementedError()

def get_value( self, index ): """ Returns the value at the given index in the hash table """ # YOUR CODE HERE raise NotImplementedError()

def keys( self ): """ Returns the keys in the hash table """ # YOUR CODE HERE raise NotImplementedError()

def values( self ): """ Returns the values in the hash table """ # YOUR CODE HERE raise NotImplementedError() def __contains__( self, key ): """ Returns True if the specified key is in the current hash table; otherwise, it returns False """ # YOUR CODE HERE raise NotImplementedError() def todataframe( self ): """ Returns a pandas dataframe for easier viewing in notebooks """ return pandas.DataFrame( [self.table], index=["slots"] )

def __str__( self ): """ Returns a string representation of the hash table key index. """ df = pandas.DataFrame( [self.table] ) df.index = [self.table_name] return str( df ) def __repr__( self ): """ See __str__() """ return self.__str__() def search( self, key, is_verbose=False ): """ Returns the index of the slot for the specified key if that key is present in the hash table. Otherwise, it returns None. """ # YOUR CODE HERE raise NotImplementedError()

def remove( self, key, is_verbose=False ): """ Removes the indicated entry by key from the hash table, if that key key exists. If the key does not exist, this method raises an AssertionError """ # YOUR CODE HERE raise NotImplementedError()

def add( self, key, value, is_verbose=False ): """ Adds the provided (key, value) pair as a key_value_pair (defined above) to the hash table if the specified key is not there already. If the key already exists, it overwrites the existing value at that key. """ # YOUR CODE HERE raise NotImplementedError() def rehash( self, new_M, probing_method=None ): """ Rehashes the existing entries of this hash table according to the new M value. If a new probing method is specified, that method must be used. Otherwise, the existing probing method should be used. """ # YOUR CODE HERE raise NotImplementedError()

#####_______________________________________________________#####

TEST PREPARATION Run the following code cell as preparation for upcoming tests if you wish to run the test code to find out if your implementation works. However, you do not need to run any of the following tests. The following tests will be used to grade your work. In any case, you can take advantage of the existence of these tests. Note that you will not be able to see all the test code that will be run against your submission.

import string

M = 13 c = 3 keys = [765, 431, 96, 142, 579, 226, 903, 388] values = [c for c in string.ascii_uppercase]

#####_______________________________________________________#####

# # T E S T #1 # # # This test is to warn you in case you used 'import' statements in your code that are disallowed. # Be informed that all subsequent tests will check for the same implicitly. That is, if you # used 'import' in your code even once, all remaining tests will fail, which means # you will automatically get zero for this test! If you used 'import', it means you # did not heed the warnings provided to you already. If you have used 'import' that has been flagged by # this test, it is time to go back and FIX your code. # # Please do not be bothered how the following test code works. It checks whether you # have used any 'import' statements in your solution that are disallowed in code saved in `hashtable.py`. # # Free points are awarded if you code passes this test :) # import ast

def check_import( program_filepath, exceptions=["collections", "namedtuple", "pandas"] ): """ Returns all AST nodes that contain import statements, both import and impor from will be included """ import_statements = [] exceptions = set( exceptions )

with open( program_filepath ) as infile: # source = infile.read() parsed_ast = ast.parse( source ) nodes = [node for node in ast.walk( parsed_ast )]

for node in nodes: # if isinstance( node, ast.ImportFrom ) or isinstance( node, ast.Import ): # imported_module_names = set( [cur_node.name for cur_node in node.names] )

if imported_module_names - exceptions: # # Keep import statements that mention anything other than # the exceptions # import_statements.append( node )

return import_statements

def assert_no_imports( program_filepath ): """ Asserts that no import statements have been used in the provided program file """ import_statements = check_import( program_filepath ) import_linenos = [imp_ast_node.lineno for imp_ast_node in import_statements]

if len( import_statements ) > 0: # assert False, f"Disallowed import statements found at line(s) in {program_filepath}: {import_linenos}" else: print( "--- GOOD! You did not use any disallowed 'import' statements." )

program_filepath = "hashtable.py"

assert_no_imports( program_filepath )

print( ">>> TEST 1 PASSED <<<" )

#####_______________________________________________________#####

# # T E S T #2 # # from hashtable import hashtable, HashTableFullError from probing_methods import probing_methods

print( "=" * 80 ) print( "LINEAR PROBING" ) print( "=" * 80 )

ht = hashtable( M, probing_methods.linear_probe )

for cur_key, cur_value in zip( keys, values ): # ht.add( cur_key, cur_value )

print( f"--- KEYS: {ht.keys()} " ) print( f"--- VALUES: {ht.values()} " ) print( f"--- #Collisions: {ht.n_collisions} " )

assert ht.keys() == [388, '', 431, '', '', 96, 226, 579, 903, '', '', 765, 142] assert ht.values() == ['H', None, 'B', None, None, 'C', 'F', 'E', 'G', None, None, 'A', 'D'] assert ht.n_collisions == 5

print( ">>> TEST 2 PASSED <<<" )

# # T E S T #3 # # from hashtable import hashtable, HashTableFullError from probing_methods import probing_methods

print( "=" * 80 ) print( "LINEAR PROBING" ) print( "=" * 80 )

ht = hashtable( M, probing_methods.linear_probe )

for cur_key, cur_value in zip( keys, values ): # ht.add( cur_key, cur_value )

print( f"--- KEYS: {ht.keys()} " ) print( f"--- VALUES: {ht.values()} " ) print( f"--- #Collisions: {ht.n_collisions} " )

assert ht.search( 388 ) == (0, [11, 12, 0]) assert ht.search( 395 ) == (None, [5, 6, 7, 8, 9])

print( ">>> TEST 3 PASSED <<<" )