HashTable
code: python
from typing import Any, List, Optional
class Node:
def __init__(self, key: str, value: Any):
self.key = key
self.value = value
self.next: OptionalNode = None class HashTable:
def __init__(self, size: int = 10):
self.size = size
self.table: List[OptionalNode] = None * size # O(n), O(1)
def _hash(self, key: str) -> int:
return sum(ord(char) for char in key) % self.size
# O(n), O(1)
def insert(self, key: str, value: Any) -> None:
new_node = Node(key, value)
index = self._hash(key)
if self.tableindex is None: self.tableindex = new_node else:
current = self.tableindex while current:
if current.key == key:
current.value = value
return
if current.next is None:
current.next = new_node
return
current = current.next
# O(n), O(1)
def get(self, key: str) -> Any:
index = self._hash(key)
current = self.tableindex while current:
if current.key == key:
return current.value
current = current.next
raise KeyError(key)
# O(n), O(1)
def remove(self, key: str) -> None:
index = self._hash(key)
if self.tableindex is None: raise KeyError(key)
if self.tableindex.key == key: return
current = self.tableindex while current.next:
if current.next.key == key:
current.next = current.next.next
return
current = current.next
raise KeyError(key)
import pytest
def test_insert_and_get():
ht = HashTable()
ht.insert("name", "Alice")
ht.insert("age", 30)
assert ht.get("name") == "Alice"
assert ht.get("age") == 30
def test_update_existing_key():
ht = HashTable()
ht.insert("name", "Alice")
ht.insert("name", "Bob")
assert ht.get("name") == "Bob"
def test_remove():
ht = HashTable()
ht.insert("name", "Alice")
ht.remove("name")
with pytest.raises(KeyError):
ht.get("name")
def test_get_nonexistent_key():
ht = HashTable()
with pytest.raises(KeyError):
ht.get("nonexistent")
def test_remove_nonexistent_key():
ht = HashTable()
with pytest.raises(KeyError):
ht.remove("nonexistent")
def test_hash_collision():
ht = HashTable(size=1)
ht.insert("name", "Alice")
ht.insert("age", 30)
assert ht.get("name") == "Alice"
assert ht.get("age") == 30
def test_remove_with_collision():
ht = HashTable(size=1)
ht.insert("name", "Alice")
ht.insert("age", 30)
ht.insert("city", "New York")
ht.remove("age")
assert ht.get("name") == "Alice"
assert ht.get("city") == "New York"
with pytest.raises(KeyError):
ht.get("age")