HashMap in Python

Question

This is a HashMap implementation written in Python. All the methods are based on the java implementation of a HashMap. Any and all critique is welcome.

This implementation is just a rewrite of some java HashMap methods. Yes, it's basically a wrapper class for pythons dict. This implementation is a simple exercise to see if I could write something from Java in Python.

from typing import Union, List

class HashMap:

    def __init__(self):
        self.capacity = 16
        self.map = {}

    def clear(self) -> None:
        """
        Clears all the entries into this hashmap

        :return: None
        """
        self.map = {}

    def contains_key(self, key: object) -> bool:
        """
        Returns if the map contains the passed key

        :param key -> object: Value to check residency in map keyset

        :return bool: True if "key" in map keyset, False otherwise
        """
        return key in self.map.keys()

    def contains_value(self, value: object) -> bool:
        """
        Returns if the map contains the passed value

        :param value -> object: Value to check residency in map valueset

        :return bool: True if "value" in map valueset, False otherwise
        """
        return value in self.map.values()

    def entry_set(self) -> set:
        """
        Returns a set of the hashmap

        :return set: A set representation of the map
        """
        return set(self.map)

    def get(self, key: object) -> Union[object, None]:
        """
        Returns the value at the passed key, None if not present

        :param key -> object: Key to retrieve value in map

        :return Union[object, None]: value at "key", None if key is not present in map
        """
        return self.map[key] if key in self.map.keys() else None

    def get_or_default(self, key: object, default_value: object) -> object:
        """
        Returns the value at the passed key, or default_value if not present

        :param key -> object: Key to retrieve value in map\n
        :param default_value -> object: Value to return if key is not present in map

        :return object: Value associated with "key", "default_value" otherwise 
        """
        return self.map[key] if key in self.map.keys() else default_value

    def is_empty(self) -> bool:
        """
        Returns if the map has no key-value entries

        :return bool: True if map isn't empty, False otherwise
        """
        return self.map != {}

    def key_set(self) -> set:
        """
        Returns a set of all the keys

        :return set: Set of all keys in map
        """
        return set(self.map.keys())

    def put(self, key: object, value: object) -> object:
        """
        Adds the key-value pair to the map, returning the value

        :param key -> object: Key to add to set\n
        :param value -> object: Value to add to set

        :return object: "value" passed
        """
        self.map[key] = value
        return value

    def remove(self, key: object) -> Union[object, None]:
        """
        Removes the mapping for the passed key, returning the value

        :param key -> object: Key to retrieve value from map

        :return object: Value associated with "key", None if key not in map keyset
        """
        if key in self.map.keys():
            value = self.map[key]
            del self.map[key]
            return value
        return None

    def size(self) -> int:
        """
        Returns the size of the hashmap

        :return int: Size of map
        """
        return len(self.map)

    def values(self) -> List[object]:
        """
        Returns a list of the values in the hashmap

        :return List[object]: List of values in map
        """
        return list(self.map.values())

Testing Implementation

if __name__ == "__main__":
    hashmap = HashMap()

    hashmap.put("Ben", 18)
    hashmap.put(5, 18)
    hashmap.put("5", True)
    hashmap.put(False, 3.661)

    print(hashmap.get(5))
    print(hashmap.get(False))
    print(hashmap.get("Ben"))
    print(hashmap.size())
    print(hashmap.values())

Answer 1

Refactoring the core interface:

Since presented HashMap class is just a custom wrapper around Python's dictionary - it should borrow all the advantages from that.

As the class provides a public interface for the internal data structure - that data structure needs to be protected (or private). Otherwise, the one can easily compromise it like shown below:

hashmap = HashMap()
hashmap.map = tuple()

So we change the constructor/initializer to the following:

def __init__(self):
    self.capacity = 16
    self._map = {}

Let get down to instance methods:

• clear method. It reassigns the internal map with self._map = {}.
  In ideal perspective using self._map.clear() would be preferable as it allows to beat potential copies of self._map (even if that's unlikely to happen)
• contains_key method.
  Returns key in self._map.keys() which is a verbose way of key in self._map

• entry_set method and key_set method lead to confusion as they return the same result:
  return set(self._map) is technically equal to return set(self._map.keys()).

  To fix that - let's perceive "entry" as a (key, value) pair.
  Therefore the definition of entry_set is changed to:

  def entry_set(self) -> set:
      """
      Returns a set of the hashmap
  
      :return set: A set representation of the map
      """
      return set(self._map.items())
  

• get method. The noisy expression self._map[key] if key in self._map.keys() else None should be eliminated in favor of flexible dict.get() method:

  self._map.get(key, None)
  

• get_or_default method has the same issue as get method, and the optimal way would be to just combine them into a single unified method:

  def get(self, key: object, default_value=None) -> object:
      """
      Returns the value at the passed key, or default_value if not present
  
      :param key -> object: Key to retrieve value in map\n
      :param default_value -> object: Value to return if key is not present in map
  
      :return object: Value associated with "key", "default_value" otherwise 
      """
      return self._map.get(key, default_value)
  

• is_empty method. The returned value self._map != {} is simply replaced with bool(self._map)

• key_set method. The returned value set(self._map.keys()) is simplified to set(self._map)

• remove method. The whole method body:

  if key in self._map.keys():
      value = self._map[key]
      del self._map[key]
      return value
  return None
  

  can be replaced with the convenient dict.pop method:

  return self._map.pop(key, None)
  

---

The final optimized implementation:

class HashMap:

    def __init__(self):
        self.capacity = 16
        self._map = {}

    def clear(self) -> None:
        """
        Clears all the entries into this hashmap

        :return: None
        """
        self._map.clear()

    def contains_key(self, key: object) -> bool:
        """
        Returns if the map contains the passed key

        :param key -> object: Value to check residency in map keyset

        :return bool: True if "key" in map keyset, False otherwise
        """
        return key in self._map

    def contains_value(self, value: object) -> bool:
        """
        Returns if the map contains the passed value

        :param value -> object: Value to check residency in map valueset

        :return bool: True if "value" in map valueset, False otherwise
        """
        return value in self._map.values()

    def entry_set(self) -> set:
        """
        Returns a set of the hashmap

        :return set: A set representation of the map
        """
        return set(self._map.items())

    def get(self, key: object, default_value=None) -> object:
        """
        Returns the value at the passed key, or default_value if not present

        :param key -> object: Key to retrieve value in map\n
        :param default_value -> object: Value to return if key is not present in map

        :return object: Value associated with "key", "default_value" otherwise 
        """
        return self._map.get(key, default_value)

    def is_empty(self) -> bool:
        """
        Returns if the map has no key-value entries

        :return bool: True if map isn't empty, False otherwise
        """
        return bool(self._map)

    def key_set(self) -> set:
        """
        Returns a set of all the keys

        :return set: Set of all keys in map
        """
        return set(self._map)

    def put(self, key: object, value: object) -> object:
        """
        Adds the key-value pair to the map, returning the value

        :param key -> object: Key to add to set\n
        :param value -> object: Value to add to set

        :return object: "value" passed
        """
        self._map[key] = value
        return value

    def remove(self, key: object) -> Union[object, None]:
        """
        Removes the mapping for the passed key, returning the value

        :param key -> object: Key to retrieve value from map

        :return object: Value associated with "key", None if key not in map keyset
        """

        return self._map.pop(key, None)

    def size(self) -> int:
        """
        Returns the size of the hashmap

        :return int: Size of map
        """
        return len(self._map)

    def values(self) -> List[object]:
        """
        Returns a list of the values in the hashmap

        :return List[object]: List of values in map
        """
        return list(self._map.values())

P.S. obviously, Python's dict itself is a good hashmap :-)

Answer 2

This is a small review focusing only on the type hints.

• In all methods, the type of key should be Hashable, not object. Unhashable objects (e.g. mutable collections like lists) cannot be used as keys in Python dictionaries, and the same goes for HashMap since it uses a Python dictionary behind the scenes.

• Instead of just using set as the return type, prefer using Set with the type of the elements it contains:

  def key_set(self) -> Set[Hashable]:
  

• Although they are equivalent, consider using Optional[T] instead of Union[T, None] as it is more readable:

  def get(self, key: Hashable) -> Optional[object]:
  

• __init__'s return type should be None. After correcting this, you'll also need to provide a type hint for self.map:

  def __init__(self) -> None:
      self.map: Dict[Hashable, object] = {}