0

I'm trying to implement a dictionary with a hash table (not using Java's provided hash table classes, but rather made from scratch). Below is the find() method from my Dictionary class, used to detect whether or not a key is in the table when inserting/removing. If the key is already in the table, it returns a score associated with the key (elements in the table are inserted as pairs of key/score into LinkedLists in each table position). If not, it returns -1.

I am running a supplied test program to determine if my Dictionary class works, but I am encountering a NullPointerException when reaching a certain point. Included below is the particular test. Why would this exception be coming up? (I can provide more code if needed!)

Find:

public int find(String config) {
    for (int i = 0; i < dictSize; i++) {
        if (dict[i] != null) {
            LinkedList<DictEntry> current = dict[i];
            String currentConfig = current.peek().getConfig(); //Dictionary.java:66

            if (currentConfig.equals(config)) {
                int currentScore = current.peek().getScore();
                return currentScore;
            }
        }
    }

    return -1;
}

Insert:

public int insert(DictEntry pair) throws DictionaryException {
    String entryConfig = pair.getConfig();
    int found = find(entryConfig); //Dictionary.java:27

    if (found != -1) {
        throw new DictionaryException("Pair already in dictionary.");
    }

    int entryPosition = hash(entryConfig);

    if (dict[entryPosition] == null) { //Dictionary.java:35
        LinkedList<DictEntry> list = new LinkedList<DictEntry>();
        dict[entryPosition] = list;
        list.add(pair);
        return 0;
    } else {
        LinkedList<DictEntry> list = dict[entryPosition];
        list.addLast(pair);
        return 1;
    }
}

The test:

    // Test 7: insert 10000 different values into the Dictionary
        // NOTE: Dictionary is of size 9901
    try {
        for (int i = 0; i < 10000; ++i) {
            s = (new Integer(i)).toString();
            for (int j = 0; j < 5; ++j) s += s;
            collisions += dict.insert(new DictEntry(s,i)); //TestDict.java:69
        }
        System.out.println("   Test 7 succeeded");
    } catch (DictionaryException e) {
        System.out.println("***Test 7 failed");
    }

Exception stack trace:

Exception in thread "main" java.lang.NullPointerException
    at Dictionary.find(Dictionary.java:66)
    at Dictionary.insert(Dictionary.java:27)
    at TestDict.main(TestDict.java:69)
Improve this question
3
  • 1
    Please post your exception stack trace as well. Commented Oct 16, 2012 at 6:15
  • and also post insert method code Commented Oct 16, 2012 at 6:17
  • private LinkedList[] dict; is an array to hold linked lists. The elements to be added to the table will be hashed and added to the corresponding linked list in the corresponding position. Commented Oct 16, 2012 at 6:20

1 Answer 1

Reset to default
5

peek() returns null that's why. You can have a nullity check prior to getConfig() call.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Is the check if (dict[i] != null) not sufficient? Should I have a second check just for getConfig()?
Replace String currentConfig = current.peek().getConfig(); by DictEntry entry = current.peek(); if( entry != null ) { String currentConfig = entry.getConfig(); ... }
exactly @Aubin, thanks. The check you made with dict[i] only checks if that object is null. Calling peek() checks the head of the list, null if the list is empty.
Thank you, this worked! It got rid of the NullPointerException, but now I am getting an ArrayIndexOutOfBoundsException. Is this simply because the array of size 9901 can't hold 10000 elements? Because I thought the test would generate collisions, so I shouldn't expand the table size.
In a hash table collisions are handled by linked lists. Only "perfect" hash function gives different key with no collision and they are tailor made for a specific context, it's not the case for general purpose containers. cs.auckland.ac.nz/~jmor159/PLDS210/niemann/s_has.htm
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.