I'm implementing a hashset, and I got some problems with it. I've got it to add word-objects, but it still add duplicates which it shouldn't. My contains method works though. I would like some help to sort it out
I know the problem is in the add method, but I can't really figure what I should do there. I've pretty much stuck in one way of thinking and some fresh ideas would be nice.
java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class HashWordSet implements WordSet {
private int N;
ArrayList<Node> buckets;
public HashWordSet(){
buckets = new ArrayList<Node>();
}
private class Node {
Word word;
Node next;
}
public void add(Word word) {
if(buckets.size() == 0){
Node newNode = new Node();
newNode.word = word;
buckets.add(0, newNode);
}
else{
int pos = getBucketNumber(word);
Node current = buckets.get(pos);
if(contains(word)){
current = current.next;
}
Node newNode = new Node();
newNode.word = word;
newNode.next = buckets.get(pos);
buckets.set(pos, newNode);
}
N++;
}
private int getBucketNumber(Word wrd) {
int hc = wrd.hashCode();
int result = hc % (buckets.size());
return result; // Simple hash function
}
public boolean contains(Word word) {
int h = getBucketNumber(word);
Node current = buckets.get(h);
while (current != null)
{
if (current.word.equals(word))
return true;
current = current.next;
}
return false;
}
public boolean isEmpty() {
return (N == 0);
}
public int size() {
return N;
}
public String toString(){
Node node= null;
return node.word.toString();
}
public Iterator<Word> iterator() {
return new HashWordIterator();
}
private class HashWordIterator implements Iterator<Word> {
private int bucket;
private Node current;
private int previousBucket;
private Node previous;
public HashWordIterator()
{
current = null;
bucket = -1;
previous = null;
previousBucket = -1;
}
public boolean hasNext() {
if (current != null && current.next != null)
return true;
return false;
}
public Word next() {
previous = current;
previousBucket = bucket;
if (current == null || current.next == null)
{
// Move to next bucket
bucket++;
while (bucket < buckets.size()&& buckets.get(bucket) == null)
bucket++;
if (bucket < buckets.size())
current = buckets.get(bucket);
else
throw new NoSuchElementException();
}
else // Move to next element in bucket
current = current.next;
return current.word;
}
public void remove() {
throw new UnsupportedOperationException("The method remove () is not implemented");
}
}
}
the interface
java
public interface WordSet extends Iterable<Word> {
public void add(Word word); // Add word if not already added
public boolean contains(Word word); // Return true if word contained
public int size(); // Return current set size
public String toString(); // Print contained words
}
and the word class if needed
java
public class Word implements Comparable<Word>{
private String word;
private int result = 0;
public Word(){
word = "" ;
}
public Word(String str) {
word = str;
}
public String toString() {
return word.toString();
}
/* Override Object method */
public int hashCode() {
result = word.toUpperCase().hashCode();
if(result <0)
result = -result;
return result;
}
/* Override Object method */
public boolean equals(Object obj) {
if (obj instanceof Word){
return ((Word) obj).word.equalsIgnoreCase(word);
}
return false;
}
public int compareTo(Word w) {
return word.compareToIgnoreCase(w.word);
}
}
| 