## DEV Community is a community of 697,080 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Implement a Hashmap with its various methods

CodeWithML
Sharing solutions to coding problems.
Originally published at codewithml.netlify.app ・2 min read

### Problem Statement: Implement Hash Map with get, set and remove methods.

#### Test Cases

1. Get
• Get - key exists --> value
• Get - key doesn't exist --> Keyerror
2. Set
• Set - key exists --> Overwrite value
• Set - key doesn't exist --> new key, value
3. Remove
• Remove - key exists --> delete key, value
• Remove - key doesn't exist --> Keyerror

### Algorithm

1. Hash Function

• Return key modulo(%) table size
2. Get Function

• Get hashIndex for lookup
• If key exists, return the value
• Else, keyerror
3. Set Function

• Get hashIndex for lookup
• If key exists, overwrite the value
4. Remove Function

• Get hashIndex for lookup
• If key exists, delete the entry from the table
• Else, keyerror

### Time and Space Complexity

1. Hash Function
• Time complexity: O(1)
• Space complexity: O(1)
2. Get Function
• Time complexity: O(1) average and best case, O(n) worst case
• Space complexity: O(1)
3. Set Function
• Time complexity: O(1) average and best case, O(n) worst case
• Space complexity: O(1)
4. 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

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
``````

### 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()
``````

Github repo