Implementing hash table in Python using Tuples

Question

I am trying to implement a basic hash table using a list of tuples. The code produce the desired output. Please help me improve my code as I feel there are a lot of while loops.

#global variables to keep track of the hash table count = 0 size = 1000 def hash_table(size): return [None] * size def hash_item(key, value): return (key,value) def hash_func(key): #simple hash function index = hash(key) % 1000 return index def insert_hash(table,key,value): index = hash_func(key) item = hash_item(key,value) global count global size if count == size: raise Exception("Hash table limit reached") if table[index] == None: table[index] = item else: collision_handler(table, index, item) count = count + 1 def print_hash(table,key): index = hash_func(key) while table[index][0] != key: #in case there is a collision: index = index + 1 print(table[index]) def delete_hash(table,key): index = hash_func(key) while table[index][0] != key: index = index + 1 table.pop(index) def collision_handler(table,index,item): #handling collisions using open addressing while table[index] != None: index = index + 1 table[index] = item a = hash_table(size) b = hash_func('1') insert_hash(a, '1','john') print_hash(a,'1') delete_hash(a,'1') insert_hash(a,'1','edward') print_hash(a,'1') 

Answer 1

Despite the code produce the desired output in your simple test case, your implementation is quite flawed.

a = hash_table(size) insert_hash(a, 1, 'john') insert_hash(a, 2, 'edward') delete_hash(a, 1) print_hash(a, 2) 

Output:

Traceback (most recent call last): File "C:/Code Review/hash_table.py", line 53, in <module> print_hash(a, 2) File "C:/Code Review/hash_table.py", line 30, in print_hash while table[index][0] != key: #in case there is a collision: TypeError: 'NoneType' object is not subscriptable >>> 

The issue: table.pop(index) will move items after the one being delete forward by one position in the table. Given that they are indexed by the hash values, this would mean that they can't be found anymore.

a = hash_table(size) for _ in range(2000): insert_hash(a, 1, 'john') delete_hash(a, 1) 

Output:

Traceback (most recent call last): File "C:/Code Review/hash_table.py", line 51, in <module> insert_hash(a, 1, 'john') File "C:/Code Review/hash_table.py", line 22, in insert_hash if table[index] == None: IndexError: list index out of range >>> 

After each insert/delete, the table size has shrunk by one item. After a thousand insert/deletes, the table can't hold any values!

a = hash_table(size) insert_hash(a, 999, 'john') insert_hash(a, 999, 'edward') 

Output:

Traceback (most recent call last): File "C:/Code Review/hash_table.py", line 51, in <module> insert_hash(a, 999, 'edward') File "C:/Code Review/hash_table.py", line 25, in insert_hash collision_handler(table, index, item) File "C:/Code Review/hash_table.py", line 42, in collision_handler while table[index] != None: IndexError: list index out of range >>> 

A collision at the last slot in the hash table doesn't have room to handle the collision, despite the table only having a 999 empty slots. You need to use circular addressing.

You need to add more test cases, and rework the code to handle these issues. I generated these issues quickly by exploiting the fact that hash(int) == int for sufficiently small integers, but they would arise using strings for keys as well. It is just be harder to generate cases which deterministicly fail using string keys.