Hash table implementation JAVA

Hi experts, I am required to implement a hash table that uses single linked lists. The official description is as such (sorry if some stuff is useless, its a copy paste):

"Consider the following (contiguous) list of 26 components. This list is to be used to store words - all words beginning with 'a' or 'A' in component 1; 'b', 'B' in component 2, etc. If there is more than 1 word starting with a  particular letter, then the 'overflow' (or collided) words are to be stored in an 'overflow' linked list associated with that component - hence the pointer field attached to each component. In addition, the data field of the node has an integer field which keeps count of the number of times that that particular word has been inserted into the structure. This structure is an example of a hash table. Each datum is placed into the structure in a component position which is determined by applying a hash function (ie a mathematical formula) to the datum. If this position is already filled, then we say a collision has occurred, and the collided datum is placed in the overflow linked list associated with this position. In the above example, the hash function is a simple one - the conversion of the first character of the word into its ordinal position in the alphabet. A hash table is meant to give direct access to data - hence the core part of the table can be implemented via an array. Because a hash function is not generally a 1-1 mapping (but is many-to-1), collisions in array components must be handled. The overflow lists, if implemented dynamically, serve this purpose quite well."

My code below is for the class hash table which will be called upon by the "main" class. I have already implemented the single linked list class.

I am having trouble trying to come up with a way to first check if a slot that is mapped by a key is empty, therefore I can put the word in. But if the slot is full, as in there are more than one words associated with that key, the word has to be put in the appropriate linked list.

Hope that makes sense.

Basically I am missing the part that is in the if statement...

Cheers,

Dennis


package assignment3;
 
public class Hash_Table {
    
    // Need array sizes of 52, because 2 x 26 (size of alphabet) for both lower and upper case
    
    private String single_words[] = new String[52];
    private Linked_List collision_list[] = new Linked_List[52];
 
    // Constructor
 
    public Hash_Table(){
 
 
    }
 
    // This method assigns a mapping key to the incoming word
 
    public void hash_word(String in_word){
 
        int map_key;
 
        // Determine the first letter of the word
 
        char first_letter = in_word.charAt(0);
 
        // The ASCII character encoding scheme gives the letter 'a' the value 97;
        // subsequent letters, such as 'b' is 98, and so on. Therefore we can map the value by
        // subtracting the value 96 from the first letter's numerical value, as per the
        // the ASCII scheme
 
        map_key = (int) first_letter - 96;
 
        // Check to see if there are any words in the hash table with that key
 
        if(single_words[map_key] == null){
 
        // No word associated with that key, so assign the word to that slot
 
            single_words[map_key] = in_word;
 
 
        }
 
        // There are more than one words with that key, add word to linked list
 
        else{
 
 
        }
 
    }
 
 
}

Open in new window

datopdogg7Asked:
Who is Participating?
 
objectsCommented:
other than that  it looks fine

0
 
objectsCommented:
             collision_list[map_key].add(in_word);

0
 
objectsCommented:
you can actually avoid your single_words array by storing all words (matching a bucket) in the linked list.

0
Cloud Class® Course: CompTIA Cloud+

The CompTIA Cloud+ Basic training course will teach you about cloud concepts and models, data storage, networking, and network infrastructure.

 
datopdogg7Author Commented:
Hey objects,

But the if statement is incomplete because the very first addition to the slot will be fine. But then what happens if a second word with the same key is inputted? then the slot will have to be cleared, and both words will have to be put in the linked list. Then the third word with the same mapping will have to know that a) the slot that can hold just one word is empty and b) there is now a link list associated with that mapping that the word has to be added to ....

Hope that helps

Dennis
0
 
datopdogg7Author Commented:
Unfortunately the assignment deliverables don't allow that.... I know that would be nice :(
0
 
objectsCommented:
>              collision_list[map_key].add(in_word);

woops, forgot to check if it is there already

if (!collision_list[map_key].contains(in_word))
{
   collision_list[map_key].add(in_word);
}

0
 
datopdogg7Author Commented:
Would this work?
    public void hash_word(String in_word){
 
        int map_key;
 
        // Determine the first letter of the word
 
        char first_letter = in_word.charAt(0);
 
        // The ASCII character encoding scheme gives the letter 'a' the value 97;
        // subsequent letters, such as 'b' is 98, and so on. Therefore we can map the value by
        // subtracting the value 96 from the first letter's numerical value, as per the
        // the ASCII scheme
 
        map_key = (int) first_letter - 96;
 
        // Check to see if there are any words in the hash table with that key
 
        if(single_words[map_key] == null && (collision_list[map_key].getListCount() == 0)){
 
        // No word associated with that key, so assign the word to that slot
 
            single_words[map_key] = in_word;
 
 
        }
 
        // There is one word associate with that key, remove single word from array,
        // and add both the word removed from the array and the new word to the linked list
 
        else if(single_words[map_key] != null && (collision_list[map_key].getListCount() == 0)){
 
 
        }
        
        // There is more than one word associate with that key, add to single linked list
        
        else{
            
            
        }
 
    }

Open in new window

0
 
objectsCommented:
not sure I'm following. If there is something in single_words array why wouldn't you just add the word to the overflow list?
0
 
datopdogg7Author Commented:
The prof doesn't want us to use the overflow list if there is only word associated with the mapping key.
0
 
objectsCommented:
       // There is one word associate with that key, remove single word from array,
        // and add both the word removed from the array and the new word to the linked list

If theres a word already associated then doesn't the new word just go into the overflow?

0
 
datopdogg7Author Commented:
I think I implemented a good solution. Please check it over objects, then I will close the question and award points for the help.

Dennis
    public void hash_word(String in_word){
 
        int map_key;
 
        // Determine the first letter of the word
 
        char first_letter = in_word.charAt(0);
 
        // The ASCII character encoding scheme gives the letter 'a' the value 97;
        // subsequent letters, such as 'b' is 98, and so on. Therefore we can map the value by
        // subtracting the value 96 from the first letter's numerical value, as per the
        // the ASCII scheme
 
        map_key = (int) first_letter - 96;
 
        // Check to see if there are any words in the hash table with that key
 
        if(single_words[map_key].getWord() == null && (collision_list[map_key].getListCount() == 0)){
 
            // No word associated with that key, so assign the word to that slot and
            // increment frequency
 
            single_words[map_key].setWord(in_word);
            single_words[map_key].incrementWordFrequency();
 
 
        }
 
        // There is one word associate with that key, remove single word from array,
        // and add both the word removed from the array and the new word to the linked list
 
        else if(single_words[map_key].getWord() != null && (collision_list[map_key].getListCount() == 0)){
 
            // If the word in the array is the same as the incoming word then
            // only the frequency needs updating
 
            if(single_words[map_key].getWord().compareTo(in_word) == 0){
 
                // Update frequency
                
                single_words[map_key].incrementWordFrequency();
                
                
            }
            
            // Two words are different
            
            else{
            
                // Remove word currently in the array and add to link list, then
                // reset old instance of Word in the array
                
                collision_list[map_key].addWord(single_words[map_key]);
                single_words[map_key].resetWord();
 
                // Create instance of word for the incoming word and update
                // the frequency of the data member in the instance.
 
                Word new_word = new Word();
                new_word.setWord(in_word);
                new_word.incrementWordFrequency();
 
                // Add the word to the collision list
 
                collision_list[map_key].addWord(new_word);
 
            }
 
 
 
        }
        
        // There is more than one word associate with that key, add to single linked list
 
        else{
 
                // Create instance of word for the incoming word and update
                // the frequency of the data member in the instance.
 
                Word new_word = new Word();
                new_word.setWord(in_word);
                new_word.incrementWordFrequency();
 
                // Add the word to the collision list
 
                collision_list[map_key].addWord(new_word);
 
 
        }
 
    }

Open in new window

0
 
objectsCommented:
>         if(single_words[map_key].getWord() == null && (collision_list[map_key].getListCount() == 0)){

won't list count always be zero, if array is empty

                // Remove word currently in the array and add to link list, then
                // reset old instance of Word in the array
               
                collision_list[map_key].addWord(single_words[map_key]);
                single_words[map_key].resetWord();

not sure I understand why you do this. I would think it is the same as the case where the list was not empty

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.