Toy demo for demostrating the implementation of a dictionary in python

toy_dict.py

"""
This code snippet explains the implementation of a dictionary using a hashing function.
Problem: Store the marks of student with given roll numbers in a data structure for quick access of marks based on roll number. 
Concept: Use a dictionary data structure. 
"""
roll_numbers = [9,8,7,2,1,3,4,5]
marks = [10,20,5,13,77,33,2,99]

HASH_CONST=11 # Constant used for hashing. For practical purposes more sophesticated and optimized hash functions are used. 

"""
Hash function should always return a unique value for a given input. 
This ensures faster lookup for an input.
"""
def hash_f(n):
    return n % HASH_CONST # Simply return the remainder of the number when divided by the HASH_CONST


"""
Initialize the data structure with default values which are invalid. 
Roll numbers can never be less than 0 because the hash function can never give a value less than 0. 
Data structure can have at max HASH_CONST number of values.
"""
data_struct = [-1]*HASH_CONST

print "Roll Numbers: %s\nMarks: %s\nEmpty Data Structure: %s" % (roll_numbers, marks, data_struct)

"""
In the data structure store the marks using the hash as an index. 
This will lead to faster lookup for the marks of a given student based on just their roll numbers.
Without using the hashing trick one would have looked at all the elements of the roll_numbers array
to find the index of the desired input roll number. 
Then we would have returned the value at the same index from the marks array.
Using the new data structure we can just do this in one pass. 
However, there is a one time cost of creating the data structure at the begining.
Also, the resulting data structure may require more memory than the original set of 2 arrays depending on the HASH_CONST used.
"""
for i in range(len(a)):
    data_struct[hash_f(roll_numbers[i])] = marks[i] # Store the marks at the index found using hash_f

print "Final Data structure: ", data_struct

# Pretty print the array
for i, v in enumerate(data_struct):
    print "data_struct[%s] = %s" % (i,v)
    
# An example of fast access to an element using its roll number as a key.
print "Marks of roll number %s are %s" % (2, data_struct[hash_f(2)])

"""
In practice this data structure is called a dictionary or a hash map.
The storing schema is called key value pairs. 
This is similar, but not identical, to using a primary key in a database. 
A dictionary might resolve hash collissions (2 keys with same hash) by using an array to store multiple values for same hash.
"""


"""
Output of the above code:
Roll Numbers: [9, 8, 7, 2, 1, 3, 4, 5]
Marks: [10, 20, 5, 13, 77, 33, 2, 99]
Empty Data Structure: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
Final Data structure:  [-1, 77, 13, 33, 2, 99, -1, 5, 20, 10, -1]
data_struct[0] = -1
data_struct[1] = 77
data_struct[2] = 13
data_struct[3] = 33
data_struct[4] = 2
data_struct[5] = 99
data_struct[6] = -1
data_struct[7] = 5
data_struct[8] = 20
data_struct[9] = 10
data_struct[10] = -1
Marks of roll number 2 are 13
"""

Roll Numbers: [9, 8, 7, 2, 1, 3, 4, 5]
Marks: [10, 20, 5, 13, 77, 33, 2, 99]
Empty Data Structure: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
Final Data structure: [-1, 77, 13, 33, 2, 99, -1, 5, 20, 10, -1]
data_struct[0] = -1
data_struct[1] = 77
data_struct[2] = 13
data_struct[3] = 33
data_struct[4] = 2
data_struct[5] = 99
data_struct[6] = -1
data_struct[7] = 5
data_struct[8] = 20
data_struct[9] = 10
data_struct[10] = -1
Marks of roll number 2 are 13