Recreating Python Dictionaries from Scratch

Wondering how to do that?! Well, then continue reading… :)

As it is well known that Python Dictionaries are a data structure which are used to store key-value pairs; where “keys” are used to store and retrieve the stored “values”. For example, here is a dictionary for storing and retrieving the marks of students in a class;

# Creating a dictionary
result = 
{
  'A' : '20',
  'B' : '15',
  'C' : '10'
}
result
# Retrieving the marks using key value(here, name)
result['A']
# Add a new value
result['Z'] = '9'
# Update existing value
result['A'] = '11'
# View the updated dictionary
result
# View all the names and marks stored in result using a for loop
for name in result:
    print('Name:', name, ', Marks:', result[name])

Still wondering? How this works? Read ahead… :)

• Dictionaries in Python are implemented using a data structure called hash table.
• 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.

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):
        hash('key')
        
    def __getitem__(self, key):
        idx = get_valid_index(self.data_list, key)
        kv = self.data_list[idx]
        return None if kv is None else kv[1]
    
    def __setitem__(self, key, value):
        idx = get_valid_index(self.data_list, key)
        self.data_list[idx] = (key, value)     
    
    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)

After implementing the above function we can create Python Dictionaries as follows →

# 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
# Update a value
table['a'] = 99
# Check the updated value
table['a'] == 99
# Get a list of key-value pairs
list(table) == [('a', 99), ('b', 34)]
table
>>
{
  'a' : 99,
  'b' : 34
}

And DONE! The dictionary data structure in Python was successfully created from scratch :)