Assignment 4 Solution

Your task







For this assignment you will write several classes to simulate an online Music store. Make sure you implement all required methods according to the instructions given below. In addition to the required methods, you are free to add as many other private methods as you want. Note that null keys are not allowed in the hash table. Remember that in most of scenarios objects comparison does not use ‘==’.




[70 points] The class MyHashTable has the following elds:




An int for the number of entries stored inside the table.




An int for the number of buckets the table has (Note that this value is initialized by the constructor, but could change later on if the number of entries increases).




A final double representing the load factor for the hash table.




An ArrayList of buckets used to store the entries to the table. Where each bucket is a LinkedList of HashPairs.




Implement the following public methods in the MyHashTable class:




The constructor MyHashTable() which takes an int as input representing the initial capacity of the table.1 Using the input, the constructor initializes all the elds.




A put() method that takes a key and a value as input. The method adds a HashPair of the key and value to the hash table. If a HashPair with the key already exists in the hash table, then you should overwrite the old value associated with the key with the new one. This method should be O(1). If in this hash table there was a previous value associated to the given key, then the method overwrites it with the new value and returns the old one. If there was no value associated to the given key, than the method returns null.




A get() method which takes a key as input and returns the value associated with it. If there is no such key in the hash table, then the method should return null. This method should run in O(1) on average.




A remove() method that takes a key as input and removes from the table the entry (i.e. the HashPair) associated to this key. The method should return the value associated to the key. If the key is not found, then the method returns null. This method should run in O(1) on average.




A rehash() method which takes no input and modi es the table so that it contains double the number of buckets. This method should be O(n) where n the number of entries in the table.




A keys() method which takes no input and returns an ArrayList containing all the keys in the table. The keys in the returned ArrayList may be in any order. This method







1The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.






should be O(n) where n the number of entries in the table.




A values() method which takes no input and returns an ArrayList containing all the unique values in the table. The returned ArrayList of unique values may be in any order. This method should be O(n) where n the number of entries in the table.




Inside this class you should also implement the following methods from the private nested class MyHashIterator.




The constructor which should be O(n).




A hasNext() method which should be O(1) and return true if the hash table has a next HashPair.




A next() method which is also O(1) and return the next HashPair.




[30 points] Implement the following public methods inside the MusicStore class. Note that you are allowed to add as many private methods and attributes as you see t.




The constructor MusicStore() which takes as input an ArrayList of Songs to initialize the MusicStore.




A method addSong() which takes a Song as input and adds it to the MusicStore. This method should be O(1).




A method searchByTitle() which takes a String as input and returns the Song with the provided title. If there are multiple songs with the same title, you may return any one of them. Note that the input should match exactly the Song title. This method should be O(1).




A method searchByArtist() which takes a String as input representing an artist and returns an ArrayList of Songs containing all the songs in the MusicStore performed by the given artist. The Songs in the returned ArrayList may be in any order. This method should be O(1).




A method searchByYear() which takes an Integer as input representing a year and returns an ArrayList of Songs containing all the songs in the MusicStore produced in the given year. The Songs in the returned ArrayList may be in any order. This method should be O(1)





















































4