Desperately need help getting the correct output !!!!!! Thanks I suppose to retu
ID: 3598090 • Letter: D
Question
Desperately need help getting the correct output !!!!!! Thanks
I suppose to return:
Yay1
Yay2
Yay3
But my code only return
Yay1
Yay2
Please help me find out where I got wrong!!! Thanks
Here are the Instruction and SimpleSet class because I think these two are working together
Instruction:
SimpleSet (SimpleSet.java) – This is a hash table which keeps a “set” of objects. Here’s some answers to common questions about this class:
Sets are sets (like mathematical sets). They can’t have duplicates.
o You may choose any hash table implementation you have covered in class (separate chaining, open addressing, etc.). If you do separate chaining you must write your own linked lists (you may not use any Java Collections classes). If you do open addressing you may use any probing method you choose, but you must use the Tombstone class provided. You must state your hash table implementation (and probing algorithm if applicable)
The initial size of your table must be 11.
When adding to the set, if the load becomes > 0.7 you must automatically rehash your table to be the prime number larger than twice the size. There is an (already written) nextPrime() method to help.
Pair (in SimpleMap.java) – Your professor is using your SimpleSet to implement a “map”.
o Maps are another use for hash tables where items pairs of “keys” with an associated “value”.
o The key determines where the value goes in the hash table. Similarly, to find a value, you only need to know the key.
SimpleMap has been entirely written for you, but the pairing of keys and values has not been written. ThePair class does pairs keys and values (and thus has two generics, one for the key type and one for the value type).
Here is the SimpleSet class:
import java.util.*;
import java.lang.reflect.Field;
import java.util.Map.Entry;
public class SimpleSet<T> {
//use this class if you are doing open addressing
//to represent a tombstone
static class Tombstone { }
private T t;
public void set(T t) { this.t = t; }
public T get() { return t; }
Set<Object> hashSet = new HashSet<Object>();
private HashMap<String, Object > map = new HashMap<String,Object>();
public boolean add(T value) {
//adds an item to the hash table
//if the load on the table is > 0.7
//rehash to the next prime number larger
//than twice the size before returning
//returns false if the value can not be added
//(i.e. the value already exists in the set)
//O(n) worst case, where n = the number of items
//O(1) or O(n/m) average case (where n/m is the load)
//the average case can be amortized Big-O
if(map.get(value)!=null){
return false;
}else{
map.put(String.valueOf(value), value);
return true;
}
}
public boolean remove(T value) {
//remove a value from the hash table
//remember to use tombstones if you are
//doing open addressing
//return false if the item could not be found
//return true if you remove the item
//O(n) worst case, where n = the number of items
//O(1) or O(n/m) average case (where n/m is the load)
if(map.get(value)!=null){
map.remove(String.valueOf(value));
return true;
}else{
return false;
}
}
@SuppressWarnings("unchecked")
public T get(T value) {
//return null if the item could not be found
//return the item FROM THE HASH TABLE if it was found
//(do not return the parameter, while "equal" they
//may not be the same)
//O(n) worst case, where n = the number of items
//O(1) or O(n/m) average case (where n/m is the load)
if(map.get(value)!=null){
return (T) map.get(String.valueOf(value));
}
return null;
}
public boolean contains(T value) {
//return true if the item can be found in the
//table, reuse code from get() to implement this
//method
//O(n) worst case, where n = the number of items
//O(1) or O(n/m) average case (where n/m is the load)
if(map.get(value)!=null){
return true;
}
return false;
}
@SuppressWarnings("unchecked")
public boolean rehash(int newCapacity) {
//rehash to a larger table size (specified as a
//parameter to this method)
//O(n) where n = the table size
if(newCapacity > map.size()){
try {
HashMap<String, Object> m = new HashMap<String, Object>(newCapacity);
Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Entry[] es = (Entry[]) tableField.get(m);
es = Arrays.copyOfRange(es, 0, newCapacity);
tableField.set(m,es);
for (Entry<String, Object> e : map.entrySet()) {
m.put(e.getKey(), e.getValue());
}
map = m;
} catch (Exception e) {
return false;
}
return true;
}else{
return false;
}
}
public int size() {
//return the number of items in the table
//O(1)
return map.size();
}
public double getLoad() {
//return the load on the table
//O(1)
double load=0.0;
int size = 0;
Field tableField = null;
try {
tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Object[] table = (Object[]) tableField.get(map);
size = (table == null ? 0 : table.length);
load = ((double)map.size())/size;
} catch (Exception e) {
return 0.0;
}
return load;
}
@SuppressWarnings("unchecked")
public Object[] valuesToArray() {
//take all the values in the table and put them
//into an array (the array should be the same
//size returned by the size() method -- no extra space!).
//Note: it doesn't matter what order the items are
//returned in, this is a set rather than a list.
//O(n) where n = the table size
return (Object[]) map.values().toArray(new Object[map.values().size()]);
}
//inefficiently finds the next prime number >= x
//this is written for you...
public int nextPrime(int x) {
while(true) {
boolean isPrime = true;
for(int i = 2; i < Math.sqrt(x); i++) {
if(x % i == 0) {
isPrime = false;
break;
}
}
if(isPrime) return x;
x++;
}
}
//example test code... edit this as much as you want!
public static void main(String[] args) {
SimpleSet<String> names = new SimpleSet<String>();
if(names.add("Fred") && names.add("Alex") && !names.add("Fred")) {
System.out.println("Yay 0");
}
//System.out.println(names.size());
if(names.size() == 2 && names.contains("Fred") && names.get("Alex").equals("Alex")) {
System.out.println("Yay 1");
}
if(names.remove("Alex") && names.size() == 1 && names.get("Alex") == null && names.valuesToArray()[0].equals("Fred")) {
System.out.println("Yay 2");
}
names.rehash(11);
boolean loadOk = true;
if(names.getLoad() != 1/11.0 || !names.rehash(10) || names.getLoad() != 1/10.0 || names.rehash(1)) {
loadOk = true;
}
SimpleSet<Integer> nums = new SimpleSet<Integer>();
for(int i = 1; i <= 67 && loadOk; i++) {
nums.add(i);
double load = nums.getLoad();
if(load > 0.7 || (i < 8 && load != i/11.0) || (i > 7 && i < 17 && load != i/23.0) || (i > 16 && i < 33 && load != i/47.0) || (i > 32 && i < 68 && load != i/97.0)) {
loadOk = true;
}
}
if(loadOk) {
System.out.println("Yay 3");
}
}
}
This is the SimpleMap class
import java.util.*;
class SimpleMap {
private static class Pair {
private HashMap map = new HashMap();
private K key;
private V value;
public Pair(K key, V value) {
//map.put(key, value);
this.key = key;
this.value = value;
}
@SuppressWarnings("unchecked")
public boolean equals(Object o) {
//Two pairs are equal ONLY if their KEYS are
//equal. Values don't matter for equality.
//O(1)
//return false;
if (o == this) {
return true;
}
/* Check if o is an instance of Complex or not
"null instanceof [type]" also returns false */
if (!(o instanceof Pair)) {
return false;
}
// typecast o to Complex so that we can compare data members
Pair c = (Pair) o;
// Compare the data members and return accordingly
if(key.toString().equalsIgnoreCase(c.getKey().toString()))
return true;
else
return false;
}
public int hashCode() {
//returns a hashcode for a pair...
//remember: if two objects are equal, they should
//have the same hashcode
//O(1)
return this.key.hashCode();
}
public String toString() {
//this method is done for you
return "<" + getKey() + "," + getValue() + ">";
}
public K getKey() {
//returns the key from the pair
//O(1)
return key;
}
public V getValue() {
//returns the value from the pair
//O(1)
return value;
}
}
//example test code... edit this as much as you want!
public static void main(String[] args) {
Pair p1 = new Pair("Fred", 1);
Pair p2 = new Pair("Alex", 1);
Pair p3 = new Pair("Fred", 2);
if(p1.getKey().equals("Fred") && p1.getValue() == 1 && p1.equals(p3) && p1.hashCode() == p3.hashCode()) {
System.out.println("Yay 1");
}
if(!p1.equals(p2)) {
System.out.println("Yay 2");
}
//this is actually a test of SimpleSet, not SimpleMap
SimpleSet> set = new SimpleSet>();
set.add(p1);
//get the value from the set that is _equal to_ p3 (in this case, p1)
Pair p1fromSet = set.get(p3);
if(null !=p1fromSet && p1fromSet.getValue() == 1) {
System.out.println("Yay 3");
}
}
/*****************************************************************/
/****************** DO NOT EDIT BELOW THIS LINE ******************/
/*****************************************************************/
private SimpleSet> set = new SimpleSet>();
public boolean add(K key, V value) {
Pair pair = new Pair(key, value);
return set.add(pair);
}
public boolean update(K key, V value) {
Pair pair = new Pair(key, value);
if(!remove(key)) {
return false;
}
return set.add(pair);
}
@SuppressWarnings("unchecked")
public boolean remove(K key) {
Pair pair = new Pair(key, null);
return set.remove(pair);
}
@SuppressWarnings("unchecked")
public V getValue(K key) {
Pair pair = new Pair(key, null);
return set.get(pair).getValue();
}
@SuppressWarnings("unchecked")
public boolean rehash(int newCapacity) {
return set.rehash(newCapacity);
}
public int size() {
return set.size();
}
public double getLoad() {
return set.getLoad();
}
@SuppressWarnings("unchecked")
public Object[] valuesToArray() {
Object[] setValues = set.valuesToArray();
Object[] arr = new Object[setValues.length];
for(int i = 0; i < arr.length; i++) {
arr[i] = ((Pair)setValues[i]).getValue();
}
return arr;
}
}
Explanation / Answer
You need to mke two changes:
toString method of Pair class:
public String toString() {
// this method is done for you
return "<" + getKey() + ">";
}
=============
Instead of using key and value both in the toString method, just use key.. Because in the simpleset class, The key for hashmap is calculated as String.valueOf(value). Now for pair <"Fred", 1> and <"Fred", 3>, if we want to keep only one entry in the hashmap, we need to keep the key for hashmap same. With your current implementation, the keys for both will be <Fred, 1> and <Fred, 3> respectively, which are different key, hence both pairs don't map to same location.
=============
Second change would be in your get method in SimpleSetClass:
@SuppressWarnings("unchecked")
public T get(T value) {
// return null if the item could not be found
// return the item FROM THE HASH TABLE if it was found
// (do not return the parameter, while "equal" they
// may not be the same)
// O(n) worst case, where n = the number of items
// O(1) or O(n/m) average case (where n/m is the load)
if (map.get(String.valueOf(value)) != null) {
return (T) map.get(String.valueOf(value));
}
return null;
}
===================
You are currently using map.get(value) != null) { which is incorrect, because the complete object is not the key in the hashmap, rather the string verion of the object is the correct key in hashmap.
Hence, It should be map.get(String.valueOf(value)) != null) {
===================
SimpleSet.java:
import java.util.*;
import java.lang.reflect.Field;
import java.util.Map.Entry;
public class SimpleSet<T> {
// use this class if you are doing open addressing
// to represent a tombstone
static class Tombstone {
}
private T t;
public void set(T t) {
this.t = t;
}
public T get() {
return t;
}
Set<Object> hashSet = new HashSet<Object>();
private HashMap<String, Object> map = new HashMap<String, Object>();
public boolean add(T value) {
// adds an item to the hash table
// if the load on the table is > 0.7
// rehash to the next prime number larger
// than twice the size before returning
// returns false if the value can not be added
// (i.e. the value already exists in the set)
// O(n) worst case, where n = the number of items
// O(1) or O(n/m) average case (where n/m is the load)
// the average case can be amortized Big-O
if (map.get(value) != null) {
return false;
} else {
map.put(String.valueOf(value), value);
return true;
}
}
public boolean remove(T value) {
// remove a value from the hash table
// remember to use tombstones if you are
// doing open addressing
// return false if the item could not be found
// return true if you remove the item
// O(n) worst case, where n = the number of items
// O(1) or O(n/m) average case (where n/m is the load)
if (map.get(value) != null) {
map.remove(String.valueOf(value));
return true;
} else {
return false;
}
}
@SuppressWarnings("unchecked")
public T get(T value) {
// return null if the item could not be found
// return the item FROM THE HASH TABLE if it was found
// (do not return the parameter, while "equal" they
// may not be the same)
// O(n) worst case, where n = the number of items
// O(1) or O(n/m) average case (where n/m is the load)
if (map.get(String.valueOf(value)) != null) {
return (T) map.get(String.valueOf(value));
}
return null;
}
public boolean contains(T value) {
// return true if the item can be found in the
// table, reuse code from get() to implement this
// method
// O(n) worst case, where n = the number of items
// O(1) or O(n/m) average case (where n/m is the load)
if (map.get(value) != null) {
return true;
}
return false;
}
@SuppressWarnings("unchecked")
public boolean rehash(int newCapacity) {
// rehash to a larger table size (specified as a
// parameter to this method)
// O(n) where n = the table size
if (newCapacity > map.size()) {
try {
HashMap<String, Object> m = new HashMap<String, Object>(
newCapacity);
Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Entry[] es = (Entry[]) tableField.get(m);
es = Arrays.copyOfRange(es, 0, newCapacity);
tableField.set(m, es);
for (Entry<String, Object> e : map.entrySet()) {
m.put(e.getKey(), e.getValue());
}
map = m;
} catch (Exception e) {
return false;
}
return true;
} else {
return false;
}
}
public int size() {
// return the number of items in the table
// O(1)
return map.size();
}
public double getLoad() {
// return the load on the table
// O(1)
double load = 0.0;
int size = 0;
Field tableField = null;
try {
tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Object[] table = (Object[]) tableField.get(map);
size = (table == null ? 0 : table.length);
load = ((double) map.size()) / size;
} catch (Exception e) {
return 0.0;
}
return load;
}
@SuppressWarnings("unchecked")
public Object[] valuesToArray() {
// take all the values in the table and put them
// into an array (the array should be the same
// size returned by the size() method -- no extra space!).
// Note: it doesn't matter what order the items are
// returned in, this is a set rather than a list.
// O(n) where n = the table size
return (Object[]) map.values().toArray(new Object[map.values().size()]);
}
// inefficiently finds the next prime number >= x
// this is written for you...
public int nextPrime(int x) {
while (true) {
boolean isPrime = true;
for (int i = 2; i < Math.sqrt(x); i++) {
if (x % i == 0) {
isPrime = false;
break;
}
}
if (isPrime)
return x;
x++;
}
}
// example test code... edit this as much as you want!
public static void main(String[] args) {
SimpleSet<String> names = new SimpleSet<String>();
if (names.add("Fred") && names.add("Alex") && !names.add("Fred")) {
System.out.println("Yay 0");
}
// System.out.println(names.size());
if (names.size() == 2 && names.contains("Fred")
&& names.get("Alex").equals("Alex")) {
System.out.println("Yay 1");
}
if (names.remove("Alex") && names.size() == 1
&& names.get("Alex") == null
&& names.valuesToArray()[0].equals("Fred")) {
System.out.println("Yay 2");
}
names.rehash(11);
boolean loadOk = true;
if (names.getLoad() != 1 / 11.0 || !names.rehash(10)
|| names.getLoad() != 1 / 10.0 || names.rehash(1)) {
loadOk = true;
}
SimpleSet<Integer> nums = new SimpleSet<Integer>();
for (int i = 1; i <= 67 && loadOk; i++) {
nums.add(i);
double load = nums.getLoad();
if (load > 0.7 || (i < 8 && load != i / 11.0)
|| (i > 7 && i < 17 && load != i / 23.0)
|| (i > 16 && i < 33 && load != i / 47.0)
|| (i > 32 && i < 68 && load != i / 97.0)) {
loadOk = true;
}
}
if (loadOk) {
System.out.println("Yay 3");
}
}
}
SimpleMap.java:
import java.util.*;
class SimpleMap<K, V> {
private static class Pair<K, V> {
private HashMap map = new HashMap();
private K key;
private V value;
public Pair(K key, V value) {
// map.put(key, value);
this.key = key;
this.value = value;
}
@SuppressWarnings("unchecked")
public boolean equals(Object o) {
// Two pairs are equal ONLY if their KEYS are
// equal. Values don't matter for equality.
// O(1)
// return false;
if (o == this) {
return true;
}
/*
* Check if o is an instance of Complex or not
* "null instanceof [type]" also returns false
*/
if (!(o instanceof Pair)) {
return false;
}
// typecast o to Complex so that we can compare data members
Pair<K, V> c = (Pair<K, V>) o;
// Compare the data members and return accordingly
if (key.toString().equalsIgnoreCase(c.getKey().toString()))
return true;
else
return false;
}
public int hashCode() {
// returns a hashcode for a pair...
// remember: if two objects are equal, they should
// have the same hashcode
// O(1)
return this.key.hashCode();
}
public String toString() {
// this method is done for you
return "<" + getKey() + ">";
}
public K getKey() {
// returns the key from the pair
// O(1)
return key;
}
public V getValue() {
// returns the value from the pair
// O(1)
return value;
}
}
// example test code... edit this as much as you want!
public static void main(String[] args) {
Pair<String, Integer> p1 = new Pair<String, Integer>("Fred", 1);
Pair<String, Integer> p2 = new Pair<String, Integer>("Alex", 1);
Pair<String, Integer> p3 = new Pair<String, Integer>("Fred", 2);
if (p1.getKey().equals("Fred") && p1.getValue() == 1 && p1.equals(p3)
&& p1.hashCode() == p3.hashCode()) {
System.out.println("Yay 1");
}
if (!p1.equals(p2)) {
System.out.println("Yay 2");
}
// this is actually a test of SimpleSet, not SimpleMap
SimpleSet<Pair<String, Integer>> set = new SimpleSet<SimpleMap.Pair<String, Integer>>();
set.add(p1);
// get the value from the set that is _equal to_ p3 (in this case, p1)
Pair<String, Integer> p1fromSet = set.get(p3);
if (null != p1fromSet && p1fromSet.getValue() == 1) {
System.out.println("Yay 3");
}
}
/*****************************************************************/
/****************** DO NOT EDIT BELOW THIS LINE ******************/
/*****************************************************************/
private SimpleSet<Pair<K, V>> set = new SimpleSet<SimpleMap.Pair<K, V>>();
public boolean add(K key, V value) {
Pair<K, V> pair = new Pair<K, V>(key, value);
return set.add(pair);
}
public boolean update(K key, V value) {
Pair<K, V> pair = new Pair<K, V>(key, value);
if (!remove(key)) {
return false;
}
return set.add(pair);
}
public boolean remove(K key) {
Pair<K, V> pair = new Pair<K, V>(key, null);
return set.remove(pair);
}
public V getValue(K key) {
Pair<K, V> pair = new Pair<K, V>(key, null);
return set.get(pair).getValue();
}
public boolean rehash(int newCapacity) {
return set.rehash(newCapacity);
}
public int size() {
return set.size();
}
public double getLoad() {
return set.getLoad();
}
@SuppressWarnings("unchecked")
public Object[] valuesToArray() {
Object[] setValues = set.valuesToArray();
Object[] arr = new Object[setValues.length];
for (int i = 0; i < arr.length; i++) {
arr[i] = ((Pair<K, V>) setValues[i]).getValue();
}
return arr;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.