Data Structure & Algorithms: Hash table
Tags: dsalgo
Published: 2022-09-01 06:35:53

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/056a9bykiz63cw6jpa64.png)
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
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/d4egman79erh72eau2cj.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nk30oqstx9pwonjmw7sb.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jwzxd0egb40hpy31g1yh.png)
the hash returned a value 2 & a list with key & value.
This 2 is basically the address where the list will reside

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z2jzy22jrwq88rmnjpno.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tuhoqs1zkpchcsoerg6k.png)
Same goes for {"screws":800} 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/58pxtw5lkynz3n5gq154.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3qdyl2vea4k0c1q726uc.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oqbyp4wlcj5xcwbn5wvh.png)
 
same for {"nuts":1200} 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y91hknm466fl013psaex.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/frth869dp3zbn8bm74zz.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kmado83x642ucfmk43q6.png)
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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/diekehzonh3hvy0e5yqe.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t9ky08wazbp4zkdu297n.png)

or,

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y5lpkjzg6jl0f76fwepr.png)



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x2w9maj19gp8p1xe5fp2.png)


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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jhdpu7qo94d6iojmy87f.png)

Also, this is going to be our hash method:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0016ownlprbowfrt9n6x.png)


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()
```


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gbfakjac0h7gls8ygwnm.png)
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()
```
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/28m4l6mr6ur2a698qhdo.png)


**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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oeq1ert3s1ueozhgx7tm.png)


**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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/07hmygxy6jvs6nlkqv0w.png)


**
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))
```

2. 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

<img src="https://media0.giphy.com/media/Nfs5y1kzJKfu/giphy.gif?cid=ecf05e472d3w835ptrri5m1p6ifnwl9mi7ope9pifvhpcxf6&rid=giphy.gif&ct=g">