data_structures.hashing.hash_map
================================

.. py:module:: data_structures.hashing.hash_map

.. autoapi-nested-parse::

   Hash map with open addressing.

   https://en.wikipedia.org/wiki/Hash_table

   Another hash map implementation, with a good explanation.
   Modern Dictionaries by Raymond Hettinger
   https://www.youtube.com/watch?v=p33CVV29OG8



Attributes
----------

.. autoapisummary::

   data_structures.hashing.hash_map.KEY
   data_structures.hashing.hash_map.VAL
   data_structures.hashing.hash_map._deleted


Classes
-------

.. autoapisummary::

   data_structures.hashing.hash_map.HashMap
   data_structures.hashing.hash_map._DeletedItem
   data_structures.hashing.hash_map._Item


Module Contents
---------------

.. py:class:: HashMap(initial_block_size: int = 8, capacity_factor: float = 0.75)

   Bases: :py:obj:`collections.abc.MutableMapping`\ [\ :py:obj:`KEY`\ , :py:obj:`VAL`\ ]


   Hash map with open addressing.


   .. py:method:: __delitem__(key: KEY) -> None

      >>> hm = HashMap(5)
      >>> hm._add_item(1, 10)
      >>> hm._add_item(2, 20)
      >>> hm._add_item(3, 30)
      >>> hm.__delitem__(3)
      >>> hm
      HashMap(1: 10, 2: 20)
      >>> hm = HashMap(5)
      >>> hm._add_item(-5, 10)
      >>> hm._add_item(6, 30)
      >>> hm._add_item(-7, 20)
      >>> hm.__delitem__(-5)
      >>> hm
      HashMap(6: 30, -7: 20)

      # Trying to remove a non-existing item
      >>> hm = HashMap(5)
      >>> hm._add_item(1, 10)
      >>> hm._add_item(2, 20)
      >>> hm._add_item(3, 30)
      >>> hm.__delitem__(4)
      Traceback (most recent call last):
      ...
      KeyError: 4



   .. py:method:: __getitem__(key: KEY) -> VAL

      Returns the item at the given key

      >>> hm = HashMap(5)
      >>> hm._add_item(1, 10)
      >>> hm.__getitem__(1)
      10

      >>> hm = HashMap(5)
      >>> hm._add_item(10, -10)
      >>> hm._add_item(20, -20)
      >>> hm.__getitem__(20)
      -20

      >>> hm = HashMap(5)
      >>> hm._add_item(-1, 10)
      >>> hm.__getitem__(-1)
      10



   .. py:method:: __iter__() -> collections.abc.Iterator[KEY]


   .. py:method:: __len__() -> int

      Returns the number of items present in hashmap

      >>> hm = HashMap(5)
      >>> hm._add_item(1, 10)
      >>> hm._add_item(2, 20)
      >>> hm._add_item(3, 30)
      >>> hm.__len__()
      3

      >>> hm = HashMap(5)
      >>> hm.__len__()
      0



   .. py:method:: __repr__() -> str


   .. py:method:: __setitem__(key: KEY, val: VAL) -> None

      1. Changing value of item whose key is present
      >>> hm = HashMap(5)
      >>> hm._add_item(1, 10)
      >>> hm.__setitem__(1, 20)
      >>> hm
      HashMap(1: 20)

      2. Changing value of item whose key is not present
      >>> hm = HashMap(5)
      >>> hm._add_item(1, 10)
      >>> hm.__setitem__(0, 20)
      >>> hm
      HashMap(0: 20, 1: 10)

      3. Changing the value of the same item multiple times
      >>> hm = HashMap(5)
      >>> hm._add_item(1, 10)
      >>> hm.__setitem__(1, 20)
      >>> hm.__setitem__(1, 30)
      >>> hm
      HashMap(1: 30)



   .. py:method:: _add_item(key: KEY, val: VAL) -> None

      Try to add 3 elements when the size is 5
      >>> hm = HashMap(5)
      >>> hm._add_item(1, 10)
      >>> hm._add_item(2, 20)
      >>> hm._add_item(3, 30)
      >>> hm
      HashMap(1: 10, 2: 20, 3: 30)

      Try to add 3 elements when the size is 5
      >>> hm = HashMap(5)
      >>> hm._add_item(-5, 10)
      >>> hm._add_item(6, 30)
      >>> hm._add_item(-7, 20)
      >>> hm
      HashMap(-5: 10, 6: 30, -7: 20)

      Try to add 3 elements when size is 1
      >>> hm = HashMap(1)
      >>> hm._add_item(10, 13.2)
      >>> hm._add_item(6, 5.26)
      >>> hm._add_item(7, 5.155)
      >>> hm
      HashMap(10: 13.2)

      Trying to add an element with a key that is a floating point value
      >>> hm = HashMap(5)
      >>> hm._add_item(1.5, 10)
      >>> hm
      HashMap(1.5: 10)

      5. Trying to add an item with the same key
      >>> hm = HashMap(5)
      >>> hm._add_item(1, 10)
      >>> hm._add_item(1, 20)
      >>> hm
      HashMap(1: 20)



   .. py:method:: _get_bucket_index(key: KEY) -> int


   .. py:method:: _get_next_ind(ind: int) -> int

      Get next index.

      Implements linear open addressing.
      >>> HashMap(5)._get_next_ind(3)
      4
      >>> HashMap(5)._get_next_ind(5)
      1
      >>> HashMap(5)._get_next_ind(6)
      2
      >>> HashMap(5)._get_next_ind(9)
      0



   .. py:method:: _is_full() -> bool

      Return true if we have reached safe capacity.

      So we need to increase the number of buckets to avoid collisions.

      >>> hm = HashMap(2)
      >>> hm._add_item(1, 10)
      >>> hm._add_item(2, 20)
      >>> hm._is_full()
      True
      >>> HashMap(2)._is_full()
      False



   .. py:method:: _is_sparse() -> bool

      Return true if we need twice fewer buckets when we have now.



   .. py:method:: _iterate_buckets(key: KEY) -> collections.abc.Iterator[int]


   .. py:method:: _resize(new_size: int) -> None


   .. py:method:: _size_down() -> None


   .. py:method:: _size_up() -> None


   .. py:method:: _try_set(ind: int, key: KEY, val: VAL) -> bool

      Try to add value to the bucket.

      If bucket is empty or key is the same, does insert and return True.

      If bucket has another key or deleted placeholder,
      that means that we need to check next bucket.



   .. py:attribute:: _buckets
      :type:  list[_Item | None]
      :value: [None, None, None, None, None, None, None, None]



   .. py:attribute:: _capacity_factor
      :value: 0.75



   .. py:attribute:: _initial_block_size
      :value: 8



   .. py:attribute:: _len
      :value: 0



.. py:class:: _DeletedItem

   Bases: :py:obj:`_Item`


   .. py:method:: __bool__() -> bool


.. py:class:: _Item

   Bases: :py:obj:`Generic`\ [\ :py:obj:`KEY`\ , :py:obj:`VAL`\ ]


   .. py:attribute:: key
      :type:  KEY


   .. py:attribute:: val
      :type:  VAL


.. py:data:: KEY

.. py:data:: VAL

.. py:data:: _deleted