HashTable implementation using chained objects

Question

I have this implementation for inserting into a hashtable that uses sequential chaining:

public void insert(String word, Definition definition) {

       int hash = hashFunction(word);
       

        if (table[hash] == null) {           
            EntryImplSub chainedEntry = new EntryImplSub(null);
            chainedEntry.addDefinition(definition);
            chainedEntry.setWord(word);
            
            table[hash] = chainedEntry;
            numProbes++;
            entries++;

        } 
        
        else{
            
            EntryImplSub chainedEntry = new EntryImplSub(table[hash]);
            chainedEntry.addDefinition(definition);
            chainedEntry.setWord(word);
  
            table[hash] = chainedEntry;
            numProbes++;
            }
            
      }

Essentially, I am trying to make a dictionary. There is an EntryImpl class that acts as an entry object, and each entry has a word and definition (or multiple definitions). Now I have made a new extended class EntryImplSub that is meant to be chained. This new class has a getNext() method and inherits all the other functionality from the normal EntryImpl class. The EntryImplSub constructor is used to set next.

Question

However this is not working. When I load in a large number of words they are not all entered. And I am not sure why.

My Attempt

My logic with this implementation is that if the table entry is null, we insert a new EntryImplSub object with next = null, and then set the word and definition.

If however there is already a word at the position we are trying to insert into, then we must add our new entry to the front of the list. So we create a new EntryImplSub object with the next attribute being set to whatever was already in the table. Then I set the word for the new EntryImplSub and insert this into the table. So we should have a linked list of EntryImplSub.

I am really not sure why this inst working. I've spent hours trying to find an error, and any help would be appreciated. Let me know if you need clarification on anything.

Thanks a lot!

EDIT

Here is the code that checks if an entry is in the table

 public List<Definition> getDefinitions(String word) {

    int hash = hashFunction(word);
    //ChainedEntry head = table[hash];
    while (table[hash] != null) {
        numSearches++;

        if (((EntryImpl) table[hash]).getWord().equals(word)) {
            return ((EntryImpl) table[hash]).getDefinitions();
        }
        table[hash] = table[hash].getNext();
    }

    return null;
}

If this returns null, then the word is not in the table

I assume you have read the built in implementation of HashTable and you are familiar with that. I suggest you configure your HashTable to have just one bucket and find the simplest example where this fails in a unit test and attempt to debug it. Most likely you can get a test with just a few entries to fail. — Peter Lawrey
– Peter Lawrey, Commented May 3, 2015 at 8:07
I know it's not working because when I load entries they arnt all in the hashtable — fosho
– fosho, Commented May 3, 2015 at 8:10
And how do you know they're not all in the table? Where is the code filling the table and checking that it contains everything. Note that there's big problem with your implementation: if you insert a word twice, it doesn't replace the definition, but adds a new one. — JB Nizet
– JB Nizet, Commented May 3, 2015 at 8:12

Peter Lawrey · Accepted Answer · 2015-05-03 08:10:06Z

1

I would simplify the code like this and write a short units test. Most likely this will take 2 - 3 entries to reproduce the problem which is most likely in code you haven't shown.

public void insert(String word, Definition definition) {
   int hash = 0; // put everything in one bucket for now // hashFunction(word);

    if (table[hash] == null) 
        entries++;        

    EntryImplSub chainedEntry = new EntryImplSub(table[hash]);
    chainedEntry.addDefinition(definition);
    chainedEntry.setWord(word);

    table[hash] = chainedEntry;
    numProbes++;
}

Since the word cannot be changed I would make it a constructor argument (and a final field)

answered May 3, 2015 at 8:10

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

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

5 Comments

Peter Lawrey Over a year ago

@Daniel what could be making your life hard is that you have to find a combination of words which hit the same bucket before you see a problem.

fosho Over a year ago

Perhaps the error is comes up when I search for the word? this is what im using

fosho Over a year ago

'public List<Definition> getDefinitions(String word) { int hash = hashFunction(word); //ChainedEntry head = table[hash]; while (table[hash] != null) { numSearches++; if (((EntryImpl) table[hash]).getWord().equals(word)) { return ((EntryImpl) table[hash]).getDefinitions(); } table[hash] = table[hash].getNext(); } return null; }'

JB Nizet Over a year ago

@Daniel post that code in your question. Not in comments.

Peter Lawrey Over a year ago

@Daniel the best way to know if the problem is when you read or write to the structure is to examine it in the debugger. If it's right or wrong in the debugger you know which side the problem is.

JB Nizet · Accepted Answer · 2015-05-03 08:25:09Z

1

Your code to find the definitions is incorrect: it modifies the structure of the hashtable:

table[hash] = table[hash].getNext();

this replaces the entry in a bucket by the next one, thus effectively removing the previous ones from the map.

Since your insert code only ever adds one definition to an entry anyway, and since the same word can be added several times in the map, the code should look like

int hash = hashFunction(word);
List<Definition> result = new ArrayList<>();
EntryImpl entry = table[hash];
while (entry != null) {
    if (entry.getWord().equals(word)) {
        result.addAll(entry.getDefinitions());
    }
    entry = entry.getNext();
}
return result;

answered May 3, 2015 at 8:25

JB Nizet

694k94 gold badges1.3k silver badges1.3k bronze badges

Collectives™ on Stack Overflow

HashTable implementation using chained objects

Question

My Attempt

EDIT

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Question

My Attempt

EDIT

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related