DEV Community

CodeWithML
CodeWithML

Posted on • Originally published at codewithml.netlify.app

Implement a Hashmap with its various methods

#challenge #python #computerscience

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

Difficulty level: Easy

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
    • Else, add 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 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()

Github repo

Happy Coding !! 🌟

Top comments (0)