Assignment 2 - Hash Tables in Python

In this assignment, you will re-implement Python dictionaries from scratch using hash tables. As you go through this notebook, you will find a ??? in certain places. To complete this assignment, you must replace all the ??? with appropriate values, expressions or statements to ensure that the notebook runs properly end-to-end.

Guidelines

Make sure to run all the code cells, otherwise you may get errors like NameError for undefined variables.
Do not change variable names, delete cells or disturb other existing code. It may cause problems during evaluation.
In some cases, you may need to add some code cells or new statements before or after the line of code containing the ???.
There are some tests included with this notebook to help you test your implementation. However, after submission your code will be tested with some hidden test cases. Make sure to test your code exhaustively to cover all edge cases.

This tutorial is an executable Jupyter notebook. Click the Open in Colab button at the top of this page to execute the code.

Jupyter Notebooks: This notebook is made of cells. Each cell can contain code written in Python or explanations in plain English. You can execute code cells and view the results instantly within the notebook. Jupyter is a powerful platform for experimentation and analysis. Don't be afraid to mess around with the code & break things - you'll learn a lot by encountering and fixing errors. You can use the "Kernel > Restart & Clear Output" menu option to clear all outputs and start again from the top.

Problem Statement - Hash Tables

In this assignment, you will recreate Python dictionaries from scratch using data structure called hash table. Dictionaries in Python are used to store key-value pairs. Keys are used to store and retrieve values. For example, here's a dictionary for storing and retrieving phone numbers using people's names.

phone_numbers = {
  'Aakash' : '9489484949',
  'Hemanth' : '9595949494',
  'Siddhant' : '9231325312'
}

phone_numbers

{'Aakash': '7878787878',
 'Hemanth': '9595949494',
 'Siddhant': '9231325312',
 'Vishal': '8787878787'}

You can access a person's phone number using their name as follows:

phone_numbers['Aakash']

'9489484949'

You can store new phone numbers, or update existing ones as follows:

phone_numbers['Vishal'] = '8787878787'

phone_numbers['Aakash'] = '7878787878'

phone_numbers

{'Aakash': '7878787878',
 'Hemanth': '9595949494',
 'Siddhant': '9231325312',
 'Vishal': '8787878787'}

You can also view all the names and phone numbers stored in phone_numbers using a for loop.

for name in phone_numbers:
    print('Name:', name, ', Phone Number:', phone_numbers[name])

Name: Aakash , Phone Number: 7878787878
Name: Hemanth , Phone Number: 9595949494
Name: Siddhant , Phone Number: 9231325312
Name: Vishal , Phone Number: 8787878787

Dictionaries in Python are implemented using Hash Tables. A hash table uses a list/array to store the key-value pairs, and uses a hashing function to determine the index for storing or retrieving the data associated with a given key. Here's a visual representation:

Your object is to implement a HashTable class which supports the following operations:

Insert: Insert a new key-value pair
Find: Find the value associated with a key
Update: Update the value associated with a key
List: List all the keys stored in the hash table

The HashTable class will have the following structure (note the function signatures):

class HashTable:
    def insert(self, key, value):
        """Insert a new key-value pair"""
        pass
    
    def find(self, key):
        """Find the value associated with a key"""
        pass
    
    def update(self, key, value):
        """Change the value associated with a key"""
        pass
    
    def list_all(self):
        """List all the keys"""
        pass

Data List

We'll build the HashTable class step-by-step. The first step is to create a Python list which will hold all the key-value pairs. We'll start by creating a list of a fixed size.

MAX_HASH_TABLE_SIZE = 4096

QUESTION 1: Create a Python list of size MAX_HASH_TABLE_SIZE, with all the values set to None.

Hint: Use the * operator.

# List of size MAX_HASH_TABLE_SIZE with all values None
data_list = ???

If the list was created successfully, the following cells should output True.

len(data_list) == 4096

True

data_list[99] == None

True

Hashing Function

A hashing function is used to convert strings and other non-numeric data types into numbers, which can then be used as list indices. For instance, if a hashing function converts the string "Aakash" into the number 4, then the key-value pair 'Aakash': '7878787878' will be stored at the position 4 within the data list.

Here's a simple algorithm for hashing, which can convert strings into numeric list indices.

Iterate over the string, character by character
Convert each character to a number using the ord function.
Add the numbers for each character to obtain the hash for the entire string
Take the remainder of the result with the size of the data list

QUESTION 2: Complete the get_index function below which implements the hashing algorithm described above.

def get_index(data_list, a_string):
    # Variable to store the result (updated after each iteration)
    result = 0
    
    for a_character in a_string:
        # Convert the character to a number
        a_number = ???
        # Update result by adding the number
        result += ???
    
    # Take the remainder of the result with the size of the data list
    list_index = result % ???
    return list_index

If the get_index function was defined correctly, the following cells should output True.

get_index(data_list, '') == 0

True

get_index(data_list, 'Aakash') == 585

True

get_index(data_list, 'Don O Leary') == 941

(Optional) Try out the get_index function using the empty cells below.

To insert a key-value pair into a hash table, we can simply get the hash of the key, and store the pair at that index in the data list.

key, value = 'Aakash', '7878787878'

idx = get_index(data_list, key)
idx

data_list[idx] = (key, value)

Here's the same operation expressed in a single line of code.

data_list[get_index(data_list, 'Hemanth')] = ('Hemanth', '9595949494')

The retrieve the value associated with a pair, we can get the hash of the key and look up that index in the data list.

idx = get_index(data_list, 'Aakash')
idx

key, value = data_list[idx]
value

'7878787878'

To get the list of keys, we can use a simple list comprehension.

pairs = [kv[0] for kv in data_list if kv is not None]

pairs

['Aakash', 'Hemanth']

Basic Hash Table Implementation

We can now use the hashing function defined above to implement a hash table in Python.

Question 4: Complete the hash table implementation below by following the instructions in the comments.

Hint: Insert and update may have identical implementations.

class BasicHashTable:
    def __init__(self, max_size=MAX_HASH_TABLE_SIZE):
        # 1. Create a list of size `max_size` with all values None
        self.data_list = ???
     
    
    def insert(self, key, value):
        # 1. Find the index for the key using get_index
        idx = get_index(self.data_list, ???)
        
        # 2. Store the key-value pair at the right index
        self.data_list[idx] = ???
    
    
    def find(self, key):
        # 1. Find the index for the key using get_index
        idx = ???
        
        # 2. Retrieve the data stored at the index
        kv = ???
        
        # 3. Return the value if found, else return None
        if kv is None:
            return None
        else:
            key, value = kv
            return value
    
    
    def update(self, key, value):
        # 1. Find the index for the key using get_index
        idx = ???
        
        # 2. Store the new key-value pair at the right index
        self.data_list[idx] = ???

    
    def list_all(self, key):
        # 1. Extract the key from each key-value pair 
        return [??? for kv in self.data_list if kv is not None]

If the BasicHashTable class was defined correctly, the following cells should output True.

basic_table = BasicHashTable(max_size=1024)
len(basic_table.data_list) == 1024

True

# Insert some values
basic_table.insert('Aakash', '9999999999')
basic_table.insert('Hemanth', '8888888888')

# Find a value
basic_table.find('Hemanth') == '8888888888'

True

# Update a value
basic_table.update('Aakash', '7777777777')

# Check the updated value
basic_table.find('Aakash') == '7777777777'

True

# Get the list of keys
basic_table.list_all() == ['Aakash', 'Hemanth']

True

(Optional) Test your implementation of BasicHashTable with some more examples below.

Handling Collisions with Linear Probing

As you might have wondered, multiple keys can have the same hash. For instance, the keys "listen" and "silent" have the same hash. This is referred to as collision. Data stored against one key may override the data stored against another, if they have the same hash.

basic_table.insert('listen', 99)

basic_table.insert('silent', 200)

basic_table.find('listen')

As you can see above, the value for the key listen was overwritten by the value for the key silent. Our hash table implementation is incomplete because it does not handle collisions correctly.

To handle collisions we'll use a technique called linear probing. Here's how it works:

While inserting a new key-value pair if the target index for a key is occupied by another key, then we try the next index, followed by the next and so on till we the closest empty location.
While finding a key-value pair, we apply the same strategy, but instead of searching for an empty location, we look for a location which contains a key-value pair with the matching key.
While updating a key-value pair, we apply the same strategy, but instead of searching for an empty location, we look for a location which contains a key-value pair with the matching key, and update its value.

We'll define a function called get_valid_index, which starts searching the data list from the index determined by the hashing function get_index and returns the first index which is either empty or contains a key-value pair matching the given key.

Question 5: Complete the function get_valid_index below by following the instructions in the comments.

def get_valid_index(data_list, key):
    # Start with the index returned by get_index
    idx = ???
    
    while True:
        # Get the key-value pair stored at idx
        kv = ???
        
        # If it is None, return the index
        if ???:
            return idx
        
        # If the stored key matches the given key, return the index
        k, v = kv
        if ???:
            return idx
        
        # Move to the next index
        idx += 1
        
        # Go back to the start if you have reached the end of the array
        if idx == len(data_list):
            idx = 0

If get_valid_index was defined correctly, the above cells should output True.

# Create an empty hash table
data_list = [None] * MAX_HASH_TABLE_SIZE

# New key 'listen' should return expected index
get_valid_index(data_list, 'listen') == 655

True

# Insert a key-value pair for the key 'listen'
data_list[get_index(data_list, 'listen')] = ('listen', 99)

# Colliding key 'silent' should return next index
get_valid_index(data_list, 'silent') == 656

True

(Optional) Test your implementation of get_valid_index on some more examples using the empty cells below.

Hash Table with Linear Probing

Question 6: Complete the hash table (with linear probing) implementation below by following the instructions in the comments.

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 = ???
     
    
    def insert(self, key, value):
        # 1. Find the index for the key using get_valid_index
        idx = get_valid_index(self.data_list, ???)
        
        # 2. Store the key-value pair at the right index
        self.data_list[idx] = ???
    
    
    def find(self, key):
        # 1. Find the index for the key using get_valid_index
        idx = ???
        
        # 2. Retrieve the data stored at the index
        kv = ???
        
        # 3. Return the value if found, else return None
        if kv is None:
            return None
        else:
            key, value = kv
            return value
    
    
    def update(self, key, value):
        # 1. Find the index for the key using get_valid_index
        idx = ???
        
        # 2. Store the new key-value pair at the right index
        self.data_list[idx] = ???

    
    def list_all(self):
        # 1. Extract the key from each key-value pair 
        return [??? for kv in self.data_list if kv is not None]

If the ProbingHashTable class was defined correctly, the following cells should output True.

# Create a new hash table
probing_table = ProbingHashTable()

# Insert a value
probing_table.insert('listen', 99)

# Check the value
probing_table.find('listen') == 99

True

# Insert a colliding key
probing_table.insert('silent', 200)

# Check the new and old keys
probing_table.find('listen') == 99 and probing_table.find('silent') == 200

True

# Update a key
probing_table.insert('listen', 101)

# Check the value
probing_table.find('listen') == 101

True

probing_table.list_all() == ['listen', 'silent']

True

(Optional) Test your implementation of ProbingHashTable using the empty cells below.

Submission

To save your work, select "File" > "Save a Copy in Drive" on Google Colab. Once the copy is created, click the "Share" button and select "Anyone with the link" under the "General Access" section to make this notebook publicly accessible.

Then, copy the notebook link and submit it on the assignment page.

(Optional) Python Dictionaries using Hash Tables

We can now implement Python dictionaries using hash tables. Also, Python provides a built-in function called hash which we can use instead of our custom hash function. It is likely to have far fewer collisions

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

MAX_HASH_TABLE_SIZE = 4096

class HashTable:
    def __init__(self, max_size=MAX_HASH_TABLE_SIZE):
        self.data = [None] * max_size
        
    def get_valid_index(self, key):
        # Use Python's in-built `hash` function and implement linear probing
        pass # change this
        
    def __getitem__(self, key):
        # Implement the logic for "find" here
        pass # change this
    
    def __setitem__(self, key, value):
        # Implement the logic for "insert/update" here
        pass # change this
    
    def __iter__(self):
        return (x for x in self.data 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)

If the HashTable class was defined correctly, the following cells should output True.

# Create a hash table
table = HashTable()

# Insert some key-value pairs
table['a'] = 1
table['b'] = 34

# Retrieve the inserted values
table['a'] == 1 and table['b'] == 34

True

# Update a value
table['a'] = 99

# Check the updated value
table['a'] == 99

True

# Get a list of key-value pairs
list(table) == [('b', 34), ('a', 99)]

True

Since we have also implemented the __repr__ and __str__ functions, the output of the next cell should be:

{
  'b' : 34
  'a' : 99
}

table

{
  'b' : 34
  'a' : 99
}

(Optional) Hash Table Improvements

Here are some more improvements/changes you can make to your hash table implementation:

Track the size of the hash table i.e. number of key-value pairs so that len(table) has complexity O(1).
Implement deletion with tombstones as described here: https://research.cs.vt.edu/AVresearch/hashing/deletion.php
Implement dynamic resizing to automatically grow/shrink the data list: https://charlesreid1.com/wiki/Hash_Maps/Dynamic_Resizing
Implement separate chaining, an alternative to linear probing for collision resolution: https://www.youtube.com/watch/T9gct6Dx-jo

(Optional) Complexity Analysis

With choice of a good hashing function and other improvements like dynamic resizing, you can

Operation	Average-case time complexity	Worst-case time complexity
Insert/Update	O(1)	O(n)
Find	O(1)	O(n)
Delete	O(1)	O(n)
List	O(n)	O(n)

Here are some questions to ponder upon?

What is average case complexity? How does it differ from worst-case complexity?
Do you see why insert/find/update have average-case complexity of O(1) and worst-case complexity of O(n) ?
How is the complexity of hash tables different from binary search trees?
When should you prefer using hash table over binary trees or vice versa?