Implement MyQuadraticHashSet, Use open addressing with quadratic probing. For si
ID: 3572649 • Letter: I
Question
Implement MyQuadraticHashSet, Use open addressing with quadratic probing. For simplicity, use the following method to provide the index for each probe:
private static int probeIndex(int hashCode, long modifier, int tableLength)
{
return (int)((hashCode % tableLength + tableLength + modifier * modifier) % tableLength);
}
The load threshold for your hash set will be passed as a parameter to the class’s constructor. Another parameter that will be passed to the constructor is an array of prime numbers that should be used as table sizes. This array is provided by the test programs. The first value in the array is 17, indicating that the table will initially have length 17. Proceed to the next value in the array each time you need to resize the table. Your class will be tested with load thresholds of 0.1 and 0.5.
The table:
Your table will be an array of elements. You may declare that table as having type Object[]. When you allocate the table, you will need to execute new Object[...], since new E[...] is not allowed by the Java language when E is a generic type parameter. Where necessary, you can use casts of the form (E) or (E[]) in order to get your code to compile.
Deleting elements:
private final Object REMOVED = new Object();
Every time that you remove an element from the table, replace it with REMOVED. Then, when searching for an element, if a probe yields REMOVED, you should keep probing.
Resizing the table:
Resize the table whenever the number of elements in the table plus the number of occurrences of REMOVED reaches (int)(table.length * maxLoadFactor).
Explanation / Answer
import java.util.Scanner;
/** Class QuadraticProbingHashTable **/
class QuadraticProbingHashTable
{
private int currentSize, maxSize;
private String[] keys;
private String[] vals;
/** Constructor **/
public QuadraticProbingHashTable(int capacity)
{
currentSize = 0;
maxSize = capacity;
keys = new String[maxSize];
vals = new String[maxSize];
}
/** Function to clear hash table **/
public void makeEmpty()
{
currentSize = 0;
keys = new String[maxSize];
vals = new String[maxSize];
}
/** Function to get size of hash table **/
public int getSize()
{
return currentSize;
}
/** Function to check if hash table is full **/
public boolean isFull()
{
return currentSize == maxSize;
}
/** Function to check if hash table is empty **/
public boolean isEmpty()
{
return getSize() == 0;
}
/** Fucntion to check if hash table contains a key **/
public boolean contains(String key)
{
return get(key) != null;
}
/** Functiont to get hash code of a given key **/
private int hash(String key)
{
return key.hashCode() % maxSize;
}
/** Function to insert key-value pair **/
public void insert(String key, String val)
{
int tmp = hash(key);
int i = tmp, h = 1;
do
{
if (keys[i] == null)
{
keys[i] = key;
vals[i] = val;
currentSize++;
return;
}
if (keys[i].equals(key))
{
vals[i] = val;
return;
}
i = (i + h * h++) % maxSize;
} while (i != tmp);
}
/** Function to get value for a given key **/
public String get(String key)
{
int i = hash(key), h = 1;
while (keys[i] != null)
{
if (keys[i].equals(key))
return vals[i];
i = (i + h * h++) % maxSize;
System.out.println("i "+ i);
}
return null;
}
/** Function to remove key and its value **/
public void remove(String key)
{
if (!contains(key))
return;
/** find position key and delete **/
int i = hash(key), h = 1;
while (!key.equals(keys[i]))
i = (i + h * h++) % maxSize;
keys[i] = vals[i] = null;
/** rehash all keys **/
for (i = (i + h * h++) % maxSize; keys[i] != null; i = (i + h * h++) % maxSize)
{
String tmp1 = keys[i], tmp2 = vals[i];
keys[i] = vals[i] = null;
currentSize--;
insert(tmp1, tmp2);
}
currentSize--;
}
/** Function to print HashTable **/
public void printHashTable()
{
System.out.println(" Hash Table: ");
for (int i = 0; i < maxSize; i++)
if (keys[i] != null)
System.out.println(keys[i] +" "+ vals[i]);
System.out.println();
}
}
/** Class QuadraticProbingHashTableTest **/
public class QuadraticProbingHashTableTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Hash Table Test ");
System.out.println("Enter size");
/** maxSizeake object of QuadraticProbingHashTable **/
QuadraticProbingHashTable qpht = new QuadraticProbingHashTable(scan.nextInt() );
char ch;
/** Perform QuadraticProbingHashTable operations **/
do
{
System.out.println(" Hash Table Operations ");
System.out.println("1. insert ");
System.out.println("2. remove");
System.out.println("3. get");
System.out.println("4. clear");
System.out.println("5. size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter key and value");
qpht.insert(scan.next(), scan.next() );
break;
case 2 :
System.out.println("Enter key");
qpht.remove( scan.next() );
break;
case 3 :
System.out.println("Enter key");
System.out.println("Value = "+ qpht.get( scan.next() ));
break;
case 4 :
qpht.makeEmpty();
System.out.println("Hash Table Cleared ");
break;
case 5 :
System.out.println("Size = "+ qpht.getSize() );
break;
default :
System.out.println("Wrong Entry ");
break;
}
/** Display hash table **/
qpht.printHashTable();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.