Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Solve using python Please Also Explain using the comment The hash-based set is built using a Python list to store the buckets where each bucket

Solve using python

Please Also Explain using the comment

The hash-based set is built using a Python list to store the buckets where each bucket is another Python list. The initial bucket list size is 8 and rehashing (double the bucket list size) takes place when the number of elements equals the number of buckets.

Furthermore, code skeletons outlining which methods we expect for each data structure are written at the end. They also contain an example program showing how the various methods can be used.

Notice: You are not allowed to make any changes to the method signatures in the given skeletons. Also, the demo programs should work as outlined in the provided example programs once your implementations are complete. Your task is simply to complete the given code fragments in the skeletons. However, feel free to add additional methods

HashSet.py

from dataclasses import dataclass

from typing import List

@dataclass

class HashSet:

buckets: List[List] = None

size: int = 0

def init(self):

self.size = 0

self.buckets = [[] for i in range(8)]

# Computes hash value for a word (a string)

def get_hash(self, word):

pass # Placeholder code ==> to be replaced

# Doubles size of bucket list

def rehash(self):

pass # Placeholder code ==> to be replaced

# Adds a word to set if not already added

def add(self, word):

pass # Placeholder code ==> to be replaced

# Returns a string representation of the set content

def to_string(self):

pass # Placeholder code ==> to be replaced

# Returns current number of elements in set

def get_size(self):

pass # Placeholder code ==> to be replaced

# Returns True if word in set, otherwise False

def contains(self, word):

pass # Placeholder code ==> to be replaced

# Returns current size of bucket list

def bucket_list_size(self):

pass # Placeholder code ==> to be replaced

# Removes word from the set if there does nothing

# if word not inset

def remove(self, word):

pass # Placeholder code ==> to be replaced

# Returns the size of the bucket with most elements

def max_bucket_size(self):

pass # Placeholder code ==> to be replaced

hash_main.py

import HashSet as hset

# Program starts

# Initialize word set

words = hset.HashSet() # Create new empty HashSet

words.init() # Initialize with eight empty buckets

# Add names to word set. Notice: a) contains duplicate names,

# b) more than eight names ==> will trigger rehash

names = ["Ella", "Owen", "Fred", "Zoe", "Adam", "Ceve", "Adam", "Ceve", "Jonas", "Ola", "Morgan", "Fredrik", "Simon", "Albin", "Jonas", "Amer", "David"]

for name in names:

words.add(name)

print(" to_string():", words.to_string()) # { Adam David Amer Ceve Owen Ella Jonas Morgan Fredrik Zoe Fred Albin Ola Simon }

print("get_size():", words.get_size()) # 14

print("contains(Fred):", words.contains("Fred")) # True

print("contains(Bob):", words.contains("Bob")) # False

# Hash specific data

mx = words.max_bucket_size()

print(" max bucket:", mx) # 2

buckets = words.bucket_list_size()

print("bucket list size:", buckets) # 16

# Remove elements

delete = ["Ceve", "Adam", "Ceve", "Jonas", "Ola"]

for s in delete:

words.remove(s)

print(" get_size:", words.get_size()) # 10

print("to_string():", words.to_string()) # { David Amer Owen Ella Morgan Fredrik Zoe Fred Albin Simon }

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Students also viewed these Databases questions