hashmap.py

from typing import Hashable, Iterable


class KeyValuePair:
    '''
    A single key/value pair in a hashmap
    '''
    def __init__(self, key: Hashable, value):
        self.key = key
        self.value = value

class HashMap:
    '''
    Create a hashmap of key value pairs
    '''
    def __init__(self,
                 map_size: int,
                 keys: Iterable[Hashable],
                 values: Iterable):
        self.keys = keys
        self.values = values
        self.map = [None] * map_size # initialize empty map

        for key, value in zip(keys, values): # iterate through the items and values
            self[key] = value # add the value using add function

    def __setitem__(self, key: Hashable, value):
        key_hash = hash(key) # obtain hash of new item
        value_idx = key_hash % len(self.map) # make sure hash is within map
        original_idx = value_idx # starting point, to stop infinite loops

        while self.map[value_idx] is not None: # until empty space found in map
            # break the provided key exists (should redefine existing value)
            if self.map[value_idx].key == key:
                break

            value_idx += 1 # if not None, check next value

            value_idx %= len(self.map) # prevent index from exceeding map bounds

            assert value_idx != original_idx # stop looping if the map is full

        self.map[value_idx] = KeyValuePair(key, value)

    def __getitem__(self, key: Hashable):
        key_hash = hash(key) # obtain hash of new item
        value_idx = key_hash % len(self.map) # make sure hash is within map
        original_idx = value_idx # starting point, to stop infinite loops

        while self.map[value_idx].key != key: # until matching key is found
            value_idx += 1 # if not matching, check next value

            value_idx %= len(self.map) # prevent index from exceeding map bounds

            assert value_idx != original_idx # stop if full loop completed

        return self.map[value_idx].value