Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Hash Table with Python
class HashNode:
def __init__(self, key, value):
self.next = None
self.key = key
self.value = value
class HashTable:
def __init__(self):
self.table = [None] * 101
def hash(self, key):
# Generate hash from key.
# Time O(N), Space O(1), where N is the length of key.
hashed = 0
for i in range(len(key)):
hashed = (256 * hashed + ord(key[i])) % 101
return hashed
def add(self, key, value):
# Add key, value.
# Time O(1), Space O(1), where N is the num of elements in hashtable.
bucket = self.hash(key)
if not self.table[bucket]:
self.table[bucket] = HashNode(key, value)
else:
temp = self.table[bucket]
while temp.next:
temp = temp.next
temp.next = HashNode(key, value)
def find(self, key):
# Find value from key.
# Time O(1), Space O(1), where N is the num of elements in hashtable.
bucket = self.hash(key)
if not self.table[bucket]:
return False
else:
temp = self.table[bucket]
while temp:
if temp.key == key:
return temp.value
temp = temp.next
return False
def delete(self, key):
# Delete key, value.
# Time O(1), Space O(1), where N is the num of elements in hashtable.
bucket = self.hash(key)
if not self.table[bucket]:
return False
else:
if self.table[bucket].key == key:
self.table[bucket] = None
else:
temp = self.table[bucket]
while temp:
if temp.next.key == key:
temp.next = temp.next.next
return
temp = temp.next
return False
@jafarlie
Copy link

jafarlie commented May 10, 2019

What happens when all of the cells are filled and then you continue adding elements to the linked list. This gives no advantage. Your HashTable should grow in size given your load factors reaches a limit.

@rohanrkamath
Copy link

rohanrkamath commented Aug 15, 2021

What happens when all of the cells are filled and then you continue adding elements to the linked list. This gives no advantage. Your HashTable should grow in size given your load factors reaches a limit.

When the hash table is full, you usually transfer the content to a bigger hash table. So maybe a function like a isFull() would help here...therefore dynamically creating a new hash table with a larger space (something like self.table *2).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment