Skip to main content

​
Overview

The HashTable class provides a hash table data structure that maps keys to values. It uses separate chaining (linked lists) to handle hash collisions and provides O(1) average-case performance for insertions, deletions, and lookups.

​
Constructor

​
capacity
int
default:"20"
The initial capacity of the hashtable (number of buckets)
from dsa.hashtable import HashTable

# Create a hashtable with default capacity
ht = HashTable()

# Create a hashtable with custom capacity
ht = HashTable(capacity=50)

​
Attributes

​
count
int
The number of items currently stored in the hashtable
​
capacity
int
The total capacity (number of buckets) of the hashtable

​
Methods

​
hash_function

Compute a hash value for a given key. 
hash_function(key) -> int
​
key
any
The key to convert to a hash value
​
return
int
Hash value modded to the hashtable capacity
ht = HashTable()
hash_val = ht.hash_function("mykey")
print(hash_val)  # Integer between 0 and capacity-1

​
set

Set a key-value pair in the hashtable. If the key exists, replace the value; otherwise, create a new key-value pair. 
set(key, value)
​
key
any
The key to set or update
​
value
any
The value to associate with the key
ht = HashTable()
ht.set("name", "Alice")
ht.set("age", 30)
ht.set("name", "Bob")  # Updates existing key

​
get

Get the value associated with a given key. 
get(key) -> any
​
key
any
The key to look up
​
return
any
The value associated with the key, or None if the key is not found
ht = HashTable()
ht.set("name", "Alice")
value = ht.get("name")  # Returns "Alice"
missing = ht.get("missing")  # Returns None

​
key_exists

Check whether a key exists in the hashtable. 
key_exists(key) -> bool
​
key
any
The key to check for
​
return
bool
True if the key exists, False otherwise
ht = HashTable()
ht.set("name", "Alice")
print(ht.key_exists("name"))  # True
print(ht.key_exists("age"))   # False

​
remove

Remove a key-value pair from the hashtable. 
remove(key)
​
key
any
The key to remove
Raises: KeyError if the key is not found in the hashtable 
ht = HashTable()
ht.set("name", "Alice")
ht.remove("name")  # Removes the key-value pair

try:
    ht.remove("missing")
except KeyError as e:
    print(f"Key not found: {e}")

​
pop

Remove a key and return its value. If the key is not found, return a default value. 
pop(key, default=None) -> any
​
key
any
The key to remove
​
default
any
default:"None"
The value to return if the key is not found
​
return
any
The value associated with the key, or the default value if not found
ht = HashTable()
ht.set("name", "Alice")
value = ht.pop("name")  # Returns "Alice" and removes the key
missing = ht.pop("age", "Unknown")  # Returns "Unknown"

​
enumerate

Return an enumeration of key-value pairs in the hashtable. 
enumerate() -> enumerate
​
return
enumerate
Enumeration of key-value pairs as [key, value] lists
ht = HashTable()
ht.set("name", "Alice")
ht.set("age", 30)

for idx, (key, value) in ht.enumerate():
    print(f"{idx}: {key} = {value}")

​
show_buckets

Return a string displaying the contents of all buckets in the hashtable. 
show_buckets() -> str
​
return
str
A string representation of all buckets and their contents
ht = HashTable()
ht.set("name", "Alice")
ht.set("age", 30)
print(ht.show_buckets())
# Output shows each bucket and its chain of key-value pairs

​
Special Methods

​
__len__

Return the number of items in the hashtable. 
ht = HashTable()
ht.set("name", "Alice")
ht.set("age", 30)
print(len(ht))  # 2

​
__getitem__

Get a value using bracket notation. 
ht = HashTable()
ht.set("name", "Alice")
print(ht["name"])  # "Alice"

​
__setitem__

Set a value using bracket notation. 
ht = HashTable()
ht["name"] = "Alice"
ht["age"] = 30

​
__delitem__

Delete a key-value pair using the del keyword. 
ht = HashTable()
ht["name"] = "Alice"
del ht["name"]

​
__contains__

Check if a key exists using the in operator. 
ht = HashTable()
ht["name"] = "Alice"
print("name" in ht)  # True
print("age" in ht)   # False

​
__iter__

Iterate over all keys in the hashtable. 
ht = HashTable()
ht["name"] = "Alice"
ht["age"] = 30

for key in ht:
    print(key, ht[key])

​
__eq__

Compare two hashtables for equality. 
ht1 = HashTable()
ht1["name"] = "Alice"

ht2 = HashTable()
ht2["name"] = "Alice"

print(ht1 == ht2)  # True

​
__repr__

Return a string representation of the hashtable. 
ht = HashTable()
ht["name"] = "Alice"
ht["age"] = 30
print(ht)  # {name:Alice, age:30}

​
Complete Example

from dsa.hashtable import HashTable

# Create a hashtable
ht = HashTable(capacity=10)

# Add key-value pairs
ht["name"] = "Alice"
ht["age"] = 30
ht["city"] = "New York"

# Get values
print(ht["name"])  # Alice
print(ht.get("age"))  # 30

# Check existence
if "city" in ht:
    print(f"City: {ht['city']}")

# Update value
ht["age"] = 31

# Remove key
del ht["city"]

# Get size
print(len(ht))  # 2

# Iterate over keys
for key in ht:
    print(f"{key}: {ht[key]}")

​
Performance

  • Average Case:
    • Insert: O(1)
    • Lookup: O(1)
    • Delete: O(1)
  • Worst Case:
    • Insert: O(n) (all keys hash to same bucket)
    • Lookup: O(n)
    • Delete: O(n)

​
Notes

  • The hashtable uses separate chaining to handle collisions
  • Keys are converted to strings before hashing
  • The hash function uses polynomial rolling hash with multiplier 31
  • Default capacity is 20 buckets
  • The hashtable does not automatically resize

Build docs developers (and LLMs) love

Get started for freeTalk to us