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 publicint getSize() { returntableSize; } 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) { //Calculate the hash value of the argument. intindex = hash(e); Node current = table[index]; // Traverse the linked list to check if the element exists. while (current != null) { if (current.element.equals(e)) { returntrue; // Element found, return true. } current = current.next; } // If the element is not found, the method returns false. 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) { // Calculate the hash value for the input element intindex = hash(e); // Traverse the linked list at the index corresponding to the hash value Node current = table[index]; while (current != null) { // If the element is already in the set, do nothing and return if (current.element.equals(e)) { return; } current = current.next; } // If the element is not already in the set, add it to the linked list at the appropriate index Node newNode = new Node(e, table[index]); table[index] = newNode; numElements++; // If the number of elements in the set is greater than twice the table size, resize the table 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 { //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; } } } Here Is the Question below: Consider the lines of code below MySet test = new MySet(6); for(int i = 0;i<=14;i++) test.addElement(i); a) Draw the hashtable right before the resize method is triggered b) Draw the hashtable after the for loop completes. Note: In the above code, I do have tableSize = nextPrime(s)
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
publicint getSize() {
returntableSize;
}
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)
{
//Calculate the hash value of the argument.
intindex = hash(e);
Node current = table[index];
// Traverse the linked list to check if the element exists.
while (current != null) {
if (current.element.equals(e)) {
returntrue; // Element found, return true.
}
current = current.next;
}
// If the element is not found, the method returns false.
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)
{
// Calculate the hash value for the input element
intindex = hash(e);
// Traverse the linked list at the index corresponding to the hash value
Node current = table[index];
while (current != null) {
// If the element is already in the set, do nothing and return
if (current.element.equals(e)) {
return;
}
current = current.next;
}
// If the element is not already in the set, add it to the linked list at the appropriate index
Node newNode = new Node(e, table[index]);
table[index] = newNode;
numElements++;
// If the number of elements in the set is greater than twice the table size, resize the table
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;
}
}
}
Here Is the Question below:
Consider the lines of code below
|
MySet test = new MySet(6); for(int i = 0;i<=14;i++) test.addElement(i); a) Draw the hashtable right before the resize method is triggered b) Draw the hashtable after the for loop completes. Note: In the above code, I do have tableSize = nextPrime(s) |
Step by step
Solved in 3 steps
