Hash Table

mail@pastecode.io avatar
unknown
python
7 months ago
4.5 kB
0
Indexable
Never
class Movie:
    def __init__(self, quote, title, year):
        self.quote = quote
        self.title = title
        self.year = year

class Node:
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.next = None

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        self.count = 0

    def hash_function(self, key):
        if len(key.split()) > 2:
            return hash(" ".join(key.split()[:2])) % self.size
        else:
            return hash(key) % self.size

    def add(self, key, data):
        index = self.hash_function(key)
        new_node = Node(key, data)

        if self.table[index] is None:
            self.table[index] = new_node
        else:
            current = self.table[index]
            while current.next:
                current = current.next
            current.next = new_node
        self.count += 1

    def find(self, key):
        index = self.hash_function(key)
        current = self.table[index]

        while current:
            if current.key == key:
                return current.data
            current = current.next

        return None

    def delete(self, key):
        index = self.hash_function(key)
        current = self.table[index]
        prev = None

        while current:
            if current.key == key:
                if prev:
                    prev.next = current.next
                else:
                    self.table[index] = current.next
                self.count -= 1
                return
            prev = current
            current = current.next

    def print_HT(self):
        for i, item in enumerate(self.table):
            current = item
            while current:
                print(f'"{current.data.quote}" - {current.data.title}, {current.data.year}')
                current = current.next

    def load_factor(self):
        return self.count / self.size

    def num_items(self):
        return self.count

    def num_buckets(self):
        return sum(1 for item in self.table if item)

# Helper function to read CSV and populate the hash table
def read_csv(file_name, hash_table):
    with open(file_name, 'r', encoding='utf-8') as file:
        header = file.readline().strip().split(',')
        quote_index = header.index('quote')
        movie_index = header.index('movie')
        year_index = header.index('year')

        for line in file:
            data = line.strip().split(',')
            quote = data[quote_index]
            movie = data[movie_index]
            year = data[year_index]
            movie_title = movie.split(':')[0].strip()  # Extracting movie title
            movie_obj = Movie(quote, movie_title, year)
            hash_table.add(movie_title, movie_obj)

# Main function
def main():
    table_size = 977  # Choose a prime number
    movie_hash_table = HashTable(table_size)
    read_csv('movie_quotes.csv', movie_hash_table)

    while True:
        command = input("Enter a command (? for help): ").lower()
        
        if command == 'add':
            # Implement add functionality
            pass
        elif command == 'delete':
            # Implement delete functionality
            pass
        elif command == 'find':
            movie_title = input("Enter movie title: ")
            result = movie_hash_table.find(movie_title)
            if result:
                print(f'"{result.quote}" - {result.title}, {result.year}')
            else:
                print("Movie not found.")
        elif command == 'printHT':
            movie_hash_table.print_HT()
        elif command == 'load':
            print(f"Current load factor: {movie_hash_table.load_factor()}")
        elif command == 'count':
            print(f"Number of items in the table: {movie_hash_table.num_items()}")
        elif command == 'buckets':
            print(f"Number of non-empty buckets: {movie_hash_table.num_buckets()}")
        elif command == 'who':
            print("I am ChatGPT.")
        elif command == 'hash(k)':
            # Implement hash(k) functionality
            pass
        elif command == 'help' or command == '?':
            print("Available commands: add, delete, find, printHT, load, count, buckets, who, hash(k), help, exit")
        elif command == 'exit':
            print("Exiting program. Goodbye!")
            break
        else:
            print("Invalid command. Enter '?' for help.")

if __name__ == "__main__":
    main()
Leave a Comment