Java Question

Part I.

In this project, you’ll take the hash table with quadratic probing and implemented in the modules and modify it to implement find() using the ideas presented in the modules.

Preparation

We will use FHhashQP.java and HashEntry.java from your module. We will extend FHhashQP to a new class called FHhashQPwFind.

Note: You do not need to modify HashEntry class.

class FHhashQP

Add a private instance variable countOfProbes to class FHhashQPand provide an accessor method for it.

Update countOfProbes whenever the table probes for a new position.

In your README discuss the following questions:

• Which method(s) probe for an element when adding a new key to the table?
• From the client’s perspective which method(s) may result in probing the table?
  Note: Refer to the classes that implement the hash table.

class FHhashQPwFind

Implement the class FHhashQPwFind to extend FHhashQP. Your new class will take a second parameter KeyType as you saw in the module. The syntax for this is:

public class FHhashQPwFind<KeyType, E extends Comparable<KeyType> >
   extends FHhashQP<E>
{
     // ...
}

Add the following attributes and methods:

Methods:

• A constructor which receives an int as an argument for the starting table size. Here call the constructor of the parent class which accepts an int for the initial table size. The parent constructor should initialize the countOfProbes instance variable. All other instance variables are initialized.
• E find(KeyType key) – returns the found object, or throws a java.util.NoSuchElementException
• int myHashKey( KeyType key) – a private or protected method, which provides a trivial modification to myHash() which uses the key rather than the object, to hash.
• int findPosKey( KeyType key ) – a private or protected method, which provides trivial modification to findPos() which uses the key rather than the object, to get a position.

Client Requirements

Create two wrapper classes: SongCompTitle and SongCompArtist.

Both should override the compareTo(), hashCode() and toString() methods.

Define the equals() method as described in Find() in Hash Tables such that the equals() method of the wrapper class preserves the equals() provided by the embedded data.

The toString() method should output all the data for a specific instance of our wrapper class. Given this requirement how many SongEntry objects does each wrapper class contain?

Hint: one of the wrapper classes may contain more than one.

class SongCompTitle

Wrapper class for a SongEntry object. We will use this to compare objects based on the songs String title field.

• Contains a single SongEntry object as the attribute, which we will use as key.
• Declare that it implements the Comparable< … > interface of type String.
  Note: This is similar to the example in the modules for class Employee, which you can use as a template.
• Two SongCompTitle objects are the same if the title (the key of the table) of the SongEntry objects are the same.
• Simply return the result of the SongEntry object toString() method.

class SongCompArtist

Wrapper class for a SongEntry object. We will use this to compare objects based on the songs String artist field and determine the number of songs given an artist. To simplify the implementation the artist name must be an exact match. For example, the artist “Sonny & Cher” is different from the artist “Cher”.

• Contains an attribute of type String for the artist, which we will use as key.
• Contains an attribute of type ArrayList<SongEntry> for all the songs given an artist, which is the data.
• Declare that it implements the Comparable< … > interface of type String.
  Note: This is done for you in the modules for Employees – you can use that as a template.
• Contains the method void addSong(SongEntry e), which adds a song to the list of songs.
• Two SongCompArtist are the same if the artist of the two SongCompArtist objects are equal.
• Returns a String representation which includes the artist name and the number of songs given the artist. (See sample output below.)
• Getter methods for the attributes.

class TableGenerator

Attributes:

• artists instance variable, which is an array list of String objects to be populated with artist key.
• tableOfSongTitles a hash table based on SongCompTitle.
• tableOfArtists a hash table based on SongCompArtists.

This class will create and populate two hash tables of type FHhashQPwFind class, one for each wrapper class:

Constructor:

Define the constructor such that it receives an argument of type int for the requested table size. The constructor should initialize the tables by passing the requested table size to FHhashQPwFind constructor.

Populate each hash table using:

• Write the method populateTitleTable(), which populates the tableOfSongTitles hash table.
  Note: See MyTunes for how this method is called.
• Write the method populateArtistTable(), which populates the tableOfArtists hash table and ArrayList of artists.

After populating the data print out statistics on:

• The number of songs that were attempted to be inserted.
• Number of quadratic probes performed.
• Final table size after populating with data.

class MyTunes

Creates an object of type MyTunes class that reads the song information from a JSON input file. Then, uses an object of type TableGenerator to populate two hash tables called tableOfSongTitles and tableOfArtists each which compare SongEntry objects based on different keys.

Tests the functionality of FHhashQPwFind class. Specifically checks for implementation of find() function to return an object associated with a given key input.

Suggestion: Make sure your implementation can successfully output a song by title before moving on to complete organizing songs by artists.

Example input file “findTitles.txt” provided:

Blues Power
I Got You Babe
This Love (Album Version)
Foothill College
True Confessions
Broken Bridges
The Parting Glass
The Way Of Love
Wonderwall
How Will I Know

Example input file “findArtists.txt” provided:

Blue Oyster Cult
Derek & The Dominos
Sonny & Cher
Acid Kings
Anne Murray
Big Bopper
Bita
Captain Beefheart
Cher
Country Joe & The Fish
Bob Verheecke
Derek & The Dominos
Flash And The Pan
John Stevens
Foothill College

The example test files are by no means complete. Include test cases beyond those provided. Clarify the purpose of each test case.

Output for input file using shorter JSON song data set:

Total number of songs read 12 
Testing with requested table size 10

Populating hash table of song titles...
Number of songs attempted to insert: 12
Number of quadratic probes performed: 22
Final table size for the hash table of song titles: 47

Populating hash table of artists...
Number of songs attempted to insert: 12
Number of quadratic probes performed: 0
Final table size for the hash table of artist names: 11
Test file for hash table of song titles: resources/findTitles.txt 
Requested song title "Blues Power" found
Requested song title "I Got You Babe" found
Requested song title "This Love (Album Version)" found
Requested song title "Foothill College" NOT found
Requested song title "True Confessions" NOT found
Requested song title "Broken Bridges" NOT found
Requested song title "The Parting Glass" NOT found
Requested song title "The Way Of Love" NOT found
Requested song title "Wonderwall" NOT found
Requested song title "How Will I Know" NOT found
Done with testing table of song titles.
Test file for hash table of artists names: resources/findArtists.txt 

Number of store songs given an artist:
                                       Blue Oyster Cult size      3
                                    Derek & The Dominos size      3
                                           Sonny & Cher size      4
                                           John Stevens size      2
Requested artist name "Blue Oyster Cult" found
Requested artist name "Derek & The Dominos" found
Requested artist name "Sonny & Cher" found
Requested artist name "Acid Kings" not found
Requested artist name "Anne Murray" not found
Requested artist name "Big Bopper" not found
Requested artist name "Bita" not found
Requested artist name "Captain Beefheart" not found
Requested artist name "Cher" not found
Requested artist name "Country Joe & The Fish" not found
Requested artist name "Bob Verheecke" not found
Requested artist name "Derek & The Dominos" found
Requested artist name "Flash And The Pan" not found
Requested artist name "John Stevens" found
Requested artist name "Foothill College" not found
Done with testing table of artists.

Done with MyTunes.

In your README discuss the following questions:

• Given the initial table size of 10, what is the actual initial table size used? and why?
• How does different initial table sizes impact the number of quadratic probes?
  For example, an initial table size of 3 versus 30 versus one million? Try these and reflect on the output in your README.

Finally, test your FHhashQPwFind class and find() method thoroughly on your two hash tables.

Additional Requirements:

• Your implementation of class SongCompTitle, class SongCompArtist and class FHhashQPwFind should not catch any exceptions. Instead throw the exception to the caller.
• Specify whether a method is being overridden with the @Override annotation (Links to an external site.) in your implementation.
• Provide at least one additional input file for each key.
• Change the initial requested table size. In your README discuss how this effects the number of quadratic probes performed?