Recreating Python Dictionaries from Scratch

Aditi Deodhar
Analytics Vidhya
Published in
2 min readFeb 12, 2021

--

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 = 4096class 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 :)

--

--

Aditi Deodhar
Analytics Vidhya

MSIS @ Northeastern University | Data Science Enthusiast