hash map with open addressing https en wikipedia orgwikihashtable another hash map implementation with a good explanation modern dictionaries by raymond hettinger https www youtube comwatch vp33cvv29og8 hash map with open addressing get next index implements linear open addressing hashmap5 getnextind3 4 hashmap5 getnextind5 1 hashmap5 getnextind6 2 hashmap5 getnextind9 0 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 return true if we have reached safe capacity so we need to increase the number of buckets to avoid collisions hm hashmap2 hm additem1 10 hm additem2 20 hm isfull true hashmap2 isfull false return true if we need twice fewer buckets when we have now if lenself buckets self initialblocksize return false limit lenself buckets self capacityfactor 2 return lenself limit def resizeself newsize int none oldbuckets self buckets self buckets none newsize self len 0 for item in oldbuckets if item self additemitem key item val def sizeupself none self resizelenself buckets 2 def sizedownself none self resizelenself buckets 2 def iteratebucketsself key key iteratorint ind self getbucketindexkey for in rangelenself buckets yield ind ind self getnextindind def additemself key key val val none for ind in self iteratebucketskey if self trysetind key val break def setitemself key key val val none if self isfull self sizeup self additemkey val def delitemself key key none trying to remove a nonexisting item for ind in self iteratebucketskey item self bucketsind if item is none raise keyerrorkey if item is deleted continue if item key key self bucketsind deleted self len 1 break if self issparse self sizedown def getitemself key key val for ind in self iteratebucketskey item self bucketsind if item is none break if item is deleted continue if item key key return item val raise keyerrorkey def lenself int return self len def iterself iteratorkey yield from item key for item in self buckets if item def reprself str valstring join fitem key item val for item in self buckets if item return fhashmapvalstring if name main import doctest doctest testmod hash map with open addressing 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 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 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 return true if we need twice fewer buckets when we have now 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 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 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 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 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
from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

KEY = TypeVar("KEY")
VAL = TypeVar("VAL")


@dataclass(frozen=True, slots=True)
class _Item(Generic[KEY, VAL]):
    key: KEY
    val: VAL


class _DeletedItem(_Item):
    def __init__(self) -> None:
        super().__init__(None, None)

    def __bool__(self) -> bool:
        return False


_deleted = _DeletedItem()


class HashMap(MutableMapping[KEY, VAL]):
    

    def __init__(
        self, initial_block_size: int = 8, capacity_factor: float = 0.75
    ) -> None:
        self._initial_block_size = initial_block_size
        self._buckets: list[_Item | None] = [None] * initial_block_size
        assert 0.0 < capacity_factor < 1.0
        self._capacity_factor = capacity_factor
        self._len = 0

    def _get_bucket_index(self, key: KEY) -> int:
        return hash(key) % len(self._buckets)

    def _get_next_ind(self, ind: int) -> int:
        
        return (ind + 1) % len(self._buckets)

    def _try_set(self, ind: int, key: KEY, val: VAL) -> bool:
        
        stored = self._buckets[ind]
        if not stored:
            self._buckets[ind] = _Item(key, val)
            self._len += 1
            return True
        elif stored.key == key:
            self._buckets[ind] = _Item(key, val)
            return True
        else:
            return False

    def _is_full(self) -> bool:
        
        limit = len(self._buckets) * self._capacity_factor
        return len(self) >= int(limit)

    def _is_sparse(self) -> bool:
        
        if len(self._buckets) <= self._initial_block_size:
            return False
        limit = len(self._buckets) * self._capacity_factor / 2
        return len(self) < limit

    def _resize(self, new_size: int) -> None:
        old_buckets = self._buckets
        self._buckets = [None] * new_size
        self._len = 0
        for item in old_buckets:
            if item:
                self._add_item(item.key, item.val)

    def _size_up(self) -> None:
        self._resize(len(self._buckets) * 2)

    def _size_down(self) -> None:
        self._resize(len(self._buckets) // 2)

    def _iterate_buckets(self, key: KEY) -> Iterator[int]:
        ind = self._get_bucket_index(key)
        for _ in range(len(self._buckets)):
            yield ind
            ind = self._get_next_ind(ind)

    def _add_item(self, key: KEY, val: VAL) -> None:
        
        for ind in self._iterate_buckets(key):
            if self._try_set(ind, key, val):
                break

    def __setitem__(self, key: KEY, val: VAL) -> None:
        
        if self._is_full():
            self._size_up()

        self._add_item(key, val)

    def __delitem__(self, key: KEY) -> None:
        
        for ind in self._iterate_buckets(key):
            item = self._buckets[ind]
            if item is None:
                raise KeyError(key)
            if item is _deleted:
                continue
            if item.key == key:
                self._buckets[ind] = _deleted
                self._len -= 1
                break
        if self._is_sparse():
            self._size_down()

    def __getitem__(self, key: KEY) -> VAL:
        
        for ind in self._iterate_buckets(key):
            item = self._buckets[ind]
            if item is None:
                break
            if item is _deleted:
                continue
            if item.key == key:
                return item.val
        raise KeyError(key)

    def __len__(self) -> int:
        
        return self._len

    def __iter__(self) -> Iterator[KEY]:
        yield from (item.key for item in self._buckets if item)

    def __repr__(self) -> str:
        val_string = ", ".join(
            f"{item.key}: {item.val}" for item in self._buckets if item
        )
        return f"HashMap({val_string})"


if __name__ == "__main__":
    import doctest

    doctest.testmod()