Class HashTable

algorithms/data_structures/hash_table.py:18–142

Hash table using open addressing with linear probing. Examples: >>> ht = HashTable(10) >>> ht.put(1, 'one') >>> ht.get(1) 'one'

class HashTable:
    """Hash table using open addressing with linear probing.

    Examples:
        >>> ht = HashTable(10)
        >>> ht.put(1, 'one')
        >>> ht.get(1)
        'one'
    """

    _empty = object()
    _deleted = object()

    def __init__(self, size: int = 11) -> None:
        """Initialize the hash table.

        Args:
            size: Number of slots in the underlying array.
        """
        self.size = size
        self._len = 0
        self._keys: list[object] = [self._empty] * size
        self._values: list[object] = [self._empty] * size

    def put(self, key: int, value: object) -> None:
        """Insert or update a key-value pair.

        Args:
            key: The key to insert.
            value: The value associated with the key.

        Raises:
            ValueError: If the table is full.
        """
        initial_hash = hash_ = self.hash(key)

        while True:
            if self._keys[hash_] is self._empty or self._keys[hash_] is self._deleted:
                self._keys[hash_] = key
                self._values[hash_] = value
                self._len += 1
                return
            elif self._keys[hash_] == key:
                self._keys[hash_] = key
                self._values[hash_] = value
                return

            hash_ = self._rehash(hash_)

            if initial_hash == hash_:
                raise ValueError("Table is full")

    def get(self, key: int) -> object | None:
        """Retrieve the value for a given key.

        Args:
            key: The key to look up.