Problem Statement: Implement Hash Map with get, set and remove methods.
Difficulty level: Easy
Test Cases
- Get
- Get - key exists --> value
- Get - key doesn't exist --> Keyerror
- Set
- Set - key exists --> Overwrite value
- Set - key doesn't exist --> new key, value
- Remove
- Remove - key exists --> delete key, value
- Remove - key doesn't exist --> Keyerror
Algorithm
-
Hash Function
- Return key modulo(%) table size
-
Get Function
- Get hashIndex for lookup
- If key exists, return the value
- Else, keyerror
-
Set Function
- Get hashIndex for lookup
- If key exists, overwrite the value
- Else, add value
-
Remove Function
- Get hashIndex for lookup
- If key exists, delete the entry from the table
- Else, keyerror
Time and Space Complexity
- Hash Function
- Time complexity: O(1)
- Space complexity: O(1)
- Get Function
- Time complexity: O(1) average and best case, O(n) worst case
- Space complexity: O(1)
- Set Function
- Time complexity: O(1) average and best case, O(n) worst case
- Space complexity: O(1)
- Remove Function
- Time complexity: O(1) average and best case, O(n) worst case
- Space complexity: O(1)
Code
class Item(object):
def __init__(self, key, value):
self.key = key
self.value = value
class HashTable(object):
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(self.size)]
def hashFunction(self, key):
return key % self.size
def set(self, key, value):
hashIndex = self.hashFunction(key)
for item in self.table[hashIndex]:
if item.key == key:
item.value = value
return
self.table[hashIndex].append(Item(key, value))
def get(self, key):
hashIndex = self.hashFunction(key)
for item in self.table[hashIndex]:
if item.key == key:
return item.value
raise KeyError('Key not found')
def remove(self, key):
hashIndex = self.hashFunction(key)
for index, item in enumerate(self.table[hashIndex]):
if item.key == key:
del self.table[hashIndex][index]
return
raise KeyError('Key not found')
Unit Test
import unittest
from hashmap import HashTable
class TestHashMap(unittest.TestCase):
def test_end_to_end(self):
hash_table = HashTable(10)
print("Test: get on an empty hash table index")
self.assertRaises(KeyError, hash_table.get, 0)
print("Test: set on an empty hash table index")
hash_table.set(0, 'first')
self.assertEqual(hash_table.get(0), 'first')
hash_table.set(1, 'second')
self.assertEqual(hash_table.get(1), 'second')
print("Test: set on a non empty hash table index")
hash_table.set(10, 'third')
self.assertEqual(hash_table.get(0), 'first')
self.assertEqual(hash_table.get(10), 'third')
print("Test: set on a key that already exists")
hash_table.set(10, 'fourth')
self.assertEqual(hash_table.get(0), 'first')
self.assertEqual(hash_table.get(10), 'fourth')
print("Test: remove on a key that already exists")
hash_table.remove(10)
self.assertEqual(hash_table.get(0), 'first')
self.assertRaises(KeyError, hash_table.get, 10)
print("Test: remove on a key that doesn't exist")
self.assertRaises(KeyError, hash_table.remove, -1)
print('Success: test_end_to_end')
def main():
test = TestHashMap()
test.test_end_to_end()
if __name__ == "__main__":
main()
Top comments (0)