Assignment 2 - Hash Tables and Python Dictionaries

:zap: In this assignment, you will apply the concepts learned in Lecture 1 and Lecture 2

  • Implement hash tables from scratch in Python
  • Handle hashing collisions using linear probing
  • Replicate the functionality of Python dictionaries
  • Ask questions and help others on the forum

:ledger: Assignment Notebook

Assignment 2 - Hash Tables and Python Dictionaries

Use the starter notebook(s) to get started with the assignment. Read the problem statement, follow the instructions, add your solutions, and make a submission.

:handshake: Share your work

Share your work on the Share Your Work Category on the respective monthly threads.

2 Likes

Stuck on def list_all(self):
# 1. Extract the key from each key-value pair

If I use return [self.data_list] I get the entire self which is a list like:
[…None, None, None, None, None, ‘7777777777’, None, None,… None, ‘8888888888’,None, None, None,…]]

As the list only contains the value in a hashtable (no key is stored here). How do I get the key? Can’t inverse ord() function.

Hi,
You may try this:
return [kv[0] for kv in self.data_list if kv is not None]

Store both key and value, not just value.

1 Like

Sir, could you please elaborate?
I have tried storing both key, value pair but still my assignment fails on Question 5.

where is it possibly failing? We are required to store the (key, value) pair as a tuple in the index, calculated using the hash function. Try to read the notes/comments provided in the notebook.

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(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]

This is the Question and I believe there is nothing wrong with this implementation but still it fails.

Absolutely right! No bugs here. Check get_valid_index() implementation, something might be wrong here.

Oops check update() also, their is a bug.

Thank you for taking time to review my implementation.
But I don’t seem to find anything wrong with the implementation nor did I find anything wrong with the update method.

How is it possible that i gt Q2 and Q4 fail while having Q5 passed? all my output returns ‘True’ though

check get_valid_index in function update and other functions (param does not seem to match signature). Also if possible avoid sharing code, is there a way to message people?

Besides what exactly is code failing? Are you not getting expected results in a particular question or the code throws error?

1 Like

Get_valid_index() takes two arguments, provided only one. Pass the list as well as the key.

1 Like

It occurred with me too.

Hint:

Q2. Check for local/global variable
Q4. Check the matching statement/criteria in the ‘if’ statement. What should match what, as described in the comment?

1 Like

I had the same issue and it took me a little bit to spot it. To expand on what @rajibdasbhagat replied with, go through each of the get_index and get_valid_index functions and make sure you are doing exactly what the comments are asking you to do.

1 Like

Ahhh yess, thanks mate.
Btw it’s really strange that I didn’t pass this positional argument but still the interpreter didn’t throw any errors.

@hemanth @aakashns I have submitted assignment 2 of hash tables and it says that my submission has failed when I believe I have done everything right. Can you please check and let me know?

@hemanth, My assignment 2 submission says Q5 FAIL when I believe everything I did was right. Can you tell what Q5 was in case I need to correct it?

Question numbers are mentioned in the assignment notebook.

@aakashns Thanks for replying. But, I have followed all the instructions in the Q5 code block and got all outcomes as TRUE as well. Still, it shows fail. Can you please help me with it? https://jovian.ai/sankalpsaoji98/python-hash-tables-assignment is my assignment. Thanks.