Hash Table data structure
Tags: algorithms, beginners, codenewbie, python
Published: 2021-06-16 21:12:21

Hi, this is \#day_4, we are going to talk about **hash tables**

## Definition of Hash table
> "A hash table is a type of data structure that stores key-value pairs. The key is sent to a hash function that performs arithmetic operations on it. The result (commonly called the hash value or hash) is the index of the key-value pair in the hash table."
>- *[www.educative.io](https://www.educative.io/edpresso/what-is-a-hash-table)*

## Application of hash tables
 
+ Password verification
+ File System
+ Programming Language
+ Rabin-Karp Algorithm
+ School system
+ Search Engines
+ Driver's license record

## Space and Time complexity

The **space complexity** of the hash table is **O(n)**

|         	| insert 	| delete 	| search 	|
|---------	|--------	|--------	|--------	|
| Average 	| O(1)   	| O(1)   	| O(1)   	|
| Worst   	| O(n)   	| O(n)   	| O(n)   	|

[*wikipedia*](https://en.wikipedia.org/wiki/Hash_table)
[*freeCodeCamp*](https://www.freecodecamp.org/news/javascript-hash-table-associative-array-hashing-in-js/)

## Collision

**Collision** is when two keys or more result the same value after hashing them.
**example**:
#### Data:
| Name ( key )  | grade (  value ) |
|:-------------:|:----------------:|
| aya           | 77               |
| yaa           | 83               |

#### Hash function example 
```python
    def hashKey(self,key) -> int:
        """
            ord  -> built-in method that returns the Unicode code of a character 
            size -> the hash table length
            using (hashedString % self.size) -> for not getting an index out of the range of our hash table length
        """
        hashedString = 0
        for character in key:
            hashedString += ord(character)
        return hashedString % self.size

```
#### Getting the hashed names ( hashed keys )

````python
#! collision
print(table.hashKey('aya')) # 15
print(table.hashKey('yaa')) # 15
```
## Solutions of the Collision problem

###1. **Open Addressing** ###

+ **_Linear Probing_** : is  inserting the value directly if the `table[hashedKey]` is empty else inserting It into the next value `table[(key + 1) % sizeOfTheTable ]` if it available  Otherwise tring for the next index until finding an empty place [more details...](https://www.log2base2.com/algorithms/searching/linear-probing-hash-table.html)

+ **_Quadratic Probing_** : operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found [more details...](https://www.geeksforgeeks.org/quadratic-probing-in-hashing/)  

+ **_Double Hashing_** : is applying another hash function to key`hashTable[(hashfunc1(key) + i * hashfunc2(key)) % sizeOfTheTable] 
` [more details...](https://www.geeksforgeeks.org/double-hashing/)

###2. **Separate Chainings** ###

This technique creates a linked list to the slot for which collision occurs and insert into the wanted value as a node which has three properties (key, value, next)[more details...](https://www.geeksforgeeks.org/implementing-our-own-hash-table-with-separate-chaining-in-java/)

## Implementation of the hash table (separate chaining) using python

Although *Hash table* are built-in data structure in programming languages such as **dictionary** in python, **Map** in javascript, let's try to implement it in python.
if you are not familiar with python you can find the **implementation of hash table** in other langauges in these links:
+ [javascript](https://www.freecodecamp.org/news/javascript-hash-table-associative-array-hashing-in-js/)
+ [java](https://www.geeksforgeeks.org/implementing-our-own-hash-table-with-separate-chaining-in-java/)
+ [c++](https://www.geeksforgeeks.org/c-program-hashing-chaining/)
+ [C](https://www.tutorialspoint.com/data_structures_algorithms/hash_table_program_in_c.htm)
+ [php](https://gist.github.com/meetrajesh/4282835)

### Node & Linked List Class
if you're not familiar with linked list check this [article](https://dev.to/ayabouchiha/linked-list-data-structure-4g7k)
```python
class Node:
    def __init__(self,key,value,next = None):
        self.key = key
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self)    :
        self.head = None
        self.size = 0

    def insertAtFirst(self,key,value):
        self.head = Node(key,value,self.head)
        self.size += 1
        
    def insertAtLast(self,key,value):
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(key,value)
        self.size+=1

    def remove(self, key):
        current = self.head
        previous = None
        if current.key == key:
            self.head = current.next
        else:
            while current.next:
                previous = current
                current = current.next
                if current.key == key:
                    previous.next = current.next
            self.size -= 1

    def find(self, key):
        current = self.head
        while current:
            if current.key == key:
                return current.value
            current = current.next

    def printAll(self):
        current = self.head
        while current:
            print(current.key,current.value)
            current = current.next

```
### Hash Table Class
```python
class HashTable:
    def __init__(self,size):
        self.table =[None] * size
        self.size = size
```
#### hashKey method
```python
    def hashKey(self,key) -> int:
        """
            ord  -> built-in method that returns the Unicode code of a character 
            size -> the hash table length
            using (hashedString % self.size) -> for not getting an index out of the range of our  hash table length
        """
        hashedString = 0
        for character in key:
            hashedString += ord(character)
        return hashedString % self.size
```
#### add method
```python
    def add(self, key, value):
        """
            The Logic:
            self.table[idx] is None 
                => create a linked list and insert into it a node that contains the giving key and the giving value
            self.table[idx] is not None:
                => insert into the linked list a node that contains the giving key and the giving value
        """
        idx = self.hashKey(key)
        if self.table[idx] is None:
            newLinkedList = LinkedList()
            newLinkedList.insertAtFirst(key,value)
            self.table[idx] = newLinkedList
        else:
            self.table[idx].insertAtLast(key, value)
```
#### get method

```python
    def get(self, key) -> any:
        idx = self.hashKey(key)
        if self.table[idx] is not None:
            return self.table[idx].find(key)
```
#### delete method

```python
    def delete(self, key):
        idx = self.hashKey(key)
        if self.table[idx] is not None:
            self.table[idx].remove(key)
```
#### printAll 

```python
    def printAll(self):
        for i in self.table:
            if i is not None:
                i.printAll()
```
#### All hash table methods
```python
class HashTable:
    def __init__(self,size):
        self.table =[None] * size
        self.size = size

    def hashKey(self,key) -> int:
        """
            ord  -> built-in method that returns the Unicode code of a character 
            size -> the hash table length
            using (hashedString % self.size) -> for not getting an index out of the range of our  hash table length
        """
        hashedString = 0
        for character in key:
            hashedString += ord(character)
        return hashedString % self.size

    def add(self, key, value):
        """
            The Logic:
            self.table[idx] is None 
                => create a linked list and insert into it a node that contains the giving key and the giving value
            self.table[idx] is not None:
                => insert into the linked list a node that contains the giving key and the giving value
        """
        idx = self.hashKey(key)
        if self.table[idx] is None:
            newLinkedList = LinkedList()
            newLinkedList.insertAtFirst(key,value)
            self.table[idx] = newLinkedList
        else:
            self.table[idx].insertAtLast(key, value)
            
    def get(self, key) -> any:
        idx = self.hashKey(key)
        if self.table[idx] is not None:
            return self.table[idx].find(key)

    def delete(self, key):
        idx = self.hashKey(key)
        if self.table[idx] is not None:
            self.table[idx].remove(key)

    def printAll(self):
        for i in self.table:
            if i is not None:
                i.printAll()
```
### Final Code
```python
class Node:
    def __init__(self,key,value,next = None):
        self.key = key
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self)    :
        self.head = None
        self.size = 0

    def insertAtFirst(self,key,value):
        self.head = Node(key,value,self.head)
        self.size += 1
        
    def insertAtLast(self,key,value):
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(key,value)
        self.size+=1

    def remove(self, key):
        current = self.head
        previous = None
        if current.key == key:
            self.head = current.next
        else:
            while current.next:
                previous = current
                current = current.next
                if current.key == key:
                    previous.next = current.next
            self.size -= 1

    def find(self, key):
        current = self.head
        while current:
            if current.key == key:
                return current.value
            current = current.next

    def printAll(self):
        current = self.head
        while current:
            print(current.key,current.value)
            current = current.next

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

    def hashKey(self,key) -> int:
        """
            ord  -> built-in method that returns the Unicode code of a character 
            size -> the hash table length
            using (hashedString % self. size) -> for not getting an index out of the range of our  hash table length
        """
        hashedString = 0
        for character in key:
            hashedString += ord(character)
        return hashedString % self.size

    def add(self, key, value):
        """
            The Logic:
            self.table[idx] is None 
                => create a linked list and insert into it a node that contains the giving key and the giving value
            self.table[idx] is not None:
                => insert into the linked list a node that contains the giving key and the giving value
        """
        idx = self.hashKey(key)
        if self.table[idx] is None:
            newLinkedList = LinkedList()
            newLinkedList.insertAtFirst(key,value)
            self.table[idx] = newLinkedList
        else:
            self.table[idx].insertAtLast(key, value)
            
    def get(self, key) -> any:
        idx = self.hashKey(key)
        if self.table[idx] is not None:
            return self.table[idx].find(key)

    def delete(self, key):
        idx = self.hashKey(key)
        if self.table[idx] is not None:
            self.table[idx].remove(key)

    def printAll(self):
        for i in self.table:
            if i is not None:
                i.printAll()
```
## Exercises 

[Exercises](https://www.google.com/amp/s/www.geeksforgeeks.org/practice-problems-on-hashing/amp/)
## References and useful Resources
+ [https://en.wikipedia.org/wiki/Quadratic_probing](https://en.wikipedia.org/wiki/Quadratic_probing)
+ [https://www.geeksforgeeks.org/hashing-set-3-open-addressing/](https://www.geeksforgeeks.org/hashing-set-3-open-addressing/)
+ [https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/](https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/)
+ [https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/#:~:text=Separate%20chaining%20is%20one%20of,into%20a%20specific%20linked%20list.](https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/#:~:text=Separate%20chaining%20is%20one%20of,into%20a%20specific%20linked%20list.)
+ [https://www.gatevidyalay.com/collision-resolution-techniques-separate-chaining/](https://www.gatevidyalay.com/collision-resolution-techniques-separate-chaining/)
+ [https://www.youtube.com/watch?v=1fEMyNXZynw](https://www.youtube.com/watch?v=1fEMyNXZynw)
+ [https://www.youtube.com/watch?v=e1FbSMqyJRs](https://www.youtube.com/watch?v=e1FbSMqyJRs)
+ [https://www.geeksforgeeks.org/double-hashing/](https://www.geeksforgeeks.org/double-hashing/)
+ [https://www.coursera.org/lecture/data-structures/applications-of-hashing-e4vuN](https://www.coursera.org/lecture/data-structures/applications-of-hashing-e4vuN)
+ [https://www.youtube.com/watch?v=shs0KM3wKv8](https://www.youtube.com/watch?v=shs0KM3wKv8)
+ [https://www.youtube.com/watch?v=sfWyugl4JWA](https://www.youtube.com/watch?v=sfWyugl4JWA)

Have a great day :)