hash_table.py

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