Instructions
Requirements and Specifications
Source Code
LAB 8
import java.util.HashSet;
import java.util.Random;
/**
*
* @author SivasamyA
*/
public class Lab8 {
public static final int CAPACITY = 200131;
/*
Some primes of the form 4n+3:
251
2887
10039
25867
50119
100019
200131
...
999983
1101319
2000003
...
9999991 <-- Good luck!
39999983 <-- Good luck!!
58115887 <-- Good luck!!!
*/
public static final int HOW_MANY = (int)(.439 * CAPACITY);
public static final int ONE_OUT_OF = 5;
public static final int SEED = 271001;
public static void main(String args[]) {
MyHashTable ht1 = new MyHashTable(CAPACITY),
ht2 = new MyHashTable(CAPACITY);
HashSet hs1 = new HashSet(CAPACITY),
hs2 = new HashSet(CAPACITY);
Random rand = new Random(SEED);
System.out.print("Inserting " + HOW_MANY + " numbers...");
long start = System.currentTimeMillis();
for (int i = 0; i < HOW_MANY; i++) {
int rnum = rand.nextInt(Short.MAX_VALUE);
ht1.add(rnum);
hs1.add(rnum);
ht2.add(rnum);
hs2.add(rnum);
}
long end = System.currentTimeMillis();
System.out.println("done, time=" + (end - start));
System.out.print("Checking equivalence...");
start = System.currentTimeMillis();
boolean uniqueElementsEqual = MyHashTable.equalsUniqueElements(ht1, ht2);
end = System.currentTimeMillis();
boolean unqiqueElementsEqualCorrect = hs1.equals(hs2);
System.out.println("done, equivalence=" + uniqueElementsEqual +
", time=" + (end - start) + ", result=" +
((unqiqueElementsEqualCorrect == uniqueElementsEqual) ? "correct" : "incorrect"));
MyHashTable ht = ht1;
HashSet hs = hs1;
if (rand.nextInt(ONE_OUT_OF) == 0) {
ht = ht2;
hs = hs2;
}
System.out.print("Removing one random value...");
start = System.currentTimeMillis();
int removeMe = rand.nextInt(Short.MAX_VALUE);
boolean removed = ht.remove(removeMe);
while (removed == false) {
removeMe = rand.nextInt(Short.MAX_VALUE);
removed = ht.remove(removeMe);
}
hs.remove(removeMe);
end = System.currentTimeMillis();
System.out.println("done, removed=" + removeMe + ", time=" +
(end - start));
System.out.print("Removing all occurrences of " + removeMe + "...");
int removeCount = 1;
while (ht.locate(removeMe) != null) {
ht.remove(removeMe);
removeCount++;
}
System.out.println("done, remove count=" + removeCount);
System.out.print("Checking equivalence again...");
start = System.currentTimeMillis();
uniqueElementsEqual = MyHashTable.equalsUniqueElements(ht1, ht2);
end = System.currentTimeMillis();
unqiqueElementsEqualCorrect = hs1.equals(hs2);
System.out.println("done, equivalence=" + uniqueElementsEqual +
", time=" + (end - start) + ", result=" +
((unqiqueElementsEqualCorrect == uniqueElementsEqual) ? "correct" : "incorrect"));
}
}
MY HASH TABLE
import java.util.Iterator;
import java.util.NoSuchElementException;
/*
Give a comment block, if modifed.
*/
public class MyHashTable {
// Give a comment block, if modified.
private class MyHashTableItem {
public boolean isValid = true;
public E data;
// Give a comment block, if modified.
public MyHashTableItem(E inData) { data = inData; }
}
// Give a comment block, if modified.
private int hash(T key) {
return key.hashCode() % table.length;
}
private MyHashTableItem[] table; // Required
private int num; // Required
// Give a comment block, if modified.
public MyHashTable(int inCapacity) {
if (inCapacity < 0)
throw new IllegalArgumentException();
table = new MyHashTableItem[inCapacity];
}
// Give a comment block, if modified.
public int size() { return num; }
// Give a comment block, if modified.
/**
Improvement:
A bucket which has been removed can also be used, so if bucket is invalid, add inObj there
@param inObj object to be added to table
@return true if inObj is added else false
*/
public boolean add(T inObj) {
int bucket = hash(inObj), bucketsProbed = 0, tableSize = table.length;
while (bucketsProbed < tableSize) {
if (table[bucket] == null || !table[bucket].isValid) {
table[bucket] = new MyHashTableItem(inObj);
num++;
return true;
}
bucket++;
if (bucket == tableSize)
bucket = 0;
bucketsProbed++;
}
return false;
}
// Give a comment block, if modified.
public boolean remove(T inObj) {
int bucket = hash(inObj), bucketsProbed = 0, tableSize = table.length;
while (table[bucket] != null && bucketsProbed < tableSize) {
if (table[bucket].isValid && table[bucket].data.equals(inObj)) {
table[bucket].isValid = false;
num--;
return true;
}
bucket++;
if (bucket == tableSize)
bucket = 0;
bucketsProbed++;
}
return false;
}
// Give a comment block, if modified.
public T locate(T inObj) {
int bucket = hash(inObj), bucketsProbed = 0, tableSize = table.length;
while (table[bucket] != null && bucketsProbed < tableSize) {
if (table[bucket].isValid && table[bucket].data.equals(inObj))
return table[bucket].data;
bucket++;
if (bucket == tableSize)
bucket = 0;
bucketsProbed++;
}
return null;
}
// Give a comment block, if modified.
private class MyHashTableIterator implements Iterator {
private int next = 0, tableSize;
private MyHashTable myHt;
// Give a comment block, if modified.
public MyHashTableIterator(MyHashTable inHt) {
myHt = inHt;
tableSize = inHt.table.length;
while (next < tableSize &&
(myHt.table[next] == null ||
myHt.table[next].isValid == false))
next++;
}
// Give a comment block, if modified.
public T next() {
try {
T retObj = myHt.table[next++].data;
while (next < tableSize &&
(myHt.table[next] == null ||
myHt.table[next].isValid == false))
next++;
return retObj;
} catch (ArrayIndexOutOfBoundsException ex) {
throw new NoSuchElementException();
}
}
// Do not modify.
public void remove() {
/* No implementation */
throw new UnsupportedOperationException();
}
// Give a comment block, if modified.
public boolean hasNext() {
return next < tableSize &&
myHt.table[next] != null &&
myHt.table[next].isValid != false;
}
}
// Give a comment block, if modified.
public Iterator iterator() {
return new MyHashTableIterator<>(this);
}
// Give a comment block, if modified.
public String toString() {
String hashTableStr = "MyHashTable[size=" + num + ", ";
Iterator itr = iterator();
while (itr.hasNext()) {
T obj = itr.next();
hashTableStr += obj;
if (itr.hasNext())
hashTableStr += ", ";
}
hashTableStr += "]";
return hashTableStr;
}
/**
Iterate through inHt1
Improvement: Use locate method instead of iterating through inHT2
if unable to locate the element then return false else return true
O(n) = n
@param inHt1 HashMap to compare
@param inHt2 HashMap to compare
@param class of elements in HashMaps
@return true if elements in inHt1 are same asinHt2 else false
*/
public static boolean equalsUniqueElements(MyHashTable inHt1,
MyHashTable inHt2) {
Iterator itr1 = inHt1.iterator();
while (itr1.hasNext()) {
T obj1 = itr1.next();
if (inHt2.locate(obj1) == null)
return false;
}
return true;
}
}