HashMap implementation in Python

Question

Here's my implementation of a bare-bones HashMap in Python. Expected behavior, it returns None if a key is missing, When a key is inserted the second time it just overwrites the first value.

class HashMap:
    def __init__(self):
        self.store = [None for _ in range(16)]
        self.size = 0

    def get(self, key):
        key_hash = self._hash(key)
        index = self._position(key_hash)
        if not self.store[index]:
            return None
        else:
            list_at_index = self.store[index]
            for i in list_at_index:
                if i.key == key:
                    return i.value
            return None

    def put(self, key, value):
        p = Node(key, value)
        key_hash = self._hash(key)
        index = self._position(key_hash)
        if not self.store[index]:
            self.store[index] = [p]
            self.size += 1
        else:
            list_at_index = self.store[index]
            if p not in list_at_index:
                list_at_index.append(p)
                self.size += 1
            else:
                for i in list_at_index:
                    if i == p:
                        i.value = value
                        break

    def __len__(self):
        return self.size

    def _hash(self, key):
        if isinstance(key, int):
            return key
        result = 5381
        for char in key:
            result = 33 * result + ord(char)
        return result

    def _position(self, key_hash):
        return key_hash % 15


class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __eq__(self, other):
        return self.key == other.key


if __name__ == '__main__':
    hashmap = HashMap()
    hashmap.put(2, 12)
    hashmap.put('asd', 13)
    hashmap.put(2, 11)
    print(hashmap.get(2))
    print(hashmap.get('asd'))
    print(hashmap.get('ade'))

Invite comments and reviews.

Answer 1

• Initialization of store as a list of None does not really buy you anything in terms of efficiency, but complicates the code quite a bit. I recommend to initialize it with empty lists instead.

• put iterates the list twice. A single pass is sufficient:

      for i in list_at_index:
          if i == p:
              i.value = p.value
              return
      list_at_index.append(p)
      self.size += 1
  

• store has 16 slots, but key_hash % 15 returns only 15 possible values. The last slot is never used.

• Absence of delete is somewhat questionable.

Answer 2

You can also collapse the loop in the get() method using next() replacing:

for i in list_at_index:
    if i.key == key:
        return i.value
return None

with:

return next((i.value for i in self.store[index] if i.key == key), None)

As a side note, I think it would be a good idea to avoid hardcoding the numbers like 5381 or 15 in the code and make them proper constants or hashmap initialization parameters.

Answer 3

Instead of rolling your own hash function _hash you should use Python’s built-in hash().

Answer 4

You can define __getitem__ and __setitem__ instead of get and put to use square bracket notation (I don't think you would have to change the functions at all, just the names).