Use quadratic hashing to reimplement the hash table public class Table<K, E> { p
ID: 3547558 • Letter: U
Question
Use quadratic hashing to reimplement the hash table
public class Table<K, E>
{
private int manyItems;
private Object[ ] keys;
private Object[ ] data;
private boolean[ ] hasBeenUsed;
public Table(int capacity)
{
if (capacity <= 0)
throw new IllegalArgumentException("Capacity is negative");
keys = new Object[capacity];
data = new Object[capacity];
hasBeenUsed = new boolean[capacity];
}
public boolean containsKey(K key)
{
return(findIndex(key)!= -1);
}
private int findIndex(K key)
{
//Postcondition: If the specified key is found in the table, then the return
// value is the index of the specified key. Otherwise, the return value is - 1
int count = 0;
int i = hash(key);
while ((count < data. length) && (hasBeenUsed[i]))
{
if (key . equals (keys[i]))
return i ;
count++;
i = nextIndex(i);
}
return -1;
}
@SuppressWarnings("unchecked")
public E get(K key)
{
int index = findIndex(key);
if (index == -1)
return null;
else
return (E) data [index] ;
}
private int hash (Object key)
// The return value is a valid index of the table's arrays. The index is calculated as the
//remainder when the absolute value of the key's hash code is divided by the size of the
//table's arrays.
{
return Math.abs(key.hashCode( )) % data.length;
}
private int nextIndex(int i)
// The return value is normally i+1. But if i+1 is data.length, then the return value Is zero //instead,
{
if (i+1 == data.length)
return 0;
else
return i+1;
}
private E put(K key, E element)
{
int index = findIndex(key);
E answer;
if (index!=-1)
{
answer =(E) data[index];
data[index]= element;
return answer;
}
else if (manyItems < data.length)
{//the key is not yet in this table.
index = hash (key);
while (keys[index] != null)
index = nextIndex (index);
keys[index] = key;
data[index] = element;
hasBeenUsed[index] = true;
manyItems++;
return null;
}
else
{//the table is full.
throw new IllegalStateException("Table is full.");
}
}
@SuppressWarnings("unchecked")
private E remove (K key)
{
int index = findIndex(key);
E answer = null;
if (index!=-1)
{
answer =(E) data[index];
keys[index]= null;
data[index] = null;
manyItems--;
}
return answer;
}
}
Explanation / Answer
public class QuadraticProbingHashTable { /** * 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 ); makeEmpty( ); } /** * Insert into the hash table. If the item is * already present, do nothing. * @param x the item to insert. */ public void insert( Hashable x ) { // Insert x as active int currentPos = findPos( x ); if( isActive( currentPos ) ) return; array[ currentPos ] = new HashEntry( x, true ); // Rehash; see Section 5.5 if( ++currentSize > array.length / 2 ) rehash( ); } /** * Expand the hash table. */ private void rehash( ) { HashEntry [ ] oldArray = array; // Create a new double-sized, empty table allocateArray( nextPrime( 2 * oldArray.length ) ); currentSize = 0; // Copy table over for( int i = 0; i = array.length ) // Implement the mod /* 6*/ currentPos -= array.length; } /* 7*/ return currentPos; } /** * Remove from the hash table. * @param x the item to remove. */ public void remove( Hashable x ) { int currentPos = findPos( x ); if( isActive( currentPos ) ) array[ currentPos ].isActive = false; } /** * Find an item in the hash table. * @param x the item to search for. * @return the matching item. */ public Hashable find( Hashable x ) { int currentPos = findPos( x ); return isActive( currentPos ) ? array[ currentPos ].element : null; } /** * 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( ) { currentSize = 0; for( int i = 0; iRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.