Quadratic Probing with a find()

Make sure you have read and understand the Modules Information About Programming Assignments and Style Rules for Assignments before submitting this assignment.

Adding find() to Our Hash Table

This week you will implement find() using the ideas presented in the modules. As you have done recently you will realize the generic by deriving from the base class FHhashQP.

The Spec

Derive the class generic FHhashQPwFind from FHhashQP. It will take a second type parameter KeyType as you saw in the modules. The syntax for this is:

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

Add the following public method:

• E find(KeyType key) – returns the found object, or throws a java.util.NoSuchElementException

Add the following protected (or private) methods:

• int myHashKey( KeyType key) – a trivial modification to myHash() which uses the key rather than the object, to hash.
• int findPosKey( KeyType key ) – a trivial modification to findPos() which uses the key rather than the object, to get a position.

Client Requirements

• Create two wrapper classes for EBookEntry: EBookCompInt and EBookCompString. Each one contains a singleEBookEntry object and overrides the toString(), compareTo(), equals() and hashCode() methods. It also must declare that it implements the Comparable< … > interface for the appropriate basic type, Integer or String. This is done for you in the modules for Employees – you can use that as a template.
• In main() instantiate an FHhashQPwFind hash table based on one of these two wrapper classes.
• Test this on EBookEntry data by reading the data from the file, then wrapping each book and adding the wrapped object to the hash table (no array needed).
• Generate 25 random integers (scaled to the number of EBookEntries) to use as special indices. Then display the 25 from the original array (provided by the EBookEntryReader class) followed by 25 find() calls, which report success (show the found book) or failure (show a simple “not found” String).
• Test find() on two or three keys that you know are not in the hash table.
• Do everything twice, once using the int eTextNum as a key field, and a second time using a string key field, like title or creator. The accessors and mutators of EBookEntry will help you with this. You can provide one main()with one set of key choices left in and the other commented out, rather than two mains.

Here is an example of what I mean (the various occurrences of “…” stand for omitted code that is not important to the example):

// ----------- wrapper classes -------------_x000D_
_x000D_
class EBookCompInt_x000D_
   implements Comparable<Integer>_x000D_
{_x000D_
   ...  _x000D_
}_x000D_
_x000D_
class EBookCompString _x000D_
   implements Comparable<String>_x000D_
{_x000D_
   ..._x000D_
}_x000D_
_x000D_
//------------------------------------------------------_x000D_
public class Foothill_x000D_
{_x000D_
_x000D_
   public static final int NUM_RANDOM_INDICES = 25;_x000D_
   _x000D_
   // -------  main --------------_x000D_
   public static void main(String[] args) throws Exception_x000D_
   {_x000D_
      _x000D_
      // FHhashQPwFind< Integer, EBookCompInt> hashTable _x000D_
      //    = new FHhashQPwFind<Integer, EBookCompInt>();_x000D_
      _x000D_
      FHhashQPwFind< String, EBookCompString> hashTable _x000D_
         = new FHhashQPwFind<String, EBookCompString>();_x000D_
_x000D_
      ..._x000D_
  _x000D_
      // create a QP hash table of EBooks ..._x000D_
      // generate some random indices into the EBookEntryReader vector ..._x000D_
      // insert all books into the hash table (if SORT_BY_ID) or fewer (If SORT_BY_CREATOR) ..._x000D_
      // display NUM_RANDOM_INDICES books from array ..._x000D_
      _x000D_
      ..._x000D_
 _x000D_
      _x000D_
      // attempt to find on the selected key_x000D_
      System.out.println( "The same random books from the hash table " );_x000D_
      for (int k = 0; k < NUM_RANDOM_INDICES; k++)_x000D_
      {_x000D_
         ..._x000D_
         try_x000D_
         {_x000D_
            // bookResult = hashTable.find( _x000D_
            //    bookInput.getBook(randomIndices[k]).getCreator() );_x000D_
            bookResult = hashTable.find( _x000D_
               bookInput.getBook(randomIndices[k]).getETextNum() );_x000D_
_x000D_
         }_x000D_
         catch (NoSuchElementException e)_x000D_
         {_x000D_
            ... _x000D_
         }_x000D_
         System.out.println();_x000D_
      }_x000D_
      _x000D_
      // test known successes failures exceptions:_x000D_
      try_x000D_
      {_x000D_
          // bookResult = hashTable.find( "Jack Kerouac" );_x000D_
          bookResult = hashTable.find( -3 );_x000D_
          _x000D_
          ..._x000D_
          _x000D_
      }_x000D_
      catch (NoSuchElementException e)_x000D_
      {_x000D_
      }_x000D_
      _x000D_
      // more failures_x000D_
      try_x000D_
      {_x000D_
      }_x000D_
      catch (NoSuchElementException e)_x000D_
      {_x000D_
      }_x000D_
      _x000D_
      try_x000D_
      {_x000D_
      }_x000D_
      catch (NoSuchElementException e)_x000D_
      {_x000D_
      }_x000D_
   } _x000D_
}_x000D_

 

Do you need a similar assignment done for you from scratch? We have qualified writers to help you. We assure you an A+ quality paper that is free from plagiarism. Order now for an Amazing Discount!
Use Discount Code "Newclient" for a 15% Discount!

NB: We do not resell papers. Upon ordering, we do an original paper exclusively for you.