(Optional) Question: Implement a python-friendly interface for the hash table

I’m struggling with the logic in the HashTable class for the optional question. For the get_valid_index function i’m using the built in has function and passing in key as the argument and finding the remainder of the length of the data list variable set from the constructor method. Am I using the implementation of the built in hash function and linear probing correctly with the get_valid_index function? The two cells after return False and they are supposed to return True, but the 3rd cell returns True so I’m confused.

MAX_HASH_TABLE_SIZE = 4096
class HashTable:
def __init__(self, max_size=MAX_HASH_TABLE_SIZE):
    self.data_list = [None] * max_size

def get_valid_index(self, key):
    # Use Python's in-built `hash` function and implement linear probing
    idx = hash(key) % len(self.data_list)
    
def __getitem__(self, key):
    # Implement the logic for "find" here
    idx = get_valid_index(self.data_list, key) # find index for key
    kv = self.data_list[idx] # retreive key value(kv) stored at index

def __setitem__(self, key, value):
    # Implement the logic for "insert/update" here
    idx = get_valid_index(self.data_list, key) #find index for key
    self.data_list[idx] = key, value #store key-value pair at correct index

def __iter__(self):
    return (x for x in self.data_list if x is not None)

def __len__(self):
    return len([x for x in self])

def __repr__(self):
    from textwrap import indent
    pairs = [indent("{} : {}".format(repr(kv[0]), repr(kv[1])), '  ') for kv in self]
    return "{\n" + "{}".format(',\n'.join(pairs)) + "\n}"

def __str__(self):
    return repr(self)

Hey…
After using hash function on the key you are taking the remainder from len(self.data_list). This is wrong.
You have to take the remainder the the max_size for which you have to create a variable
self.max_size = max_size in the __init__ method… and then use it for taking the remainder…
Hope it helps

Thanks! That makes more sense since self.max_size is an integer. I’m still getting the same results though. I thought that I implemented the correct logic for __getitem__ and __setitem__ functions as well. Do you notice any other flaws, I’ve made the edits you suggested.

MAX_HASH_TABLE_SIZE = 4096

 class HashTable:
    def __init__(self, max_size=MAX_HASH_TABLE_SIZE):
        self.data_list = [None] * max_size
        self.max_size = max_size
def get_valid_index(self, key):
    # Use Python's in-built `hash` function and implement linear probing
    idx = hash(key) % self.max_size
    
def __getitem__(self, key):
    # Implement the logic for "find" here
    idx = get_valid_index(self.data_list, key) # find index for key
    kv = self.data_list[idx] # retreive key value(kv) stored at index

def __setitem__(self, key, value):
    # Implement the logic for "insert/update" here
    idx = get_valid_index(self.data_list, key) #find index for key
    self.data_list[idx] = key, value #store key-value pair at correct index

Hey…
All your methods except the __init__ are wrongly implemented…
Sorry that I didn’t saw this in the original question itself…
Let’s go through them one by one…

def get_valid_index(self, key):
    # Use Python's in-built `hash` function and implement linear probing
    idx = hash(key) % self.max_size

In the above function, you are not returning idx that you have calculated…

def __getitem__(self, key):
    # Implement the logic for "find" here
    idx = get_valid_index(self.data_list, key) # find index for key
    kv = self.data_list[idx] # retreive key value(kv) stored at index

In this function first, you are calling get_valid_index the wrong way…
You need to call this as self.get_valid_index(key)
Also, you are not returning the value, you can do this by return kv[1]

def __setitem__(self, key, value):
    # Implement the logic for "insert/update" here
    idx = get_valid_index(self.data_list, key) #find index for key
    self.data_list[idx] = key, value #store key-value pair at correct index

Here also you need to call the get_valid_index as self.get_valid_index(key)

Hope this helps…
For reference, you can look at this and try to understand what’s really happening and not copy the solution…

Thank you! This is super helpful, I realize now that I was not pointing to the class instance and need to when trying to access different class methods that are defined in the HashTable class. Makes much more sense now!

1 Like