Is there a way to search the key value in a hash table with separate chaining?

Question

I've been given a problem that involves a hash table with separate chaining. I know how to search the instance of the hash table for the key and return the item, but is it possible to search for the item and return the key?

For example,

Under where I loaded the csv file into the hash table, I have key = p_id and item = package

If I want to create a function that returns the p_id (key) if the p_notes in package contains a certain string, how would I implement it? I've tried multiple different ways, but I receive an error stating that the key isn't iterable.

class ChainingHashTable:  # Hashing Class with separate chaining

    def __init__(self, initial_capacity=40):

        self.table = []  # Initialize the hash table with empty bucket list entries
        for i in range(initial_capacity):
            self.table.append([])

    # Inserts a new item into the hash table, or updates an existing item

    def insert(self, key, item):  # Does both insert and update
        # Get the bucket list where this item will go
        bucket = hash(key) % len(self.table)
        bucket_list = self.table[bucket]

        # Update the key if it is already in the bucket list
        for kv in bucket_list:
            # print(key_value)
            if kv[0] == key:
                kv[1] = item
                return True

        key_value = [key, item]
        bucket_list.append(key_value)
        return True

    # Searches for an item with matching key in the hash table
    # Returns the item if found, or None if not found

    def search(self, key):
        # Get the bucket list where this key would be
        bucket = hash(key) % len(self.table)
        bucket_list = self.table[bucket]
        # print(bucket_list)

        # Search for the key in the bucket list
        for kv in bucket_list:
            # print(key_value)
            if kv[0] == key:
                return kv[1]  # Value
            return None

    # Removes an item with matching key from the hash table.
    def remove(self, key):
        # Get the bucket list where this item will be removed from
        bucket = hash(key) % len(self.table)
        bucket_list = self.table[bucket]

        # Remove the item from the bucket list if it is present
        for kv in bucket_list:
            # print(key_value)
            if kv[0] == key:
                bucket_list.remove([kv[0], kv[1]])


packageHash = ChainingHashTable()


class Package:

    def __init__(self, ID, Address, City, State, Zip, Deadline, Mass, Notes, Status):
        self.ID = ID
        self.Address = Address
        self.City = City
        self.State = State
        self.Zip = Zip
        self.Deadline = Deadline
        self.Mass = Mass
        self.Notes = Notes
        self.Status = Status

    # Overwrite print(Package), otherwise it will print the object's memory address
    def __str__(self):
        return "%s, %s, %s, %s, %s, %s, %s, %s, %s" % (
            self.ID, self.Address, self.City, self.State, self.Zip, self.Deadline, self.Mass, self.Notes, self.Status)


def load_package_file(fileName):
    with open(fileName) as packageFile:
        package_data = csv.reader(packageFile, delimiter=',')
        next(package_data)  # Skip the header row
        for row in package_data:
            p_id = int(row[0])
            p_address = (row[1])
            p_city = (row[2])
            p_state = (row[3])
            p_zip = (row[4])
            p_deadline = (row[5])
            p_mass = (row[6])
            p_notes = (row[7])
            p_status = (row[8])

            # packageHash.insert(p_id, package)
            package = Package(p_id, p_address, p_city, p_state, p_zip, p_deadline, p_mass, p_notes, p_status)

            packageHash.insert(p_id, package)

user_240443 · Answer

Hashtables have no way of looking up a value to find the key except by brute force. Iterate every key-value, and check if it fits your predicate. Something like this would fit your code so far:

def find_value(self, predicate):
    for bucket in self.table:
        for kv in bucket:
            if predicate(kv[1]):
                return kv[0]
    return None

You could use it as:

key = packageHash.findValue(lambda pkg: "foo" in pkg.Notes)

This is not very Pythonic though. It would be better to allow your class to iterate over key-value pairs, then just use the built-in function next, though this requires knowledge of generators:

def items(self):
    for bucket in self.table:
        yield from bucket

and then

key = next((key for key, pkg in packageHash.items() if "foo" in pkg.Notes), None)

Is there a way to search the key value in a hash table with separate chaining?

1 Answers