} Based on the given code, Please help me to answer the below question. 2) Consider the lines of code below a) Which call to addElement will trigger the resize method? Describe where this happens in your code and how your resize method works. Why do we need to “rehash” each element? b) Draw the hashtable right before the resize method is triggered c) Draw the hashtable after the for loop completes. 1 MySet test = new MySet(6); 2 for(int i = 0;i<14;i++) { 3 test.addElement(i);
This is the code below:
package hashset;
import java.util.Iterator;
public class MySet {
// implements a set using a separate chaining hash table
privateclass Node {
private Integer element;
private Node next;
private Node(Integer e, Node n) {
element = e;
next = n;
}
}
private Node table[]; //an array of linked list
privateinttableSize; //current number of lists in the table
privateintnumElements; //number of elements in the set
privatefinalintprimes[] = {7, 23, 59, 131, 271, 563, 1171,
2083, 4441, 8839, 16319, 32467,
65701, 131413, 263983, 528991};
privateintprimeIndex; //last prime used
privateint nextPrime(intp) {
//finds the next prime from the list above
//used for resizing and the initial size
while (primes[primeIndex] <= p)
primeIndex++;
returnprimes[primeIndex];
}
public MySet(ints) {
//s is a hint for the initial size
primeIndex = 0;
tableSize = nextPrime(s);
table = new Node[tableSize];
numElements = 0;
}
//return the hash function value for k
privateint hash(Integer k) {
return Math.abs(k.hashCode() % tableSize);
}
//"double" the table size and reinsert the values stored in the
//current table. the table size should remain prime
privatevoid resize()
{
// Double the table size
intnewSize = nextPrime(tableSize * 2);
Node[] newTable = new Node[newSize];
for (inti = 0; i < tableSize; i++) {
Node current = table[i];
while (current != null) {
Node next = current.next;
intindex = hash(current.element);
current.next = newTable[index];
newTable[index] = current;
current = next;
}
}
table = newTable;
tableSize = newSize;
}
//returns true when e is in the set, otherwise returns false
publicboolean find(Integer e)
{
intindex = hash(e);
Node current = table[index];
while (current != null) {
if (current.element.equals(e)) {
returntrue;
}
current = current.next;
}
returnfalse;
}
//if e is not in the set add e to the set otherwise the set does not change
//if after adding the new element numElements > 2*tableSize then call resize
publicvoid addElement(Integer e)
{
intindex = hash(e);
Node current = table[index];
while (current != null) {
if (current.element.equals(e)) {
return; // already in the set
}
current = current.next;
}
// not found, add to the set
Node newNode = new Node(e, table[index]);
table[index] = newNode;
numElements++;
if (numElements > 2 * tableSize) {
resize();
}
}
//returns a string representation for the set
//the string representation of the set is { followed by a comma delimiter list of set
//elements followed by a }. The string for the empty set is {}
//For example, {1,2,3}.
//Note that you SHOULD NOT have any spaces in your String
/*
* Example:
* table[0]: 2 -> 4
* table[1]: 1 -> 3
*
* The string representation of this set is {2,4,1,3}
*/
//toString method
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
MySetIterator iter = new MySetIterator();
while (iter.hasNext()) {
sb.append(iter.next());
if (iter.hasNext()) {
sb.append(",");
}
}
sb.append("}");
returnsb.toString();
}
publicclass MySetIterator implements Iterator<Integer> {
//implements an iterator for the set
privateintcurrentList;
private Node currentNode;
//helper method that finds the next non empty bucket
privatevoid nextList() {
while (currentList < tableSize && table[currentList] == null) {
currentList++;
}
currentNode = (currentList < tableSize) ? table[currentList] : null;
}
public MySetIterator() {
currentList = 0;
nextList();
}
//returns true if the iteration has more elements.
publicboolean hasNext() {
returncurrentNode != null;
}
//Returns the next element in the iteration.
public Integer next() {
Integer rVal = currentNode.element;
if (currentNode.next != null) {
//what should the currentNode be?
currentNode = currentNode.next;
}
else {
//No more elements in the current bucket
//I need to get the next bucket
currentList++;
nextList();
}
returnrVal;
}
}
public Iterator<Integer> iterator() {
//returns an iterator for the set
returnnew MySetIterator();
}
class Main {
publicstaticvoid main(String[] args) {
MySet mySet = new MySet(10);
// Add elements to the set
mySet.addElement(1);
mySet.addElement(2);
mySet.addElement(3);
mySet.addElement(4);
mySet.addElement(5);
// Print the set
System.out.println("Set: " + mySet.toString());
// Find elements in the set
System.out.println("Find 3: " + mySet.find(3)); // Should return true
System.out.println("Find 6: " + mySet.find(6)); // Should return false
// Add more elements to trigger resize
mySet.addElement(6);
mySet.addElement(7);
mySet.addElement(8);
mySet.addElement(9);
mySet.addElement(10);
mySet.addElement(11);
// Print the set after resizing
System.out.println("Set after resizing: " + mySet.toString());
}
}
Based on the given code, Please help me to answer the below question.
2) Consider the lines of code below
a) Which call to addElement will trigger the resize method? Describe where this
happens in your code and how your resize method works. Why do we need to
“rehash” each element?
b) Draw the hashtable right before the resize method is triggered
c) Draw the hashtable after the for loop completes.
1 MySet test = new MySet(6);
2 for(int i = 0;i<14;i++) {
3 test.addElement(i);
Trending now
This is a popular solution!
Step by step
Solved in 5 steps
