Data Structure & Algorithms: Hash table

So, basically you are going to submit a dictionary to a hash function and the function will return you a value along with a list which contains the key & value of the dictionary you provided. The list then resides at that value of the memory.

Here we are going to take key & value of a dictionary and put it to a function (the box & gear one)

For example, using {"nails":1000} dictionary here

the hash returned a value 2 & a list with key & value.
This 2 is basically the address where the list will reside

Same goes for {"screws":800}

same for {"nuts":1200}

by the way note few things:

1. Hash is one way : That means that you are entering the dictionary and getting a value & a list . but you can not return these value & list to hash table to get the dictionary

2. Also it is Deterministic: This means that if you put {"nails":1000} into hash, every time it will just return 2. It will not give different values depending on different times. If you insert it for the 1st time , you will get 2. 2nd time still will result 2 and so on......

Also, to solve the issue of collisions , we can put an array inside our hash table or linked list . So, that we can have multiple amount of data and still get the same output.

or,

Constructor
Let create a class where we will keep an array data_map of size 7. [Note: Arrays sizes are fixed]

Also, this is going to be our hash method:

The reason we had the modulus and len(self.data_map) is that, we had 7 sized array and if we have anything divided by 7, we get reminder from 0 to 6. Thus we can keep our key values within the array. Got it?

Code for hash table:

class HashTable:
    def __init__(self, size = 7):
        self.data_map = [None] * size

    def __hash(self, key):
        my_hash = 0
        for letter in key:
            my_hash = (my_hash + ord(letter) * 23) % len(self.data_map)
        return my_hash  

    def print_table(self):
        for i, val in enumerate(self.data_map): 
            print(i, ": ", val)


my_hash_table = HashTable()

my_hash_table.print_table()

It will have a output like this as we have no value assigned yet.

Set method to set key and values within the table

whole code including the set method:

class HashTable:
    def __init__(self, size = 7):
        self.data_map = [None] * size

    def print_table(self):
        for i, val in enumerate(self.data_map): 
            print(i, ": ", val)

    def __hash(self, key):
        my_hash = 0
        for letter in key:
            my_hash = (my_hash + ord(letter) * 23) % len(self.data_map)
        return my_hash  

    #created the set method
    def set_item(self, key, value):
        index = self.__hash(key) #cheks the index of the key
        if self.data_map[index] == None: #if there is no array already reated within the array, creates one array
            self.data_map[index] = []
        self.data_map[index].append([key, value]) #appends key and value within the array


my_hash_table = HashTable()

my_hash_table.set_item('bolts', 1400)
my_hash_table.set_item('washers', 50)
my_hash_table.set_item('lumber', 70)

my_hash_table.print_table()

Get the key and value

Code for the get code

class HashTable:
    def __init__(self, size = 7):
        self.data_map = [None] * size

    def __hash(self, key):
        my_hash = 0
        for letter in key:
            my_hash = (my_hash + ord(letter) * 23) % len(self.data_map)
        return my_hash  

    def print_table(self):
        for i, val in enumerate(self.data_map): 
            print(i, ": ", val)

    def set_item(self, key, value):
        index = self.__hash(key)
        if self.data_map[index] == None:
            self.data_map[index] = []
        self.data_map[index].append([key, value])


    #creating the get method
    def get_item(self, key):
        index = self.__hash(key) #looks for the index of the key
        if self.data_map[index] is not None: #if there is an array within the array, it will return the value
            for i in range(len(self.data_map[index])): #loops through the array and sets value for i using the length of it
                if self.data_map[index][i][0] == key: #if it founds the key, sends the value of it
                    return self.data_map[index][i][1]
        return None #else returns none as nothing is out there


my_hash_table = HashTable()

my_hash_table.set_item('bolts', 1400)
my_hash_table.set_item('washers', 50)

#check for values using key 
print(my_hash_table.get_item('bolts'))
print(my_hash_table.get_item('washers'))
print(my_hash_table.get_item('lumber'))

Output:

All keys

Lets create a method to store all of the keys we have out there.

Code:

class HashTable:
    def __init__(self, size = 7):
        self.data_map = [None] * size

    def __hash(self, key):
        my_hash = 0
        for letter in key:
            my_hash = (my_hash + ord(letter) * 23) % len(self.data_map)
        return my_hash  

    def print_table(self):
        for i, val in enumerate(self.data_map): 
            print(i, ": ", val)

    def set_item(self, key, value):
        index = self.__hash(key)
        if self.data_map[index] == None:
            self.data_map[index] = []
        self.data_map[index].append([key, value])

    def get_item(self, key):
        index = self.__hash(key)
        if self.data_map[index] is not None:
            for i in range(len(self.data_map[index])):
                if self.data_map[index][i][0] == key:
                    return self.data_map[index][i][1]
        return None


    #Keys method
    def keys(self):
        all_keys = [] #creating an array to store the keys
        for i in range(len(self.data_map)): #loops through the array
            if self.data_map[i] is not None: # checkes if the array is empty or there is an array within it
                for j in range(len(self.data_map[i])): #loops through the inside array
                    all_keys.append(self.data_map[i][j][0]) #if found an array, stores the first values within the all_key array
        return all_keys


my_hash_table = HashTable()

my_hash_table.set_item('bolts', 1400)
my_hash_table.set_item('washers', 50)
my_hash_table.set_item('lumber', 70)

print(my_hash_table.keys())

Output:

**
Let's solve an interview problem:
**

Assume that you have 2 lists A=[2,4,5] and B=[0,8,5]
check if there is anything common within the lists/array:

Okay, so we can have 2 approaches:

1. Use nested loop to iterate ( We will need 2 loops thus it will be O(n^2) )

code for that:

def item_in_common(list1, list2):
    for i in list1:
        for j in list2:
            if i == j:
                return True
    return False

list1 = [1,3,5]
list2 = [2,4,6]

print(item_in_common(list1, list2))

1. Create a dictionary using first array and then using the second array check if it is there. (This will have O(2n)== O(n) thus it will be preferable)

def item_in_common(list1, list2):
    my_dict = {}
    for i in list1:
        my_dict[i] = True

    for j in list2:
        if j in my_dict:
            return True

    return False


list1 = [1,3,5]
list2 = [2,4,6]


print(item_in_common(list1, list2))

So, where have we used hash table, right? We did not need here. But dictionary is a simple version of hash table.

Done! Lets enjoy