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

## 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) |

## 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

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

```
#! collision
print(table.hashKey('aya')) # 15
print(table.hashKey('yaa')) # 15
```

## Solutions of the Collision problem

###
1. **Open Addressing**

: is inserting the value directly if the*Linear Probing*`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...: operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found more details...*Quadratic Probing*: is applying another hash function to key*Double Hashing*`hashTable[(hashfunc1(key) + i * hashfunc2(key)) % sizeOfTheTable]`

more details...

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

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

### Node & Linked List Class

if you're not familiar with linked list check this article

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

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

#### hashKey method

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

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

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

#### delete method

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

#### printAll

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

#### All hash table methods

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

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

## References and useful Resources

- https://en.wikipedia.org/wiki/Quadratic_probing
- https://www.geeksforgeeks.org/hashing-set-3-open-addressing/
- 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.gatevidyalay.com/collision-resolution-techniques-separate-chaining/
- https://www.youtube.com/watch?v=1fEMyNXZynw
- https://www.youtube.com/watch?v=e1FbSMqyJRs
- https://www.geeksforgeeks.org/double-hashing/
- https://www.coursera.org/lecture/data-structures/applications-of-hashing-e4vuN
- https://www.youtube.com/watch?v=shs0KM3wKv8
- https://www.youtube.com/watch?v=sfWyugl4JWA

Have a great day :)

## Discussion (2)

Great explaination @ayabouchiha

Thank you so much @mayankpathak 🙏🙏

Have a good day 😊