I'm creating an implementation of a set in Java using separate chaining with a hash table. Currently, I am just trying to add 100 random integers to the table, and then use a self-built iterator in my own implementation of toString to print the table contents. I have confirmed with the debugger that my 100 ints get added to the table, but I am confused as to where my code goes wrong with printing.
The current output I get from my toString is just a single int inside curly braces, like so: {59, }.
I have gone through the debugger a few times step by step and cannot figure out of the issue is with my iterator, toString, or a combination of both. Here is the class below:
import java.util.*;
import java.io.*;
public class MySet {
// implements a set using a separate chaining hash table
private class 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
private int lastHash; //last hash value used
private int tableSize; //current number of lists in the table
private int numElements; //number of elements in the set
private final int primes[] = {7, 23, 59, 131, 271, 563, 1171,
2083, 4441, 8839, 16319, 32467,
65701, 131413, 263983, 528991};
private int primeIndex; //last prime used
private int nextPrime(int p) {
//finds the next prime from the list above
//used for resizing and the initial size
while (primes[primeIndex] <= p)
primeIndex ;
return primes[primeIndex];
}
public MySet(int s) {
//s is a hint for the initial size
primeIndex = 0;
tableSize = nextPrime(s);
//table is an array of nodes
table = new Node[tableSize];
numElements = 0;
}
private void resize() {
//"double" the table size and reinsert the values stored in the
//current table. the table size should remain prime
int oldTableSize = tableSize;
Node oldTable[] = table;
tableSize = nextPrime(oldTableSize);
table = new Node[tableSize];
for (int i = 0; i < oldTableSize; i ) {
Node temp = oldTable[i];
while (temp != null) {
int h = hash(temp.element);
Node tempNext = temp.next;
Node temp1 = table[h];
table[h] = temp;
table[h].next = temp1;
temp = tempNext;
}
}
}
private int hash(Integer k) {
//return the hash function value for k
return Math.abs(k.hashCode() % tableSize);
}
public boolean find(Integer e) {
//returns true when e is in the set, otherwise returns false
lastHash = hash(e); //remember the last hash value used
//this can be useful in methods that call find
Node temp = table[lastHash];
while (temp != null) {
if (temp.element.equals(e)) return true;
temp = temp.next;
}
return false;
}
public void addElement(Integer e) {
//if e is not in the set add e to the set otherwise the set does not change
if(find(e)) {
return;
}
//add e to the set
int index = hash(e);
if(table[index] == null) {
table[index] = new Node(e, null);
} else if(table[index].next == null) {
table[index].next = new Node(e, null);
} else {
Node temp = table[index];
while(temp.next != null) {
temp = temp.next;
}
Node newNode = new Node(e, null);
temp.next = newNode;
}
//if after adding the new element numElements > 2*tableSize then call resize
numElements ;
if(numElements > 2 * tableSize) {
resize();
}
return;
}
//iterates through the entire table
public class MySetIterator implements Iterator<Integer> {
private Node curNode;
int index;
//implements an iterator for the set
public MySetIterator() {
curNode = table[0];
index = 0;
}
public boolean hasNext() {
return curNode.next != null;
}
public Integer next() {
if(!hasNext()) {
if(index > tableSize) {
System.out.println("\n End of table!");
}
index ;
curNode = table[index];
}
curNode = curNode.next;
return curNode.element;
}
public void remove() {
//not implemented
}
}
public Iterator<Integer> iterator() {
//returns an iterator for the set
return new MySetIterator();
}
public String toString() {
//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 { }
StringBuilder string = new StringBuilder();
if(numElements == 0) {
return "{ }";
}
string.append("{ ");
MySetIterator iterator = new MySetIterator();
while(iterator.hasNext()) {
string.append(iterator.next() ", ");
}
string.append(" }");
String toReturn = string.toString();
return toReturn;
}
public static void main(String args[]) throws IOException {
//Test driver
MySet set = new MySet(0);
Random rand = new Random();
for(int i = 0; i < 100; i ) {
set.addElement(rand.nextInt(100));
}
System.out.println(set);
}
}
If someone could point out if I'm doing something wrong here that could be causing me issues, I would appreciate it. I have a feeling I am not using my iterator implementation correctly, but that doesn't necessarily mean my iterator is correct either. Thanks.
CodePudding user response：
What happens with an iterator is that its usage looks like:
while (iterator.hasNext()) {
doSomething(iterator.next());
}
and as it stands, hasNext() returns false before next() has the chance to look for it.
Your hasNext() method will need to do all the work of finding the next entry, if there is one.
CodePudding user response：
You should not be doing anything in next() but returning a value and possibly pointing to the next potential one. hasNext() should simply return true of false if that points to a value. If it returns false and someone calls next(), that is their problem, not yours. And no need to call hasNext in your next() method. Again, that's up to the user. hasNext() should just check the appropriate variables to make certain the next value is available. Presently, your curNode.next is returning null immediately.
It also appears that everywhere you call new Node(), the second argument is null. Remember that multiple ints could hash to the same bucket. So the buckets need to contain all of those ints. One way to do this would be with a linked list but as far as I can tell, it doesn't appear that you are doing that.