hash_map_oa.py

# Name: Aaron Ruse
# OSU Email: rusea@oregonstate.edu
# Course: CS261 - Data Structures
# Assignment: 06
# Due Date: 06-06-2024
# Description: Implement an optimized HashMap class that uses Open Addressing
# with Quadratic Probing for collision
# resolution inside the dynamic array.

from a6_include import (DynamicArray, DynamicArrayException, HashEntry,
                        hash_function_1, hash_function_2)


class HashMap:
    def __init__(self, capacity: int, function) -> None:
        """
        Initialize new HashMap that uses
        quadratic probing for collision resolution
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        self._buckets = DynamicArray()

        # capacity must be a prime number
        self._capacity = self._next_prime(capacity)
        for _ in range(self._capacity):
            self._buckets.append(None)

        self._hash_function = function
        self._size = 0

    def __str__(self) -> str:
        """
        Override string method to provide more readable output
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        out = ''
        for i in range(self._buckets.length()):
            out += str(i) + ': ' + str(self._buckets[i]) + '\n'
        return out

    def _next_prime(self, capacity: int) -> int:
        """
        Increment from given number to find the closest prime number
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        if capacity % 2 == 0:
            capacity += 1

        while not self._is_prime(capacity):
            capacity += 2

        return capacity

    @staticmethod
    def _is_prime(capacity: int) -> bool:
        """
        Determine if given integer is a prime number and return boolean
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        if capacity == 2 or capacity == 3:
            return True

        if capacity == 1 or capacity % 2 == 0:
            return False

        factor = 3
        while factor ** 2 <= capacity:
            if capacity % factor == 0:
                return False
            factor += 2

        return True

    def get_size(self) -> int:
        """
        Return size of map
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        return self._size

    def get_capacity(self) -> int:
        """
        Return capacity of map
        DO NOT CHANGE THIS METHOD IN ANY WAY
        """
        return self._capacity

    # ------------------------------------------------------------------ #

    def put(self, key: str, value: object) -> None:
        """
        Updates the key/value pair in the hash map. If the given key already
        exists in the hash map, its associated value must be replaced with the
        new value. If the given key is not in the hash map, a new key/value
        pair must be added.

        param key: A string used as the hashmap key.
        param value: The object associated with the key.
        """
        # Double the table size if the load value increases to 0.5 or above.
        if self.table_load() >= 0.5:
            self.resize_table(self._capacity * 2)

        # Create an index value using the hash function.
        index = self._hash_function(key) % self._capacity

        did_insert = False
        probe_count = 0
        probe_index = (index + probe_count ** 2) % self._capacity
        # Probe until an empty index is found or the probe_index values start
        # to repeat, which means no available index will be found and the
        # table size needs to be increased.
        while probe_count < self._capacity:
            # A key, value pair exists for this index.
            if self._buckets[probe_index] is not None:
                # The key is already in the hash map, so replace the value
                # associated with the key.
                if self._buckets[probe_index].key == key and not self._buckets[probe_index].is_tombstone:
                    self._buckets[probe_index] = HashEntry(key, value)
                    did_insert = True
                    break
                # The index contains a tombstone value, indicating it is
                # available to add the key, value pair.
                elif self._buckets[probe_index].is_tombstone:
                    self._buckets[probe_index] = HashEntry(key, value)
                    did_insert = True
                    self._size += 1
                    break
            # Found an empty index to insert the key, value pair.
            else:
                self._buckets[probe_index] = HashEntry(key, value)
                did_insert = True
                self._size += 1
                break
            # Calculate new index value if the first probe failed to find an
            # available index to insert the key, value pair.
            probe_count += 1
            probe_index = (index + probe_count ** 2) % self._capacity

        # The key, value pair was not inserted into the array, so double the
        # table size and attempt the insertion again
        if not did_insert:
            self.resize_table(self._capacity * 2)
            self.put(key, value)

    def resize_table(self, new_capacity: int) -> None:
        """
        Changes the capacity of the underlying table. If new_capacity < 1,
        this method does nothing. If new_capacity is not a prime number, the
        capacity will be updated to the next higher prime number

        param new_capacity: The int value used to update the capacity.
        """
        # Do not resize the hash table to a size lower than the number of
        # elements already in the table
        if new_capacity < self._size:
            return
        # Resize to the next larger prime size if original resize value is not
        # a prime value
        elif self._is_prime(new_capacity) is False:
            new_capacity = self._next_prime(new_capacity)

        # Fill a new array with the key, value pairs from the hash table. This
        # array will be parsed when rehashing the
        # indexes for new, larger table.
        new_array = DynamicArray()
        for index in range(self._capacity):
            if self._buckets[index] is not None:
                new_array.append(self._buckets[index])

        # Parse the array, rehash the index values and fill the larger hash
        # table with values from the array.
        self._capacity = new_capacity
        self.clear()
        for index in range(new_array.length()):
            index_key = new_array.get_at_index(index).key
            index_value = new_array.get_at_index(index).value
            self.put(index_key, index_value)

    def table_load(self) -> float:
        """
        Returns the current hash table load factor.

        return a float value the represents the load factor.
        """
        num_buckets = self._buckets.length()
        num_elements = self.get_size()
        return num_elements / num_buckets

    def empty_buckets(self) -> int:
        """
        Returns the number of empty buckets in the hash table.

        returns an int that represents the number of empty buckets.
        """
        empty_sum = 0
        # Parse the hash table and increase the empty_sum count when an empty
        # index is found.
        for index in range(self._capacity):
            if self._buckets[index] is None:
                empty_sum += 1
        return empty_sum

    def get(self, key: str) -> object:
        """
        Returns the value associated with the given key. If the key is not in
        the hash map, the method returns None.

        param key: A string used as the hashmap key.

        return the object associated with the key.
        """
        # Create an index value using the hash function.
        index = self._hash_function(key) % self._capacity

        probe_count = 0
        probe_index = (index + probe_count ** 2) % self._capacity
        # Probe until the key is found or the probe_index values start to
        # repeat, which means the key is not in the table.
        while probe_count < self._capacity:
            if self._buckets[probe_index] is not None:
                # The tombstone value is found, indicating the key is not in
                # the table.
                if self._buckets[probe_index].is_tombstone:
                    return None
                # The key is found in the table and the value is returned.
                elif self._buckets[probe_index].key == key:
                    return self._buckets[probe_index].value
            # Calculate new index value if the first probe failed to find an
            # available index to insert the key, value pair.
            probe_count += 1
            probe_index = (index + probe_count ** 2) % self._capacity

    def contains_key(self, key: str) -> bool:
        """
        Returns True if the given key is in the hash map, otherwise it returns
        False.

        param key: A string used as the hashmap key.

        return a boolean value indicating if the key value pair is in the hash
        map
        """
        # The table is empty so the key is not found.
        if self._size == 0:
            return False
        else:
            # Create an index value using the hash function.
            index = self._hash_function(key) % self._capacity

            probe_count = 0
            probe_index = (index + probe_count ** 2) % self._capacity
            # Probe until the key is found or the probe_index values start to
            # repeat, which means the key is not in the table.
            while probe_count < self._capacity:
                if self._buckets[probe_index] is not None:
                    # The tombstone value is found, indicating the key is not
                    # in the table.
                    if self._buckets[probe_index].is_tombstone:
                        return False
                    # The key is found in the table.
                    elif self._buckets[probe_index].key == key:
                        return True
                # Calculate new index value if the first probe failed to find
                # an available index to insert the key, value pair.
                probe_count += 1
                probe_index = (index + probe_count ** 2) % self._capacity
            # The probe search failed to find the key, so it is not in the
            # table.
            return False

    def remove(self, key: str) -> None:
        """
         Removes the given key and its associated value from the hash map. If
         the key is not in the hash map, the method does nothing.

        param key: A string used as the hashmap key.
        """
        # Create an index value using the hash function.
        index = self._hash_function(key) % self._capacity

        probe_count = 0
        probe_index = (index + probe_count ** 2) % self._capacity
        # Probe until the key is found or the probe_index values start to
        # repeat, which means the key is not in the table.
        while probe_count < self._capacity:
            if self._buckets[probe_index] is not None:
                if self._buckets[probe_index].key == key:
                    # The key is in the hash map
                    if not self._buckets[probe_index].is_tombstone:
                        self._buckets[probe_index].is_tombstone = True
                        self._size -= 1
                        return
            # Calculate new index value if the first probe failed to find an
            # available index to insert the key, value pair.
            probe_count += 1
            probe_index = (index + probe_count ** 2) % self._capacity

    def get_keys_and_values(self) -> DynamicArray:
        """
        Returns a dynamic array where each index contains a tuple of a
        key/value pair stored in the hash map.

        return a DynamicArray containing all the key/value pairs.
        """
        new_array = DynamicArray()
        # Fill a new array with the key, value pairs from the hash table.
        for index in range(self._capacity):
            if self._buckets[index] is not None:
                if self._buckets[index].is_tombstone is False:
                    new_array.append((self._buckets[index].key,
                                      self._buckets[index].value))
        return new_array

    def clear(self) -> None:
        """
        Clears the contents of the hash map. It does not change the underlying
        hash table capacity.
        """
        # Set the hash table array to a new empty array.
        self._buckets = DynamicArray()
        for _ in range(self._capacity):
            self._buckets.append(None)
        self._size = 0

    def __iter__(self):
        """
        Enables the hash map to iterate across itself.
        """
        self._index = 0
        return self

    def __next__(self):
        """
        Return the next item in the hash map, based on the current location of
        the iterator.
        """
        try:
            value = self._buckets[self._index]
            # Skip over empty indices in the array
            while value is None or value.is_tombstone:
                self._index += 1
                value = self._buckets[self._index]
        except DynamicArrayException:
            raise StopIteration
        self._index += 1
        return value


# ------------------- BASIC TESTING ---------------------------------------- #

if __name__ == "__main__":
    print("\nPDF - put example 1")
    print("-------------------")
    m = HashMap(53, hash_function_1)
    for i in range(150):
        m.put('str' + str(i), i * 100)
        if i % 25 == 24:
            print(m.empty_buckets(), round(m.table_load(), 2), m.get_size(),
                  m.get_capacity())

    print("\nPDF - put example 2")
    print("-------------------")
    m = HashMap(41, hash_function_2)
    for i in range(50):
        m.put('str' + str(i // 3), i * 100)
        if i % 10 == 9:
            print(m.empty_buckets(), round(m.table_load(), 2), m.get_size(),
                  m.get_capacity())

    print("\nPDF - resize example 1")
    print("----------------------")
    m = HashMap(20, hash_function_1)
    m.put('key1', 10)
    print(m.get_size(), m.get_capacity(), m.get('key1'),
          m.contains_key('key1'))
    m.resize_table(30)
    print(m.get_size(), m.get_capacity(), m.get('key1'),
          m.contains_key('key1'))

    print("\nPDF - resize example 2")
    print("----------------------")
    m = HashMap(75, hash_function_2)
    keys = [i for i in range(25, 1000, 13)]
    for key in keys:
        m.put(str(key), key * 42)
    print(m.get_size(), m.get_capacity())

    for capacity in range(111, 1000, 117):
        m.resize_table(capacity)

        if m.table_load() > 0.5:
            print(f"Check that the load factor is acceptable after the call to"
                  " resize_table().\n"
                  f"Your load factor is {round(m.table_load(), 2)} and should "
                  "be less than or equal to 0.5")

        m.put('some key', 'some value')
        result = m.contains_key('some key')
        m.remove('some key')

        for key in keys:
            # all inserted keys must be present
            result &= m.contains_key(str(key))
            # NOT inserted keys must be absent
            result &= not m.contains_key(str(key + 1))
        print(capacity, result, m.get_size(), m.get_capacity(),
              round(m.table_load(), 2))

    print("\nPDF - table_load example 1")
    print("--------------------------")
    m = HashMap(101, hash_function_1)
    print(round(m.table_load(), 2))
    m.put('key1', 10)
    print(round(m.table_load(), 2))
    m.put('key2', 20)
    print(round(m.table_load(), 2))
    m.put('key1', 30)
    print(round(m.table_load(), 2))

    print("\nPDF - table_load example 2")
    print("--------------------------")
    m = HashMap(53, hash_function_1)
    for i in range(50):
        m.put('key' + str(i), i * 100)
        if i % 10 == 0:
            print(round(m.table_load(), 2), m.get_size(), m.get_capacity())

    print("\nPDF - empty_buckets example 1")
    print("-----------------------------")
    m = HashMap(101, hash_function_1)
    print(m.empty_buckets(), m.get_size(), m.get_capacity())
    m.put('key1', 10)
    print(m.empty_buckets(), m.get_size(), m.get_capacity())
    m.put('key2', 20)
    print(m.empty_buckets(), m.get_size(), m.get_capacity())
    m.put('key1', 30)
    print(m.empty_buckets(), m.get_size(), m.get_capacity())
    m.put('key4', 40)
    print(m.empty_buckets(), m.get_size(), m.get_capacity())

    print("\nPDF - empty_buckets example 2")
    print("-----------------------------")
    m = HashMap(53, hash_function_1)
    for i in range(150):
        m.put('key' + str(i), i * 100)
        if i % 30 == 0:
            print(m.empty_buckets(), m.get_size(), m.get_capacity())

    print("\nPDF - get example 1")
    print("-------------------")
    m = HashMap(31, hash_function_1)
    print(m.get('key'))
    m.put('key1', 10)
    print(m.get('key1'))

    print("\nPDF - get example 2")
    print("-------------------")
    m = HashMap(151, hash_function_2)
    for i in range(200, 300, 7):
        m.put(str(i), i * 10)
    print(m.get_size(), m.get_capacity())
    for i in range(200, 300, 21):
        print(i, m.get(str(i)), m.get(str(i)) == i * 10)
        print(i + 1, m.get(str(i + 1)), m.get(str(i + 1)) == (i + 1) * 10)

    print("\nPDF - contains_key example 1")
    print("----------------------------")
    m = HashMap(11, hash_function_1)
    print(m.contains_key('key1'))
    m.put('key1', 10)
    m.put('key2', 20)
    m.put('key3', 30)
    print(m.contains_key('key1'))
    print(m.contains_key('key4'))
    print(m.contains_key('key2'))
    print(m.contains_key('key3'))
    m.remove('key3')
    print(m.contains_key('key3'))

    print("\nPDF - contains_key example 2")
    print("----------------------------")
    m = HashMap(79, hash_function_2)
    keys = [i for i in range(1, 1000, 20)]
    for key in keys:
        m.put(str(key), key * 42)
    print(m.get_size(), m.get_capacity())
    result = True
    for key in keys:
        # all inserted keys must be present
        result &= m.contains_key(str(key))
        # NOT inserted keys must be absent
        result &= not m.contains_key(str(key + 1))
    print(result)

    print("\nPDF - remove example 1")
    print("----------------------")
    m = HashMap(53, hash_function_1)
    print(m.get('key1'))
    m.put('key1', 10)
    print(m.get('key1'))
    m.remove('key1')
    print(m.get('key1'))
    m.remove('key4')

    print("\nPDF - get_keys_and_values example 1")
    print("------------------------")
    m = HashMap(11, hash_function_2)
    for i in range(1, 6):
        m.put(str(i), str(i * 10))
    print(m.get_keys_and_values())

    m.resize_table(2)
    print(m.get_keys_and_values())

    m.put('20', '200')
    m.remove('1')
    m.resize_table(12)
    print(m.get_keys_and_values())

    print("\nPDF - clear example 1")
    print("---------------------")
    m = HashMap(101, hash_function_1)
    print(m.get_size(), m.get_capacity())
    m.put('key1', 10)
    m.put('key2', 20)
    m.put('key1', 30)
    print(m.get_size(), m.get_capacity())
    m.clear()
    print(m.get_size(), m.get_capacity())

    print("\nPDF - clear example 2")
    print("---------------------")
    m = HashMap(53, hash_function_1)
    print(m.get_size(), m.get_capacity())
    m.put('key1', 10)
    print(m.get_size(), m.get_capacity())
    m.put('key2', 20)
    print(m.get_size(), m.get_capacity())
    m.resize_table(100)
    print(m.get_size(), m.get_capacity())
    m.clear()
    print(m.get_size(), m.get_capacity())

    print("\nPDF - __iter__(), __next__() example 1")
    print("---------------------")
    m = HashMap(10, hash_function_1)
    for i in range(5):
        m.put(str(i), str(i * 10))
    # print(m)
    for item in m:
        print('K:', item.key, 'V:', item.value)

    print("\nPDF - __iter__(), __next__() example 2")
    print("---------------------")
    m = HashMap(10, hash_function_2)
    for i in range(5):
        m.put(str(i), str(i * 24))
    m.remove('0')
    m.remove('4')
    print(m)
    for item in m:
        print('K:', item.key, 'V:', item.value)