Skip to content

Instantly share code, notes, and snippets.

@syphh
Created September 17, 2022 11:45
Show Gist options
  • Save syphh/00b889c90b32f22c050c85dea5e55c77 to your computer and use it in GitHub Desktop.
Save syphh/00b889c90b32f22c050c85dea5e55c77 to your computer and use it in GitHub Desktop.
from typing import List, Any
class Node:
def __init__(self, key, value, nxt=None):
self.key: str = key
self.value: Any = value
self.nxt: Node = nxt
class LinkedList:
def __init__(self, head=None):
self.head: Node = head
def insert(self, key, value):
new_node = Node(key, value, self.head)
self.head = new_node
def search(self, key):
node = self.head
while node:
if node.key == key:
return node
node = node.nxt
return None
def delete(self, key):
if self.head and self.head.key == key:
self.head = self.head.nxt
return True
else:
node = self.head
while node and node.nxt and node.nxt.key != key:
node = node.nxt
if node:
node.nxt = node.nxt.nxt
return True
return False
def __repr__(self):
res = ''
head = self.head
while head:
res += str(head) + ' - > '
head = head.nxt
res += 'null'
return res
class HashTable:
def __init__(self):
self.capacity: int = 30
self.size: int = 0
self.load_factor: float = 0.75
self.slots: List[LinkedList] = [LinkedList() for _ in range(self.capacity)]
def hash_func(self, key):
total = 0
for ch in key:
total += ord(ch)
return total % self.capacity
def rehash(self):
old = self.slots
self.capacity *= 2
self.size = 0
self.slots = [LinkedList() for _ in range(self.capacity)]
for slot in old:
node = slot.head
while node:
self.insert(node.key, node.value)
node = node.nxt
def insert(self, key, value):
index = self.hash_func(key)
node = self.slots[index].search(key)
if node:
node.value = value
else:
self.slots[index].insert(key, value)
self.size += 1
if self.size/self.capacity > self.load_factor:
self.rehash()
def search(self, key):
index = self.hash_func(key)
node = self.slots[index].search(key)
return node is not None
def get(self, key):
index = self.hash_func(key)
node = self.slots[index].search(key)
return node.value if node else None
def delete(self, key):
index = self.hash_func(key)
if self.slots[index].delete(key):
self.size -= 1
phone_agenda = HashTable()
phone_agenda.insert("John Smith", "452865236")
phone_agenda.insert("Samy Sterious", "854125693")
phone_agenda.insert("Sarah Plick", "125846532")
phone_agenda.insert("Khaled Anas", "956234157")
key = "Samy Sterious"
print("Phone number of {}: {}".format(key, phone_agenda.get(key)))
print("Hash table slots:\n{}".format(phone_agenda))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment