This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Design a hash map¶

Constraints and assumptions¶

• For simplicity, are the keys integers only?
  • Yes
• For collision resolution, can we use chaining?
  • Yes
• Do we have to worry about load factors?
  • No
• Can we assume inputs are valid or do we have to validate them?
  • Assume they're valid
• Can we assume this fits memory?
  • Yes

Solution¶

In [1]:

%%writefile hash_map.py
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 _hash_function(self, key):
        return key % self.size

    def set(self, key, value):
        hash_index = self._hash_function(key)
        for item in self.table[hash_index]:
            if item.key == key:
                item.value = value
                return
        self.table[hash_index].append(Item(key, value))

    def get(self, key):
        hash_index = self._hash_function(key)
        for item in self.table[hash_index]:
            if item.key == key:
                return item.value
        raise KeyError('Key not found')

    def remove(self, key):
        hash_index = self._hash_function(key)
        for index, item in enumerate(self.table[hash_index]):
            if item.key == key:
                del self.table[hash_index][index]
                return
        raise KeyError('Key not found')

%%writefile hash_map.py 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 _hash_function(self, key): return key % self.size def set(self, key, value): hash_index = self._hash_function(key) for item in self.table[hash_index]: if item.key == key: item.value = value return self.table[hash_index].append(Item(key, value)) def get(self, key): hash_index = self._hash_function(key) for item in self.table[hash_index]: if item.key == key: return item.value raise KeyError('Key not found') def remove(self, key): hash_index = self._hash_function(key) for index, item in enumerate(self.table[hash_index]): if item.key == key: del self.table[hash_index][index] return raise KeyError('Key not found')

Overwriting hash_map.py