Doubt in assignment 2 of Data structures and Algorithms

Working through the second assignment of Data structures and algorithms…pertaining to Hashtables.

my code for the last question is -
class ProbingHashTable:

def __init__(self, max_size=MAX_HASH_TABLE_SIZE):

    # 1. Create a list of size `max_size` with all values None

    self.data_list = [None] * max_size

     

def insert(self, key, value):

    # 1. Find the index for the key using get_valid_index

    idx = get_valid_index(self.data_list, key)

    

    # 2. Store the key-value pair at the right index

    self.data_list[idx] = (key,value)

    

def find(self, key):

    # 1. Find the index for the key using get_valid_index

    idx = get_valid_index(self.data_list, key)

    

    # 2. Retrieve the data stored at the index

    kv = self.data_list[idx]

    

    # 3. Return the value if found, else return None

    return None if kv is None else kv[1]

    

def update(self, key, value):

    # 1. Find the index for the key using get_valid_index

    idx = get_valid_index(self.data_list, key)

    

    # 2. Store the new key-value pair at the right index

    self.data_list[idx] = (key,value)



def list_all(self):

    # 1. Extract the key from each key-value pair 

    return [kv[0] for kv in self.data_list if kv is not None]

All of my previous question cells have given the correct outputs but this code is giving me all false outputs. can someone help or give me a hint?
Thanks in advance.

The Code seems correct to me, can you share the outputs you are getting, It should not give all False.
Make new cells and print probing_table.find method, or probing_table.list_all() and check if you are getting a correct output or not.

Hi,

I think you can try
return “[kv[1] for kv in self.data_list if kv is not None]”
instead of “return [kv[0] for kv in self.data_list if kv is not None]”

I have similar problem but with the first past of the assignment (class BasicHashTable). The length of the hash table is correct but the “insert” and “find” functions would return the wrong values. So when I run these functions from basic_table(), I’d get the values from the previous code snippets, meaning the new keys and values didn’t overwrite the current values at all.

I did try that but it is still evaluating to false.
Thanks for the help tho.

Yes. The values are not being overwritten which is why we are getting false as outputs.

The outputs are just False.
I’ll try the new cells thing you mentioned.
Thank you.

1 Like

Another doubt:
when implementing the Hashing function,the step 4 states that “take the remainder of the result with the size of the data list”. What does this mean and why are we doing this?
The whole algorithm -
Here’s a simple algorithm for hashing, which can convert strings into numeric list indices.

  1. Iterate over the string, character by character

  2. Convert each character to a number using Python’s built-in ord function.

  3. Add the numbers for each character to obtain the hash for the entire string

  4. Take the remainder of the result with the size of the data list

This is done to ensure in which empty cell of the list the given pair (key, value) must be inserted.
For example:
Take a simple list1=[None, None, None].
Insert 22, 30, 29

22 % len(list1) = 1 Hence, list1 = [None, 22, None]
30 % len(list1) = 0 Hence, list1 = [30, 22, None]
29 % len(list1) = 2 Hence, list1 = [30, 22, 29]

Hope it helps!!

1 Like

Understood.Thank you.
About the other question, I tried the get_index instead of get_valid_index for the ‘update’ instance. The output is still False for all the subsequent cells.

Hi, I’m sure their is a bug in your implementatio get_valid_index(). Re-check the implementation their.

class ProbingHashTable:
def init(self, max_size=MAX_HASH_TABLE_SIZE):
# 1. Create a list of size max_size with all values None
self.data_list = [None]*max_size
def insert(self, key, value):
# 1. Find the index for the key using get_valid_index
idx = get_valid_index(self.data_list, key)

    # 2. Store the key-value pair at the right index
    self.data_list[idx] = (key,value)
def find(self, key):
    # 1. Find the index for the key using get_valid_index
    idx = get_valid_index(data_list,key) 
    # 2. Retrieve the data stored at the index
    kv = self.data_list[idx]  
    # 3. Return the value if found, else return None
    return None if kv is None else kv[1] 
def update(self, key, value):
    # 1. Find the index for the key using get_valid_index
    idx = get_valid_index(data_list,key)   
    # 2. Store the new key-value pair at the right index
    self.data_list[idx] = key,value
def list_all(self):
    # 1. Extract the key from each key-value pair 
    return [kv[0] for kv in self.data_list if kv is not None]

I am facing an error when two hash values collide can someone tell if anything is wrong in the code.

Is this even correct? There is no self.init

Maybe the implementation of your get_value_index is wrong somewhere, check the get_value_index function implementation again.

The def __init__ function is used as a constructor for a class. But a class can be defined without calling self.__init__ too, as this is a just a Class defination and does not implement anything so yes this is correct.

Hello, I figured out my mistakes.
Thank you for the help.

Then, I am clueless how to create these 4 functions within the HashTable

Hi I also faced problems for Q5, may I kindly have some guidelines from you how you solve the question? Thanks a lot!

This is my get_valid_index().
Can me point me on the bug.

@phuonganh-thuy-do, I was getting the same. I had to add some print statements and rerun and cleanup. Are you running in colab or binder? I suspect it is colab that corrupts. I do my assignments in my jupyter notebook first and this finishes up real quick for me. I then fill stuff in jovian platform. You can then submit your homeworks.