Implement a class, MyQuadraticHashSet, that implements the MySet interface. Use
ID: 3572218 • Letter: I
Question
Implement a class, MyQuadraticHashSet, that implements the MySet interface. 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 code should call the above method with modifier taking on the values 0, 1, 2, 3, ... as it runs through its probe sequence.
TestHashSets will test MyQuadraticHashSet for correctness by comparing its results on add, contains, and remove operations to the results of performing the same operations on a java.util.HashSet. TimeHashSets will compare its runtime performance to that of java.util.HashSet and MyHashSet
The load threshold for 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 resize the table. The class will be tested with load thresholds of 0.1 and 0.5.
The table:The table will be an array of elements. Declare that table as Object[]. When allocating the table, execute new Object[...], since new E[...] is not allowed by the Java language when E is a generic type parameter. Where necessary, use casts of the form (E) or (E[]) in order to get the code to compile.
Deleting elements:
Declare a data field called REMOVED:
private final Object REMOVED = new Object();
Every time that an element is removed from the table, replace it with REMOVED. Then, when searching for an element, if a probe yields REMOVED, it 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).
public interface MySet<E> extends java.lang.Iterable<E> {
/** Remove all elements from this set */
public void clear();
/** Return true if the element is in the set */
public boolean contains(E e);
/** Add an element to the set */
public boolean add(E e);
/** Remove the element from the set */
public boolean remove(E e);
/** Return true if the set contains no elements */
public boolean isEmpty();
/** Return the number of elements in the set */
public int size();
/** Return an iterator for the elements in this set */
public java.util.Iterator<E> iterator();
}
import java.util.LinkedList;
public class MyHashSet<E> implements MySet<E> {
// Define the default hash table size. Must be a power of 2
private static int DEFAULT_INITIAL_CAPACITY = 4;
// Define the maximum hash table size. 1 << 30 is same as 2^30
private static int MAXIMUM_CAPACITY = 1 << 30;
// Current hash table capacity. Capacity is a power of 2
private int capacity;
// Define default load factor
private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
// Specify a load factor threshold used in the hash table
private float loadFactorThreshold;
// The number of elements in the set
private int size = 0;
// Hash table is an array with each cell that is a linked list
private LinkedList<E>[] table;
/** Construct a set with the default capacity and load factor */
public MyHashSet() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a set with the specified initial capacity and
* default load factor */
public MyHashSet(int initialCapacity) {
this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a set with the specified initial capacity
* and load factor */
public MyHashSet(int initialCapacity, float loadFactorThreshold) {
if (initialCapacity > MAXIMUM_CAPACITY)
this.capacity = MAXIMUM_CAPACITY;
else
this.capacity = trimToPowerOf2(initialCapacity);
this.loadFactorThreshold = loadFactorThreshold;
table = new LinkedList[capacity];
}
@Override /** Remove all elements from this set */
public void clear() {
size = 0;
removeElements();
}
@Override /** Return true if the element is in the set */
public boolean contains(E e) {
int bucketIndex = hash(e.hashCode());
if (table[bucketIndex] != null) {
LinkedList<E> bucket = table[bucketIndex];
for (E element: bucket)
if (element.equals(e))
return true;
}
return false;
}
@Override /** Add an element to the set */
public boolean add(E e) {
if (contains(e)) // Duplicate element not stored
return false;
if (size > capacity * loadFactorThreshold) {
if (capacity == MAXIMUM_CAPACITY)
throw new RuntimeException("Exceeding maximum capacity");
rehash();
}
int bucketIndex = hash(e.hashCode());
// Create a linked list for the bucket if it is not created
if (table[bucketIndex] == null) {
table[bucketIndex] = new LinkedList<E>();
}
// Add e to hashTable[index]
table[bucketIndex].add(e);
size++; // Increase size
return true;
}
@Override /** Remove the element from the set */
public boolean remove(E e) {
if (!contains(e))
return false;
int bucketIndex = hash(e.hashCode());
// Create a linked list for the bucket if it is not created
if (table[bucketIndex] != null) {
LinkedList<E> bucket = table[bucketIndex];
for (E element: bucket)
if (e.equals(element)) {
bucket.remove(element);
break;
}
}
size--; // Decrease size
return true;
}
@Override /** Return true if the set contains no elements */
public boolean isEmpty() {
return size == 0;
}
@Override /** Return the number of elements in the set */
public int size() {
return size;
}
@Override /** Return an iterator for the elements in this set */
public java.util.Iterator<E> iterator() {
return new MyHashSetIterator(this);
}
/** Inner class for iterator */
private class MyHashSetIterator implements java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list;
private int current = 0; // Point to the current element in list
private MyHashSet<E> set;
/** Create a list from the set */
public MyHashSetIterator(MyHashSet<E> set) {
this.set = set;
list = setToList();
}
@Override /** Next element for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
@Override /** Get current element and move cursor to the next */
public E next() {
return list.get(current++);
}
@Override /** Remove the current element and refresh the list */
public void remove() {
// Delete the current element from the hash set
set.remove(list.get(current));
list.remove(current); // Remove current element from the list
}
}
/** Hash function */
private int hash(int hashCode) {
return supplementalHash(hashCode) & (capacity - 1);
}
/** Ensure the hashing is evenly distributed */
private static int supplementalHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/** Return a power of 2 for initialCapacity */
private int trimToPowerOf2(int initialCapacity) {
int capacity = 1;
while (capacity < initialCapacity) {
capacity <<= 1;
}
return capacity;
}
/** Remove all e from each bucket */
private void removeElements() {
for (int i = 0; i < capacity; i++) {
if (table[i] != null) {
table[i].clear();
}
}
}
/** Rehash the set */
private void rehash() {
java.util.ArrayList<E> list = setToList(); // Copy to a list
capacity <<= 1; // Double capacity
table = new LinkedList[capacity]; // Create a new hash table
size = 0; // Reset size
for (E element: list) {
add(element); // Add from the old table to the new table
}
}
/** Copy elements in the hash set to an array list */
private java.util.ArrayList<E> setToList() {
java.util.ArrayList<E> list = new java.util.ArrayList<E>();
for (int i = 0; i < capacity; i++) {
if (table[i] != null) {
for (E e: table[i]) {
list.add(e);
}
}
}
return list;
}
@Override
public String toString() {
java.util.ArrayList<E> list = setToList();
StringBuilder builder = new StringBuilder("[");
// Add the elements except the last one to the string builder
for (int i = 0; i < list.size() - 1; i++) {
builder.append(list.get(i) + ", ");
}
// Add the last element in the list to the string builder
if (list.size() == 0)
builder.append("]");
else
builder.append(list.get(list.size() - 1) + "]");
return builder.toString();
}
}
import java.util.*;
public class TestHashSets
{
private enum OperationType { ADD, CONTAINS, REMOVE }
static final int NUM_VALUES = 1000000;
static final int BOUND = NUM_VALUES;
static Random rand = new Random(100);
public static void main(String args[])
{
// The following prime numbers are intended to be used
// as table sizes in hashing with quadratic probing.
final int[] primesForQuadraticProbing
= { 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949,
21911, 43853, 87719, 175447, 350899, 701819, 1403641,
2807303, 5614657, 11229331 };
System.out.println("Starting tests.");
HashSet<Integer> jcfHashSet = new HashSet<Integer>();
MyHashSet<Integer> liangHashSet = new MyHashSet<Integer>();
MyQuadraticHashSet<Integer> lowLoadSet = new MyQuadraticHashSet<Integer>(0.10, primesForQuadraticProbing);
MyQuadraticHashSet<Integer> highLoadSet = new MyQuadraticHashSet<Integer>(0.50, primesForQuadraticProbing);
System.out.println("Add operations ...");
performTests(jcfHashSet, liangHashSet, lowLoadSet, highLoadSet, OperationType.ADD);
checkSizes(jcfHashSet, liangHashSet, lowLoadSet, highLoadSet);
System.out.println("Contains operations ...");
performTests(jcfHashSet, liangHashSet, lowLoadSet, highLoadSet, OperationType.CONTAINS);
System.out.println("Remove operations ...");
performTests(jcfHashSet, liangHashSet, lowLoadSet, highLoadSet, OperationType.REMOVE);
checkSizes(jcfHashSet, liangHashSet, lowLoadSet, highLoadSet);
System.out.println("Tests successfully completed.");
System.exit(0);
}
static void performTests(HashSet<Integer> jcfHashSet, MyHashSet<Integer> liangHashSet,
MyQuadraticHashSet<Integer> lowLoadSet, MyQuadraticHashSet<Integer> highLoadSet,
OperationType ot)
{
for (int i = 0; i < NUM_VALUES; i++)
{
int value = rand.nextInt(BOUND) - BOUND / 2;
boolean jcfReturnVal;
boolean liangReturnVal;
boolean lowLoadSetReturnVal;
boolean highLoadSetReturnVal;
switch (ot)
{
case ADD:
jcfReturnVal = jcfHashSet.add(value);
liangReturnVal = liangHashSet.add(value);
lowLoadSetReturnVal = lowLoadSet.add(value);
highLoadSetReturnVal = highLoadSet.add(value);
break;
case CONTAINS:
jcfReturnVal = jcfHashSet.contains(value);
liangReturnVal = liangHashSet.contains(value);
lowLoadSetReturnVal = lowLoadSet.contains(value);
highLoadSetReturnVal = highLoadSet.contains(value);
break;
default:
jcfReturnVal = jcfHashSet.remove(value);
liangReturnVal = liangHashSet.remove(value);
lowLoadSetReturnVal = lowLoadSet.remove(value);
highLoadSetReturnVal = highLoadSet.remove(value);
}
if (jcfReturnVal != liangReturnVal || jcfReturnVal != lowLoadSetReturnVal
|| jcfReturnVal != highLoadSetReturnVal)
{
System.out.println("Error:");
System.out.println("On value: " + value);
System.out.println("The JCF HashSet returned " + jcfReturnVal);
System.out.print("The MyHashSet returned " + liangReturnVal);
System.out.println("The .10 load threshold MyQuadraticHashSet returned " + lowLoadSetReturnVal);
System.out.println("The .50 load threshold MyQuadraticHashSet returned " + highLoadSetReturnVal);
System.exit(1);
}
}
}
static void checkSizes(HashSet<Integer> jcfHashSet, MyHashSet<Integer> liangHashSet,
MyQuadraticHashSet<Integer> lowLoadSet, MyQuadraticHashSet<Integer> highLoadSet)
{
int size = jcfHashSet.size();
System.out.println("Set size: " + size);
if (size != liangHashSet.size() || size != lowLoadSet.size() || size != highLoadSet.size())
{
System.out.println("Error:");
System.out.println("The JCF HashSet has size " + size);
System.out.println("The MyHashSet has size " + liangHashSet.size());
System.out.println("The .10 load threshold MyQuadraticHashSet has size " + lowLoadSet.size());
System.out.println("The .50 load threshold MyQuadraticHashSet has size " + highLoadSet.size());
System.exit(1);
}
}
}
import java.util.*;
public class TimeHashSets
{
private enum OperationType { ADD, CONTAINS, REMOVE }
static final int NUM_VALUES = 1000000;
static final int BOUND = NUM_VALUES;
static Random rand = new Random(100);
public static void main(String args[])
{
// The following prime numbers are intended to be used
// as table sizes in hashing with quadratic probing.
final int[] primesForQuadraticProbing
= { 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949,
21911, 43853, 87719, 175447, 350899, 701819, 1403641,
2807303, 5614657, 11229331 };
System.out.println("Each hash set will be timed on " + NUM_VALUES + " add operations, "
+ NUM_VALUES + " contains operations, and " + NUM_VALUES + " remove operations.");
System.out.println("Timing JCF HashSet");
timeJcf(new HashSet<Integer>());
System.gc(); // Request garbage collection, although it doesn't seem to make much difference
System.out.println("Timing MyHashSet");
timeMySet(new MyHashSet<Integer>());
System.gc();
System.out.println("Timing MyQuadraticHashSet with load threshold = 0.10");
timeMySet(new MyQuadraticHashSet<Integer>(0.10, primesForQuadraticProbing));
System.gc();
System.out.println("Timing MyQuadraticHashSet with load threshold = 0.50");
timeMySet(new MyQuadraticHashSet<Integer>(0.50, primesForQuadraticProbing));
System.exit(0);
}
static void timeJcf(HashSet<Integer> jcfHashSet)
{
long startTime = System.currentTimeMillis();
for (int i = 0; i < NUM_VALUES; i++)
jcfHashSet.add(rand.nextInt(BOUND) - BOUND / 2);
for (int i = 0; i < NUM_VALUES; i++)
jcfHashSet.contains(rand.nextInt(BOUND) - BOUND / 2);
for (int i = 0; i < NUM_VALUES; i++)
jcfHashSet.remove(rand.nextInt(BOUND) - BOUND / 2);
long endTime = System.currentTimeMillis();
double seconds = (endTime - startTime) / 1000.0;
System.out.printf("Runtime: %1.3f seconds ", seconds);
}
static void timeMySet(MySet<Integer> mySet)
{
long startTime = System.currentTimeMillis();
for (int i = 0; i < NUM_VALUES; i++)
mySet.add(rand.nextInt(BOUND) - BOUND / 2);
for (int i = 0; i < NUM_VALUES; i++)
mySet.contains(rand.nextInt(BOUND) - BOUND / 2);
for (int i = 0; i < NUM_VALUES; i++)
mySet.remove(rand.nextInt(BOUND) - BOUND / 2);
long endTime = System.currentTimeMillis();
double seconds = (endTime - startTime) / 1000.0;
System.out.printf("Runtime: %1.3f seconds ", seconds);
}
}
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; iRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.