HashTable.py

class HashTable:
    # Initializes a HashTable using linear probing to minimize collisions.
    # Optional parameters allow setting the initial capacity and constants for double hashing.
    def __init__(self, initial_capacity=40, c1=0, c2=1):
        self.initial_capacity = initial_capacity
        self.package_table = [None] * initial_capacity
        self.bucket_status_table = ["EMPTY_SINCE_START"] * initial_capacity

        # Constants for double hashing
        self.c1 = c1
        self.c2 = c2

    # Adds a package to the HashTable. The package's id_number serves as the key.
    def insert(self, package):
        i = 0
        buckets_probed = 0
        N = len(self.package_table)
        bucket = hash(package.id_number) % N

        # Search for an empty slot to insert the package
        while buckets_probed < N:
            # Place package in an available bucket
            if self.bucket_status_table[bucket] in ["EMPTY_SINCE_START", "EMPTY_AFTER_REMOVAL"]:
                self.package_table[bucket] = package
                self.bucket_status_table[bucket] = "OCCUPIED"
                return True

            # No empty slot found, calculate the next bucket index
            i += 1
            bucket = (hash(package.id_number) + (self.c1 * i) + (self.c2 * i ** 2)) % N

            # Track the number of buckets checked
            buckets_probed += 1

        # If no slot is found, resize the table and retry insertion
        self.resize()
        self.insert(package)
        return True

    # Finds a package by its key. Returns the package if found, otherwise None.
    def lookup(self, key):
        i = 0
        buckets_probed = 0
        N = len(self.package_table)
        bucket = hash(key) % N

        while self.bucket_status_table[bucket] != "EMPTY_SINCE_START" and buckets_probed < N:
            if self.package_table[bucket] is not None and self.package_table[bucket].id_number == key:
                return self.package_table[bucket]

            # Calculate the next bucket index
            i += 1
            bucket = (hash(key) + self.c1 * i + self.c2 * i ** 2) % N

            # Track the number of buckets checked
            buckets_probed += 1

        return None

    # Expands the HashTable by doubling its current capacity.
    def resize(self):
        # Create a new HashTable with increased capacity
        resized_ht = HashTable(initial_capacity=self.initial_capacity * 2, c1=self.c1, c2=self.c2)

        # Transfer packages to the new, larger HashTable
        for package in self.package_table:
            if package is not None:
                resized_ht.insert(package)

        self.initial_capacity = resized_ht.initial_capacity
        self.package_table = resized_ht.package_table
        self.bucket_status_table = resized_ht.bucket_status_table

    # Provides a string representation of the HashTable for easy visualization.
    def __str__(self):
        s = "   --------\n"
        index = 0
        for item in self.package_table:
            value = str(item) if item is not None else 'E'
            s += '{:2}:|{:^6}|\n'.format(index, value)
            index += 1
        s += "   --------"
        return s