Answer To: Assignment 2: Hash Tables (replacement for P3c & P4a) DUE: Apr. 19th at 11:59pm Extra Credit...
Alekhya answered on Apr 10 2021
demoprogram-4mrnghxt.java
demoprogram-4mrnghxt.java
//********************************************************************************
// DO NOT EDIT ANYTHING BELOW THIS LINE (except to add the JavaDocs)
//********************************************************************************
class DemoProgram {
public static void main(String[] args) {
//I cannot emphasize how bad of a design it is to do a bunch of
//if statements to choose a class type. On the other hand, this
//doing this solves a _lot_ of problems with how students submit
//their assignments... so we're just going to do this.
//Anyone who is _really_ interested in why we're doing it this way,
//or why this is normally a terrible design decision... feel free
//to ask a UTA to flag me on Piazza.
System.out.println(args);
System.out.println(args.length);
if (args.length==1 && (args[0].equals("1") || args[0].equals("2"))) {
demoProgram(args[0].equals("1"));
return;
}
else {
System.out.println("Usage: java DemoProgram [1|2]");
}
}
public static void demoProgram(boolean useTable1) {
try(java.util.Scanner input = new java.util.Scanner(System.in)) {
ThreeTenHashTable1 table1 = new ThreeTenHashTable1<>(2);
ThreeTenHashTable2 table2 = new ThreeTenHashTable2<>(2);
System.out.println("\nThis is a demo interactive program for your hash table. Be aware that both the keys and values in the table are Strings, so if you enter 1 as your key, you get the string \"1\" not the integer 1.");
while(true) {
System.out.println("\nOptions:\n\t1. Add/Replace a Key-Value Pair\n\t2. Get the value associated with a key\n\t3. Remove a key\n\t4. Resize the table\n\t5. Display the table\n\t6. Quit");
//get user selection
int choice = forceIntChoice(input, "Enter a menu choice: ", 1, 6);
//menu actions
String key, value;
int size;
switch(choice) {
case 1: //put
System.out.println("----------Adding/Updating a Key-Value Pair----------");
System.out.print("Enter a key: ");
key = input.nextLine();
System.out.print("Enter a value: ");
value = input.nextLine();
size = useTable1 ? table1.size() : table2.size();
if(useTable1) table1.put(key, value);
else table2.put(key, value);
System.out.println(((size == (useTable1 ? table1.size() : table2.size())) ? "Updated" : "Added") + " value at key.");
pauseForUser(input);
break;
case 2: //get
System.out.println("----------Getting a Value by Key----------");
System.out.print("Enter a key: ");
key = input.nextLine();
value = useTable1 ? table1.get(key) : table2.get(key);
System.out.println((value == null) ? "No such key" : "Associated value is " + value);
pauseForUser(input);
break;
case 3: //remove
System.out.println("----------Removing a Key-Value Pair----------");
System.out.print("Enter a key: ");
key = input.nextLine();
value = useTable1 ? table1.remove(key) : table2.remove(key);
System.out.println((value == null) ? "No such key" : "Removed pair was (" + key + "," + value + ")");
pauseForUser(input);
break;
case 4: //resize
System.out.println("----------Resizing the Table----------");
size = forceIntChoice(input, "Enter a new size: ", Integer.MIN_VALUE, Integer.MAX_VALUE);
boolean done = useTable1 ? table1.rehash(size) : table2.rehash(size);
System.out.println(done ? "Resized table" : "Unable to resize table to requested size");
pauseForUser(input);
break;
case 5: //display
break;
case 6: //quit
default:
return;
}
System.out.println("******************************************");
size = useTable1 ? table1.size() : table2.size();
int capacity = useTable1 ? table1.getCapacity() : table2.getCapacity();
System.out.println("Table Size: " + size + ", Capacity: " + capacity);
System.out.println(useTable1 ? table1.toStringDebug() : table2.toStringDebug());
System.out.println("******************************************");
pauseForUser(input);
}
}
catch(Exception e) {
e.printStackTrace();
}
}
private static void pauseForUser(java.util.Scanner input) {
System.out.println("(Hit to Continue)");
input.nextLine();
}
private static int forceIntChoice(java.util.Scanner input, String prompt, int min, int max) {
int choice = -1;
while(choice == -1) {
try {
System.out.print(prompt);
choice = Integer.parseInt(input.nextLine());
if(choice >= min && choice <= max) {
return choice;
}
System.out.println("You must enter an integer between "+min+" and "+max+".");
}
catch(RuntimeException e) { }
System.out.println("You must enter a valid integer.");
}
return choice;
}
}
tableentry-sjljb5gt.java
tableentry-sjljb5gt.java
class TableEntry {
private K key;
private V value;
public TableEntry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public String toString() {
return key.toString()+":"+value.toString();
}
}
threetenhashtable1-5rbmfdq1.txt
class ThreeTenHashTable1 {
//you must use this storage for the hash table
//and you may not alter this variable's name, type, etc.
private TableEntry[] storage;
private int size;
//System.out.println(storage);
/* +++++++++++++++++++ YOUR CODE HERE +++++++++++++++++++ */
//Add additional instance variables here!
//You may also add additional _private_ methods if you'd like.
@SuppressWarnings("unchecked")
public ThreeTenHashTable1(int size) {
//Create a hash table where the size of the storage is
//the provided size (number of "slots" in the table)
//You may assume size is >= 2
//Remember... if you want an array of ClassWithGeneric, the following format ___SHOULD NOT___ be used:
// ClassWithGeneric[] items = (ClassWithGeneric,[]) Object[10];
//instead, use this format:
// ClassWithGeneric[] items = (ClassWithGeneric,[]) ClassWithGeneric[10];
//TableEntry[] storage = (TableEntry,[]) ThreeTenHashTable1[size];
storage=new TableEntry[size];
}
public int getCapacity() {
return storage.length;
//return how many "slots" are in the table
//O(1)
//return storage.length;
}
public int size() {
//return the number of elements in the table
//O(1)
return size;
}
public void put(K k, V v) {
int tmp = (k.hashCode() % getCapacity());
System.out.println(k.hashCode());
if(tmp<0)
tmp=tmp+(storage.length);
//System.out.println(tmp);
int i=tmp;
do
{
if (storage[i] == null)
{
storage[i]=new TableEntry(k,v);
size++;
break;
}
else if (storage[i].getKey().equals(k))
{
storage[i] = new TableEntry(k,v);
return;
}
i = (i + 1) % storage.length;
} while (i != tmp);
double loadFactor = (double) size / getCapacity();
if(loadFactor>0.8)
rehash(getCapacity());
}
public V remove(K k) {
//Remove the given key (and associated value)
//from the table. Return the value removed.
//If the value is not in the table, return null.
//Hint 1: Remember to leave a tombstone!
//Hint 2: Does it matter what a tombstone is?
// Yes and no... You need to be able to tell
// the difference between an empty spot and
// a tombstone and you also need to be able
// to tell the difference between a "real"
// element and a tombstone.
//Worst case: O(n), Average case: O(1)
int i=k.hashCode()%storage.length;
if(i<0)
i=i+storage.length;
if(storage[i].getKey().equals(k))
{V f=storage[i].getValue();
storage[i]=null;
storage[i]=new TableEntry("tombstone",null);
size--;
return f;
}
return null;
}
public V get(K k) {
//Given a key, return the value from the table.
//If the value is not in the table, return null.
//Worst case: O(n), Average case: O(1)
int i=k.hashCode()%storage.length;
if(i<0)
i=i+storage.length;
if(storage[i].getKey().equals(k))
{
return storage[i].getValue();
}
return null;
}
public boolean isTombstone(int loc) {
//this is a helper method needed for printing
//return whether or not there is a tombstone at the
//given index
//O(1)
//System.out.println(storage[loc].getKey());
if(storage[loc]!=null) {
if(storage[loc].getKey().equals("tombstone"))
return true;}
return false;
}
@SuppressWarnings("unchecked")
public boolean rehash(int capacity) {
TableEntry[] tmp = storage;
if(capacity==storage.length) {
storage = new TableEntry[tmp.length * 2];
for (int i = 0; i < 2 * tmp.length; i++) {
// Initialised to null
storage[i]=null;
}
}
else if(size<=capacity)
{storage=new TableEntry[capacity];}
else
return false;
// Now size is made zero
// and we loop through all the nodes in the original bucket list(temp)
// and insert it into the new list
size = 0;
for (int i = 0; i < tmp.length; i++) {
if(tmp[i]!=null) {
K key = (K) tmp[i].getKey();
V val = (V) tmp[i].getValue();
// calling the insert function for each node in temp
// as the new list is now the bucketArray
put(key, val);
} }
return true;
}
//--------------------------------------------------------
// testing code goes here... edit this as much as you want!
//--------------------------------------------------------
public static void main(String[] args) {
//main method for testing, edit as much as you want
ThreeTenHashTable1 st1 = new ThreeTenHashTable1<>(10);
ThreeTenHashTable1 st2 = new ThreeTenHashTable1<>(5);
//boolean c=isTombstone(1);
/*if(st1.getCapacity() == 10 && st2.getCapacity() == 5 && st1.size() == 0 && st2.size() == 0) {
System.out.println("Yay 1");
}
st1.put("a","apple");
st1.put("b","banana");
st1.put("banana","b");
st1.put("b","butter");
if(st1.toString().equals("a:apple\nb:butter\nbanana:b") && st1.toStringDebug().equals("[0]: null\n[1]: null\n[2]: null\n[3]: null\n[4]: null\n[5]: null\n[6]: null\n[7]: a:apple\n[8]: b:butter\n[9]: banana:b")) {
System.out.println("Yay 2");
}
if(st1.getCapacity() == 10 && st1.size() == 3 && st1.get("a").equals("apple") && st1.get("b").equals("butter") && st1.get("banana").equals("b")) {
System.out.println("Yay 3");
}
st2.put("a",1);
st2.put("b",2);
st2.put("e",3);
st2.put("y",4);
if(st2.toString().equals("e:3\ny:4\na:1\nb:2") && st2.toStringDebug().equals("[0]: null\n[1]: e:3\n[2]: y:4\n[3]: null\n[4]: null\n[5]: null\n[6]: null\n[7]: a:1\n[8]: b:2\n[9]: null")) {
System.out.println("Yay 4");
}
if(st2.getCapacity() == 10 && st2.size() == 4 && st2.get("a").equals(1) && st2.get("b").equals(2) && st2.get("e").equals(3) && st2.get("y").equals(4)) {
System.out.println("Yay 5");
}
if(st2.remove("e").equals(3) && st2.getCapacity() == 10 && st2.size() == 3 && st2.get("e") == null && st2.get("y").equals(4)) {
System.out.println("Yay 6");
}
if(st2.toString().equals("y:4\na:1\nb:2") && st2.toStringDebug().equals("[0]: null\n[1]: tombstone\n[2]: y:4\n[3]: null\n[4]: null\n[5]: null\n[6]: null\n[7]: a:1\n[8]: b:2\n[9]: null")) {
System.out.println("Yay 7");
}
if(st2.rehash(2) == false && st2.size() == 3 && st2.getCapacity() == 10) {
System.out.println("Yay 8");
}
if(st2.rehash(4) == true && st2.size() == 3 && st2.getCapacity() == 4)...