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;
}
}