Java Program to Implement Hash Tables chaining with Singly Linked Lists

«
»
This is a Java Program to implement hash tables chaining with Singly Linked List. A hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found. In order to prevent collision, hash tables are chained with another data structure ( Singly Linked List in this case ).

Here is the source code of the Java program to implement hash tables chaining with Singly Linked List. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  *    Java Program to Implement Hash Tables chaining with Singly Linked Lists
  3.  */
  4.  
  5. import java.util.Scanner;
  6.  
  7. /* Node for singly linked list */
  8. class SLLNode
  9. {
  10.     SLLNode next;
  11.     int data;
  12.  
  13.     /* Constructor */
  14.     public SLLNode(int x)
  15.     {
  16.         data = x;
  17.         next = null;
  18.     }
  19. }
  20.  
  21. /* Class HashTableChainingSinglyLinkedList */
  22. class HashTableChainingSinglyLinkedList
  23. {
  24.     private SLLNode[] table;
  25.     private int size ;
  26.  
  27.     /* Constructor */
  28.     public HashTableChainingSinglyLinkedList(int tableSize)
  29.     {
  30.         table = new SLLNode[ nextPrime(tableSize) ];
  31.         size = 0;
  32.     }
  33.     /* Function to check if hash table is empty */
  34.     public boolean isEmpty()
  35.     {
  36.         return size == 0;
  37.     }
  38.     /* Function to clear hash table */
  39.     public void makeEmpty()
  40.     {
  41.         int l = table.length;
  42.         table = new SLLNode[l];
  43.         size = 0;
  44.     }
  45.     /* Function to get size */
  46.     public int getSize()
  47.     {
  48.         return size;
  49.     }
  50.     /* Function to insert an element */
  51.     public void insert(int val)
  52.     {
  53.         size++;
  54.         int pos = myhash(val);        
  55.         SLLNode nptr = new SLLNode(val);                
  56.         if (table[pos] == null)
  57.             table[pos] = nptr;            
  58.         else
  59.         {
  60.             nptr.next = table[pos];
  61.             table[pos] = nptr;
  62.         }    
  63.     }
  64.     /* Function to remove an element */
  65.     public void remove(int val)
  66.     {
  67.         int pos = myhash(val);    
  68.         SLLNode start = table[pos];
  69.         SLLNode end = start;
  70.         if (start.data == val)
  71.         {
  72.             size--;
  73.             table[pos] = start.next;
  74.             return;
  75.         }
  76.         while (end.next != null && end.next.data != val)
  77.             end = end.next;
  78.         if (end.next == null)
  79.         {
  80.             System.out.println("\nElement not found\n");
  81.             return;
  82.         }
  83.         size--;
  84.         if (end.next.next == null)
  85.         {
  86.             end.next = null;
  87.             return;
  88.         }
  89.         end.next = end.next.next;
  90.         table[pos] = start;
  91.     }
  92.     /* Function myhash */
  93.     private int myhash(Integer x )
  94.     {
  95.         int hashVal = x.hashCode( );
  96.         hashVal %= table.length;
  97.         if (hashVal < 0)
  98.             hashVal += table.length;
  99.         return hashVal;
  100.     }
  101.     /* Function to generate next prime number >= n */
  102.     private static int nextPrime( int n )
  103.     {
  104.         if (n % 2 == 0)
  105.             n++;
  106.         for ( ; !isPrime( n ); n += 2);
  107.  
  108.         return n;
  109.     }
  110.     /* Function to check if given number is prime */
  111.     private static boolean isPrime( int n )
  112.     {
  113.         if (n == 2 || n == 3)
  114.             return true;
  115.         if (n == 1 || n % 2 == 0)
  116.             return false;
  117.         for (int i = 3; i * i <= n; i += 2)
  118.             if (n % i == 0)
  119.                 return false;
  120.         return true;
  121.     }
  122.     public void printHashTable ()
  123.     {
  124.         System.out.println();
  125.         for (int i = 0; i < table.length; i++)
  126.         {
  127.             System.out.print ("Bucket " + i + ":  ");             
  128.             SLLNode start = table[i];
  129.             while(start != null)
  130.             {
  131.                 System.out.print(start.data +" ");
  132.                 start = start.next;
  133.             }
  134.             System.out.println();
  135.         }
  136.     }   
  137. }
  138.  
  139. /* Class HashTableChainingSinglyLinkedListTest */
  140. public class HashTableChainingSinglyLinkedListTest
  141. { 
  142.     public static void main(String[] args) 
  143.     {
  144.         Scanner scan = new Scanner(System.in);
  145.         System.out.println("Hash Table Test\n\n");
  146.         System.out.println("Enter size"); 
  147.         /* Make object of HashTableChainingSinglyLinkedList */
  148.         HashTableChainingSinglyLinkedList htcsll = new HashTableChainingSinglyLinkedList(scan.nextInt() );
  149.  
  150.         char ch;
  151.         /*  Perform HashTableChainingSinglyLinkedList operations  */
  152.         do    
  153.         {
  154.             System.out.println("\nHash Table Operations\n");
  155.             System.out.println("1. insert ");
  156.             System.out.println("2. remove");
  157.             System.out.println("3. clear");
  158.             System.out.println("4. size"); 
  159.             System.out.println("5. check empty");
  160.  
  161.             int choice = scan.nextInt();            
  162.             switch (choice)
  163.             {
  164.             case 1 : 
  165.                 System.out.println("Enter integer element to insert");
  166.                 htcsll.insert( scan.nextInt() ); 
  167.                 break;                          
  168.             case 2 :                 
  169.                 System.out.println("Enter integer element to delete");
  170.                 htcsll.remove( scan.nextInt() ); 
  171.                 break;                        
  172.             case 3 : 
  173.                 htcsll.makeEmpty();
  174.                 System.out.println("Hash Table Cleared\n");
  175.                 break;
  176.             case 4 : 
  177.                 System.out.println("Size = "+ htcsll.getSize() );
  178.                 break; 
  179.             case 5 : 
  180.                 System.out.println("Empty status = "+ htcsll.isEmpty() );
  181.                 break;        
  182.             default : 
  183.                 System.out.println("Wrong Entry \n ");
  184.                 break;   
  185.             }
  186.             /* Display hash table */ 
  187.             htcsll.printHashTable();  
  188.  
  189.             System.out.println("\nDo you want to continue (Type y or n) \n");
  190.             ch = scan.next().charAt(0);                        
  191.         } while (ch == 'Y'|| ch == 'y');  
  192.     }
  193. }

advertisement
Hash Table Test
 
 
Enter size
5
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
4
 
Bucket 0:
Bucket 1:
Bucket 2:
Bucket 3:
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
7
 
Bucket 0:
Bucket 1:
Bucket 2:  7
Bucket 3:
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
2
 
Bucket 0:
Bucket 1:
Bucket 2:  2 7
Bucket 3:
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
8
 
Bucket 0:
Bucket 1:
Bucket 2:  2 7
Bucket 3:  8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
1
 
Bucket 0:
Bucket 1:  1
Bucket 2:  2 7
Bucket 3:  8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
5
 
Bucket 0:  5
Bucket 1:  1
Bucket 2:  2 7
Bucket 3:  8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
15
 
Bucket 0:  15 5
Bucket 1:  1
Bucket 2:  2 7
Bucket 3:  8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
32
 
Bucket 0:  15 5
Bucket 1:  1
Bucket 2:  32 2 7
Bucket 3:  8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
77
 
Bucket 0:  15 5
Bucket 1:  1
Bucket 2:  77 32 2 7
Bucket 3:  8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
1
Enter integer element to insert
68
 
Bucket 0:  15 5
Bucket 1:  1
Bucket 2:  77 32 2 7
Bucket 3:  68 8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
4
Size = 10
 
Bucket 0:  15 5
Bucket 1:  1
Bucket 2:  77 32 2 7
Bucket 3:  68 8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
2
Enter integer element to delete
32
 
Bucket 0:  15 5
Bucket 1:  1
Bucket 2:  77 2 7
Bucket 3:  68 8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
2
Enter integer element to delete
2
 
Bucket 0:  15 5
Bucket 1:  1
Bucket 2:  77 7
Bucket 3:  68 8
Bucket 4:  4
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
3
Hash Table Cleared
 
 
Bucket 0:
Bucket 1:
Bucket 2:
Bucket 3:
Bucket 4:
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. clear
4. size
5. check empty
5
Empty status = true
 
Bucket 0:
Bucket 1:
Bucket 2:
Bucket 3:
Bucket 4:
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter