Implement a generic Map class using the structure provided, you should not modif
ID: 3854765 • Letter: I
Question
Implement a generic Map class using the structure provided, you should not modify this class.
NOTE: Make sure to provide equals and hashCode methods in the private class to get this working properly
This is the provided code:
// QuadraticProbing Hash table class
//
// CONSTRUCTION: an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// bool insert( x ) --> Insert x
// bool remove( x ) --> Remove x
// bool contains( x ) --> Return true if x is present
// void makeEmpty( ) --> Remove all items
public class QuadraticProbingHashTable<AnyType>
{
/**
* Construct the hash table.
*/
public QuadraticProbingHashTable( )
{
this( DEFAULT_TABLE_SIZE );
}
/**
* Construct the hash table.
* @param size the approximate initial size.
*/
public QuadraticProbingHashTable( int size )
{
allocateArray( size );
doClear( );
}
/**
* Insert into the hash table. If the item is
* already present, do nothing.
* @param x the item to insert.
*/
public boolean insert( AnyType x )
{
// Insert x as active
int currentPos = findPos( x );
if( isActive( currentPos ) )
return false;
array[ currentPos ] = new HashEntry<>( x, true );
theSize++;
// Rehash; see Section 5.5
if( ++occupied > array.length / 2 )
rehash( );
return true;
}
/**
* Expand the hash table.
*/
private void rehash( )
{
HashEntry<AnyType> [ ] oldArray = array;
// Create a new double-sized, empty table
allocateArray( 2 * oldArray.length );
occupied = 0;
theSize = 0;
// Copy table over
for( HashEntry<AnyType> entry : oldArray )
if( entry != null && entry.isActive )
insert( entry.element );
}
/**
* Method that performs quadratic probing resolution.
* @param x the item to search for.
* @return the position where the search terminates.
*/
private int findPos( AnyType x )
{
int offset = 1;
int currentPos = myhash( x );
while( array[ currentPos ] != null &&
!array[ currentPos ].element.equals( x ) )
{
currentPos += offset; // Compute ith probe
offset += 2;
if( currentPos >= array.length )
currentPos -= array.length;
}
return currentPos;
}
/**
* Remove from the hash table.
* @param x the item to remove.
* @return true if item removed
*/
public boolean remove( AnyType x )
{
int currentPos = findPos( x );
if( isActive( currentPos ) )
{
array[ currentPos ].isActive = false;
theSize--;
return true;
}
else
return false;
}
/**
* Get current size.
* @return the size.
*/
public int size( )
{
return theSize;
}
/**
* Get length of internal table.
* @return the size.
*/
public int capacity( )
{
return array.length;
}
/**
* Find an item in the hash table.
* @param x the item to search for.
* @return the matching item.
*/
public boolean contains( AnyType x )
{
int currentPos = findPos( x );
return isActive( currentPos );
}
/**
* Return true if currentPos exists and is active.
* @param currentPos the result of a call to findPos.
* @return true if currentPos is active.
*/
private boolean isActive( int currentPos )
{
return array[ currentPos ] != null && array[ currentPos ].isActive;
}
/**
* Make the hash table logically empty.
*/
public void makeEmpty( )
{
doClear( );
}
private void doClear( )
{
occupied = 0;
for( int i = 0; i < array.length; i++ )
array[ i ] = null;
}
private int myhash( AnyType x )
{
int hashVal = x.hashCode( );
hashVal %= array.length;
if( hashVal < 0 )
hashVal += array.length;
return hashVal;
}
private static class HashEntry<AnyType>
{
public AnyType element; // the element
public boolean isActive; // false if marked deleted
public HashEntry( AnyType e )
{
this( e, true );
}
public HashEntry( AnyType e, boolean i )
{
element = e;
isActive = i;
}
}
private static final int DEFAULT_TABLE_SIZE = 101;
private HashEntry<AnyType> [ ] array; // The array of elements
private int occupied; // The number of occupied cells
private int theSize; // Current size
/**
* Internal method to allocate array.
* @param arraySize the size of the array.
*/
private void allocateArray( int arraySize )
{
array = new HashEntry[ nextPrime( arraySize ) ];
}
/**
* Internal method to find a prime number at least as large as n.
* @param n the starting number (must be positive).
* @return a prime number larger than or equal to n.
*/
private static int nextPrime( int n )
{
if( n % 2 == 0 )
n++;
for( ; !isPrime( n ); n += 2 )
;
return n;
}
/**
* Internal method to test if a number is prime.
* Not an efficient algorithm.
* @param n the number to test.
* @return the result of the test.
*/
private static boolean isPrime( int n )
{
if( n == 2 || n == 3 )
return true;
if( n == 1 || n % 2 == 0 )
return false;
for( int i = 3; i * i <= n; i += 2 )
if( n % i == 0 )
return false;
return true;
}
// Simple main
public static void main( String [ ] args )
{
QuadraticProbingHashTable<String> H = new QuadraticProbingHashTable<>( );
long startTime = System.currentTimeMillis( );
final int NUMS = 2000000;
final int GAP = 37;
System.out.println( "Checking... (no more output means success)" );
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
H.insert( ""+i );
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
if( H.insert( ""+i ) )
System.out.println( "OOPS!!! " + i );
for( int i = 1; i < NUMS; i+= 2 )
H.remove( ""+i );
for( int i = 2; i < NUMS; i+=2 )
if( !H.contains( ""+i ) )
System.out.println( "Find fails " + i );
for( int i = 1; i < NUMS; i+=2 )
{
if( H.contains( ""+i ) )
System.out.println( "OOPS!!! " + i );
}
long endTime = System.currentTimeMillis( );
System.out.println( "Elapsed time: " + (endTime - startTime) );
System.out.println( "H size is: " + H.size( ) );
System.out.println( "Array size is: " + H.capacity( ) );
}
}
Explanation / Answer
SeparateChainingHashTable.java
import java.util.LinkedList;
import java.util.List;
// SeparateChaining Hash table class
//
// CONSTRUCTION: an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// boolean contains( x ) --> Return true if x is present
// void makeEmpty( ) --> Remove all items
public class SeparateChainingHashTable<AnyType>
{
/**
* Construct the hash table.
*/
public SeparateChainingHashTable( )
{
this( DEFAULT_TABLE_SIZE );
}
/**
* Construct the hash table.
* @param size approximate table size.
*/
@SuppressWarnings("unchecked")
public SeparateChainingHashTable( int size )
{
theLists = new LinkedList[ nextPrime( size ) ];
for( int i = 0; i < theLists.length; i++ )
theLists[ i ] = new LinkedList<AnyType>( );
}
/**
* Insert into the hash table. If the item is
* already present, then do nothing.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
List<AnyType> whichList = theLists[ myhash( x ) ];
if( !whichList.contains( x ) )
{
whichList.add( x );
// Rehash; see Section 5.5
if( ++currentSize > theLists.length )
rehash( );
}
}
/**
* Remove from the hash table.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
List<AnyType> whichList = theLists[ myhash( x ) ];
if( whichList.contains( x ) )
{
whichList.remove( x );
currentSize--;
}
}
/**
* Find an item in the hash table.
* @param x the item to search for.
* @return true if x isnot found.
*/
public boolean contains( AnyType x )
{
List<AnyType> whichList = theLists[ myhash( x ) ];
return whichList.contains( x );
}
/**
* Make the hash table logically empty.
*/
public void makeEmpty( )
{
for( int i = 0; i < theLists.length; i++ )
theLists[ i ].clear( );
currentSize = 0;
}
/**
* A hash routine for String objects.
* @param key the String to hash.
* @param tableSize the size of the hash table.
* @return the hash value.
*/
public static int hash( String key, int tableSize )
{
int hashVal = 0;
for( int i = 0; i < key.length( ); i++ )
hashVal = 37 * hashVal + key.charAt( i );
hashVal %= tableSize;
if( hashVal < 0 )
hashVal += tableSize;
return hashVal;
}
@SuppressWarnings("unchecked")
private void rehash( )
{
List<AnyType> [ ] oldLists = theLists;
// Create new double-sized, empty table
theLists = new List[ nextPrime( 2 * theLists.length ) ];
for( int j = 0; j < theLists.length; j++ )
theLists[ j ] = new LinkedList<AnyType>( );
// Copy table over
currentSize = 0;
for( int i = 0; i < oldLists.length; i++ )
for( AnyType item : oldLists[ i ] )
insert( item );
}
private int myhash( AnyType x )
{
int hashVal = x.hashCode( );
hashVal %= theLists.length;
if( hashVal < 0 )
hashVal += theLists.length;
return hashVal;
}
private static final int DEFAULT_TABLE_SIZE = 101;
/** The array of Lists. */
private List<AnyType> [ ] theLists;
private int currentSize;
/**
* Internal method to find a prime number at least as large as n.
* @param n the starting number (must be positive).
* @return a prime number larger than or equal to n.
*/
private static int nextPrime( int n )
{
if( n % 2 == 0 )
n++;
for( ; !isPrime( n ); n += 2 )
;
return n;
}
/**
* Internal method to test if a number is prime.
* Not an efficient algorithm.
* @param n the number to test.
* @return the result of the test.
*/
private static boolean isPrime( int n )
{
if( n == 2 || n == 3 )
return true;
if( n == 1 || n % 2 == 0 )
return false;
for( int i = 3; i * i <= n; i += 2 )
if( n % i == 0 )
return false;
return true;
}
// Simple main
public static void main( String [ ] args )
{
SeparateChainingHashTable<Integer> H = new SeparateChainingHashTable<Integer>( );
final int NUMS = 40000;
final int GAP = 37;
System.out.println( "Checking... (no more output means success)" );
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
H.insert( i );
for( int i = 1; i < NUMS; i+= 2 )
H.remove( i );
for( int i = 2; i < NUMS; i+=2 )
if( !H.contains( i ) )
System.out.println( "Find fails " + i );
for( int i = 1; i < NUMS; i+=2 )
{
if( H.contains( i ) )
System.out.println( "OOPS!!! " + i );
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.