building a simple hash table from scratch

[Sami Kassoum]

Hello everyone, I am totally new here and also 1 year in learning java.
these days I am trying to understand how hash Tables works in java. I am trying to build a simple hash table from scratch,
that table would hold key and value both of type string. I am not allowed to use any generic classes here in my code.
I wan't to define tow methods for this table , set() and get()
can someone please tell me why my program dos not print out the Value "kassoum" for the key "sammy", instead I got null! ?
Thanks in advance

package javaapplication1;

class SimpleHashTable{
    
    //I declared an array of 10 linkedLists of type node
    static private Node [] hashTable  = new Node[10];
    
    public static void  main(String args[]){
        test();        
    }
    
    static class Node{               
        String key;
        String val;        
        Node next;        
    }
    // method for entering a key and value into the hash table
    static void put(String key, String value){
       int location = key.hashCode()%10; //every key string would give me its unique array index
       Node runner;         // the runner will go throught the linked list wothout loosing the head 
       runner  = hashTable[location];
       if (runner==null){//the linked list is still empty and this is the first entry
           runner = new Node();
           runner.key=key;
           runner.val = value;
       }
       else {
           while (runner!=null){
           runner = runner.next;
           }
           runner = new Node();
           runner.key=key;
           runner.val = value; 
       }    
    }
    //end of put() method
    
    static void test(){
        put ("sammy", "Kassoum");
        System.out.println(get("sammy"));
    }
    
    static String get(String key){
        int location = key.hashCode()%10;
        Node runner;
        runner = hashTable[location];
        if (runner==null)// this means that the key hasn't any value yet
            return null;
        else 
            while (runner!=null){                
                    System.out.println("this is the value :- " + runner.val);                
                    runner = runner.next;                            
            }         
        return runner.val;
    }
    
}

[Liutauras Vilda]

Welcome to the Ranch.

I have moved your topic to "Java in General" as it is too difficult for "Beginning Java".

[Norm Radder]

How are you trying to debug the code to see what it is doing?  I use print statements that print out the values of variables as their values are changed and as they are used.  The print out will show you what the code is doing and help you find the problem.

Note: A helpful technique that goes with the above is to define a toString() method in the Node class so when a Node is printed, its contents will be formatted.
Another useful debugging tool is the Arrays class's toString method for formatting arrays for printing:

  System.out.println("an ID "+ java.util.Arrays.toString(theArrayName));

[Sami Kassoum]

Liutauras Vilda wrote:Welcome to the Ranch.

I have moved your topic to "Java in General" as it is too difficult for "Beginning Java".

Thanks Vilda, I see, I agree with you it is a difficult one

[Norm Radder]

With normal debugging techniques it should be easy to find the problem and fix it.

What have you tried?

[Sami Kassoum]

Norm Radder wrote:How are you trying to debug the code to see what it is doing?  I use print statements that print out the values of variables as their values are changed and as they are used.  The print out will show you what the code is doing and help you find the problem.

Note: A helpful technique that goes with the above is to define a toString() method in the Node class so when a Node is printed, its contents will be formatted.
Another useful debugging tool is the Arrays class's toString method for formatting arrays for printing:

  System.out.println("an ID "+ java.util.Arrays.toString(theArrayName));

Thanks Norm Radder
for debugging usually I just go through the code and read it thoroughly, sometimes I try to eliminate portions of the code and try to run the other.
thanks for your advise to use the toString() method. I am working now on the code and I discovered mistakes in inserting new item to a linked list.
maybe my question is too big to be discussed here...

[Sami Kassoum]

Norm Radder wrote:With normal debugging techniques it should be easy to find the problem and fix it.

What have you tried?

Hi Norm !

this is what I have tired so far
now it seems that I have a problem with the get()

package javaapplication1;

import java.util.Arrays;

class SimpleHashTable{
    
    //I declared an array of 10 linkedLists of type node
    static private Node [] hashTable  = new Node[10];
    
    public static void  main(String args[]){
        test();   
        System.out.println(Arrays.toString(hashTable));
    }
    
    static class Node{               
        String key;
        String val;        
        Node next;        
    }
    // method for entering a key and value into the hash table
    static void put(String key, String value){
       int location = key.hashCode()%10;
       System.out.println("location value in put is " + location);
       //every key string would give me its unique array index
       Node newNode;
       newNode = new Node();
       newNode.key = key;
       newNode.val = value;       
       Node runner; // the runner will go throught the linked list wothout loosing the head 
       runner = hashTable[location];
       if (hashTable[location] == null){//the linked list is still empty and this is the first entry
           hashTable[location] = newNode;
       }
       else {
           while (runner!=null){
           runner = runner.next;
           }
           runner = new Node();
           runner.key=key;
           runner.val = value; 
       }    
    }
    //end of put() method
    
    static void test(){
        put ("sammy", "0547723878");
        System.out.println(get("sammy"));
    }
    
    static String get(String key){
        Integer location = key.hashCode()%10;
        System.out.println("location value for get is " + location.toString());
        Node runner;
        runner = hashTable[location];
        if (runner==null)// this means that the key hasn't any value yet
            return null;
        else 
            while (runner!=null){                
                    System.out.println("this is the value :- " + runner.val);                
                    runner = runner.next;                            
            }         
        return runner.val;
    }
    
}

[Norm Radder]

question is too big

No, the question is about a normal type of problem that students have.  It might be past a beginner's problem but it's not too big for here.

I have a problem with the get()  

Please explain.  Copy and paste any error messages.

[Sami Kassoum]

when I run the code I receive the following :-
run:
location value in put is 1
location value for get is 1
Exception in thread "main" java.lang.NullPointerException
this is the value :- 0547723878
at javaapplication1.SimpleHashTable.get(SimpleHashTable.java:62)
at javaapplication1.SimpleHashTable.test(SimpleHashTable.java:47)
at javaapplication1.SimpleHashTable.main(SimpleHashTable.java:11)
C:\Users\Sami Kassoum\AppData\Local\NetBeans\Cache\8.1\executor-snippets\run.xml:53: Java returned: 1
BUILD FAILED (total time: 0 seconds)

so far the put() was executed and a key + value where added, inside the get() going inside the while loop I managed to print out the value of the key "sammy", but the function fails to return the value of type string.
I have a nullPointer Error, it seems that I have gone with my 'runner' variable too far ....
I am trying to figure out why ?..

[Norm Radder]

it seems that I have gone with my 'runner' variable too far ....  

can you explain what this code from the get() method is supposed to do?

        else
            // Search down the chain until runner is null????
            while (runner!=null){                
                    System.out.println("this is the value :- " + runner.val);      //<< showing the key would also be useful          
                    runner = runner.next;                            
            }         
             //  Here the value of runner is null?  That means the following statement will throw a NPE
        return runner.val;

Note the else clause is missing {}s to enclose the code it controls.  You should always use {}s with if, else and loops

[Sami Kassoum]

Norm Radder wrote:
can you explain what this code from the get() method is supposed to do?
Note the else clause is missing {}s to enclose the code it controls.  You should always use {}s with if, else and loops

i want the get() method to print me all poissible values for my specefic key.
so I realized now that I should print the values as soon as I read them and not to return them from the method.
yes you are sure for the {} of the else , I didn't noticed that,
so here what I changed in my code and now it is running without any errors, I also fixed the null pointer error

static void get(String key){
        Integer location = Math.abs(key.hashCode())%10;
        System.out.println("location value for get is " + location.toString());
        Node runner;
        runner = hashTable[location];        
        if (runner==null)
            System.out.println("there is no such a key !");
        else 
            while (runner!=null){                
                    System.out.println("the key " + key + " has this value :- " + runner.val);                
                    runner = runner.next;                            
            }       
    }

[Norm Radder]

 want the get() method to print me all poissible values for my specefic key.  

That's a new meaning for a get() method's purpose.  Normally a get() method would return the value associated with the key passed as argument.
Your get() method shows all the values in the hash bucket for the key that was passed as an arg.   That may be a valid method for debugging, but it's not useful for someone trying to get the value associated with a key.

[Liutauras Vilda]

Norm, have a cow for a helpfulness in the whole thread.

[Sami Kassoum]

Norm Radder wrote:
That's a new meaning for a get() method's purpose.  Normally a get() method would return the value associated with the key passed as argument.
Your get() method shows all the values in the hash bucket for the key that was passed as an arg.   That may be a valid method for debugging, but it's not useful for someone trying to get the value associated with a key.

I thought that a hash table stores  one key value in each linked list and then associate to that key as many as possible value keys.
like if you have a person name as a key, then you associate multiple phone numbers for that person as values.

what I understand from you is that in one linked list inside the hash table we can find in each node different keys associated with there unique values. so in this case it would be easier to find the value
then the get() method indeed should return us a value...
so I have to change the code again....

[Norm Radder]

I have to change the code  

Yes.  Each bucket in the array has a linked list of the key/value pairs for all the keys with the same hash code.  The code needs to search the list for the key that matches the arg.

[Sami Kassoum]

Norm Radder wrote:
Yes.  Each bucket in the array has a linked list of the key/value pairs for all the keys with the same hash code.  The code needs to search the list for the key that matches the arg.

great now I understand ! different key values might have the same hash code , so I have to seek inside that bucket that its address was provided after the hash code was  generated.
so I have changed my code and now it looks like this, I also managed to  store two key-value entries

package javaapplication1;

import java.util.Arrays;

class SimpleHashTable{
    
    //I declared an array of 10 linkedLists of type node
    static private Node [] hashTable  = new Node[10];
    
    public static void  main(String args[]){
        test();   
        System.out.println(Arrays.toString(hashTable));
    }
    
    static class Node{               
        String key;
        String val;        
        Node next;        
    }
    // method for entering a key and value into the hash table
    static void put(String key, String value){
       int location = Math.abs(key.hashCode())%10;
       System.out.println("location value in put is " + location);
       //every key string would give me its unique array index
       Node newNode;
       newNode = new Node();
       newNode.key = key;
       newNode.val = value;       
       Node runner; // the runner will go throught the linked list wothout loosing the head 
       runner = hashTable[location];
       if (hashTable[location] == null){//the linked list is still empty and this is the first entry
           hashTable[location] = newNode;
       }
       else {
           while (runner!=null){
           runner = runner.next;
           }
           runner = new Node();
           runner.key=key;
           runner.val = value; 
       }    
    }
    //end of put() method
    
    static void test(){
        put ("sammy", "0547723878");
        put ("kassoum","046743491");
        System.out.println(get("sammy"));
        System.out.println(get("kassoum"));
    }
    
    static String get(String key){
        Integer location = Math.abs(key.hashCode())%10;        
        Node runner;
        runner = hashTable[location];       
        while (runner!=null){                
            if (runner.key.equals(key))
                return runner.val;
            runner = runner.next;                            
        }       
        return null;
    }
    
}

[Norm Radder]

Ok, I assume that the code is working now.  Now its time for some heavier testing. Something that will cause multiple keys to have the same hashcode
Use a loop to add lots of key/value pairs ( 1000 or 10000) with the key and value being the String value of the loop index.
So for example the keys would range from "0" to "99999";  Then do some gets.

A useful check on the efficiency of the hash would be to loop through the hashTable array and print out the length of each linked list.  The idea hash would have all the lists about the same length.

Note: The code should not use hardcoded value 10 for the hash.  It should use the length of the array.  That would allow a different number of chains instead of always 10.

[Sami Kassoum]

Hi Norm  
Sorry for answering late, I was out joging
.  Your offer sounds very interesting! So the idea is to fill 10000 nodes inside the hash table,  for the keys I will use the loop numbers,  I will wrap them in the Integer object, then I invoke the toString()  method,  for the value I can randomly create numbers then entering them as strings.  For now I have no idea how to generate strings in java, so I will stick to what I mentioned,.... I think I'll have the code tomorrow since it is getting too late here

[Norm Radder]

Maybe 10000 is too many for now.  Try something smaller first, like 40.  Print out the contents of the hashTable array and manually inspect that all the added elements are there.

[Sami Kassoum]

Norm Radder wrote:Maybe 10000 is too many for now.  Try something smaller first, like 40.  Print out the contents of the hashTable array and manually inspect that all the added elements are there.

Hi Norm here I have entered 40 pairs of (key,Value) pairs as you asked, I have also done some improvement for the code :
the program looks like it is working like it should be.
here is the code :-

package javanotebookex;
 
import java.util.Arrays;
 
class JavaNoteBook{
     
    //I declared an array of 10 linkedLists of type node
    static private int tableSize = 10;
    static private Node [] hashTable  = new Node[tableSize];
     
    public static void  main(String args[]){
        test();           
    }
     
    static class Node{               
        String key;
        String val;        
        Node next;        
    }
    // method for entering a key and value into the hash table
    static void put(String key, String value){
       int location = Math.abs(key.hashCode())%10;
       //every key string would give me its unique array index
       Node newNode;       
       newNode = new Node();
       newNode.key = key;
       newNode.val = value;       
       if (hashTable[location] == null){//the linked list is still empty and this is the first entry
           hashTable[location] = newNode;
       }
       else {
           Node runner; // the runner will go throught the linked list wothout loosing the head 
           runner = hashTable[location];       
           Node prevNode = new Node(); ;
           while (runner!=null){
               prevNode = runner; 
               runner = runner.next;
           }
           runner = newNode;
           prevNode.next = runner;
       }    
    }
    //end of put() method
     
    static void test(){
        System.out.println("the folowing are the (key,value) pairs as they are inserted to the hash Table");
        System.out.println("");
        for (Integer i = 0; i < 40 ; i++){
            Integer randomValue  = (int) (Math.random() * 1000);
            put(i.toString(), randomValue.toString());
            System.out.println("("+i.toString() + " , "  + randomValue.toString()+")");
        }
        
        System.out.println("----------------------------------------------------------------");
        System.out.println("");
        System.out.println("the folowing are the (key,value) pairs as they are printd out from hash Table");
        for (Integer i = 0; i < 40 ; i++){
            System.out.println("("+i.toString() + " , "  + get(i.toString())+")");
        }
        System.out.println("");
        System.out.println("the folowing are the length of each linked list inside the hash table");
        System.out.println("");
        for (int i  = 0 ; i < tableSize ;i ++){
            System.out.println("number of nodes in the " + i  + "th " + "linked list is " + getLinkedListSize(hashTable[i]));
        }
        
    }
     
    static String get(String key){
        Integer location = Math.abs(key.hashCode())%10;        
        Node runner;
        runner = hashTable[location];       
        while (runner!=null){                
            if (runner.key.equals(key))
                return runner.val;
            runner = runner.next;                            
        }       
        return null;
    }
    static int getLinkedListSize(Node linkedList){
        int count = 0;
        while (linkedList!=null){
            linkedList = linkedList.next;
            count++;
        }
        return count;
    }     
}

--------------------------------------------------------------------
the flowing is the output of the program
run:
the folowing are the (key,value) pairs as they are inserted to the hash Table

(0 , 145)
(1 , 362)
(2 , 810)
(3 , 588)
(4 , 993)
(5 , 568)
(6 , 585)
(7 , 671)
(8 , 608)
(9 , 274)
(10 , 391)
(11 , 387)
(12 , 756)
(13 , 871)
(14 , 32)
(15 , 49)
(16 , 370)
(17 , 112)
(18 , 47)
(19 , 281)
(20 , 873)
(21 , 175)
(22 , 723)
(23 , 279)
(24 , 524)
(25 , 413)
(26 , 816)
(27 , 482)
(28 , 461)
(29 , 917)
(30 , 65)
(31 , 855)
(32 , 635)
(33 , 91)
(34 , 653)
(35 , 73)
(36 , 693)
(37 , 971)
(38 , 618)
(39 , 171)
----------------------------------------------------------------

the folowing are the (key,value) pairs as they are printd out from hash Table
(0 , 145)
(1 , 362)
(2 , 810)
(3 , 588)
(4 , 993)
(5 , 568)
(6 , 585)
(7 , 671)
(8 , 608)
(9 , 274)
(10 , 391)
(11 , 387)
(12 , 756)
(13 , 871)
(14 , 32)
(15 , 49)
(16 , 370)
(17 , 112)
(18 , 47)
(19 , 281)
(20 , 873)
(21 , 175)
(22 , 723)
(23 , 279)
(24 , 524)
(25 , 413)
(26 , 816)
(27 , 482)
(28 , 461)
(29 , 917)
(30 , 65)
(31 , 855)
(32 , 635)
(33 , 91)
(34 , 653)
(35 , 73)
(36 , 693)
(37 , 971)
(38 , 618)
(39 , 171)

the folowing are the length of each linked list inside the hash table

number of nodes in the 0th linked list is 4
number of nodes in the 1th linked list is 4
number of nodes in the 2th linked list is 4
number of nodes in the 3th linked list is 4
number of nodes in the 4th linked list is 4
number of nodes in the 5th linked list is 4
number of nodes in the 6th linked list is 4
number of nodes in the 7th linked list is 4
number of nodes in the 8th linked list is 4
number of nodes in the 9th linked list is 4
BUILD SUCCESSFUL (total time: 0 seconds)

[Norm Radder]

Ok, looks a lot better.
Except:
the code still uses hardcoded 10 vs tableSize on lines 22 and 70

Lines 31 to 41 could be simplified to this:

       else {
           Node runner = hashTable[location];   // above test shows this is not null   
           //  Scan until .next is null -> then chain on newNode
           while (runner.next != null){
               runner = runner.next;
           }
            // .next is null, chain on newNode
           runner.next = newNode;
       }    

Another technique I use for debugging Nodes in a list is to add a toString() method to the Node class:

    public static void  main(String args[]){
        test();   
        System.out.println(Arrays.toString(hashTable));    //<<<<<<<<<<<uses toString() following is editted output
        //[Node key=2; val=749, next=Node key=13; val=922, next=Node key=22; val=499, next=Node key=31; val=761, next=null<<<<, 
        // Node key=3; val=88, next=Node key=14; val=485, next=Node key=23; val=623, next=Node key=32; val=342, next=null<<<<,
        // Node key=4; val=570, next=Node key=15; val=955, next=Node key=24; val=595, next=Node key=33; val=174, next=null<<<<, 
        // Node key=5; val=599, next=Node key=16; val=134, next=Node key=25; val=438, next=Node key=34; val=835, next=null<<<<, 
        // Node key=6; val=785, next=Node key=17; val=186, next=Node key=26; val=594, next=Node key=35; val=734, next=null<<<<, 
        // Node key=7; val=916, next=Node key=18; val=494, next=Node key=27; val=119, next=Node key=36; val=354, next=null<<<<, 
        // Node key=8; val=543, next=Node key=19; val=150, next=Node key=28; val=873, next=Node key=37; val=463, next=null<<<<, 
        // Node key=9; val=845, next=Node key=10; val=47, next=Node key=29; val=526, next=Node key=38; val=785, next=null<<<<, 
        // Node key=0; val=849, next=Node key=11; val=34, next=Node key=20; val=221, next=Node key=39; val=815, next=null<<<<, 
        // Node key=1; val=683, next=Node key=12; val=384, next=Node key=21; val=798, next=Node key=30; val=439, next=null<<<<]

    }
      
    static class Node{               
        String key;
        String val;        
        Node next;  
        public String toString() {                //><<<<<<<<<<<< for debugging
          return "Node key="+key +"; val="+val + ", next="+next +"<";
        }
    }

[Sami Kassoum]

Thank you Norm for your great help , I took your comments into my code and it works fine now.