CODEWITHSUNDEEP
javaalgorithmdata-structuresadditionhashset
Wangagat
Wangagat

Reputation: 95

Implementing my own HashSet class... my add() logic seems faulty

when scanning a file for words and using the built-in hashset class from the API, my word count returns 349 (which is what it's supposed to be)

Using my home-made hashset class, I get 235... so something in my add() method must be wrong, but I can't understand what it is.

thanks for any help!

public class HashWordSet implements WordSet {

private int size = 0;
private Node[] buckets = new Node[8];

public Iterator<Word> iterator() {
    return new WordIterator();
}

//Add word if not already added
public void add(Word word) {
    int key = getBucketNumber(word);
    Node node = buckets[key];
    while (node != null) {
        if (node.value.equals(word))
            return;
        else
            node = node.next;
    }
    node = new Node(word);
    buckets[key] = node;
    size++;
    if (size == buckets.length) rehash();
}

private int getBucketNumber(Word word) {
    int hc = word.hashCode();
    if (hc < 0) hc = -hc;
    return hc % buckets.length;
}

Upvotes: 2

Views: 1495

Answers (2)

digitaljoel
digitaljoel

Reputation: 26574

node = new Node(word);
buckets[key] = node;

If there are any nodes already in the bucket you have just thrown them away. Try something like:

node = new Node(word);
node.next = buckets[key];
buckets[key] = node;

Upvotes: 1

amit
amit

Reputation: 178441

It seems like you override nodes[key] with the new word [only] instead of appending a new node to the list, so you lose all old data that was already in this node.

It should work fine if there are no elements in there before add() was invoked, but if there are - you will lose some data.

node = new Node(word);
buckets[key] = node;

Though it is hard to be 100% sure about it without the actual implementation of Node.

Upvotes: 2

Related Questions