Java Program to Implement Hash Tables Chaining with List Heads

«
»
This is a Java Program to implement hash tables chaining with List Heads. 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. Some chaining implementations store the first record of each chain in the slot array itself. The number of pointer traversals is decreased by one for most cases. The purpose is to increase cache efficiency of hash table access.
The disadvantage is that an empty bucket takes the same space as a bucket with one entry. To save memory space, such hash tables often have about as many slots as stored entries, meaning that many slots have two or more entries.

Here is the source code of the Java program to implement hash tables chaining with List Heads. 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 List Heads
  3.  */ 
  4. import java.util.Scanner;
  5.  
  6. /* Class LinkedHashEntry */
  7. class LinkedHashEntry 
  8. {
  9.     String key;
  10.     int value;
  11.     LinkedHashEntry next;
  12.  
  13.     /* Constructor */
  14.     LinkedHashEntry(String key, int value) 
  15.     {
  16.         this.key = key;
  17.         this.value = value;
  18.         this.next = null;
  19.     }
  20. }
  21.  
  22. /* Class HashTable */
  23. class HashTable
  24. {
  25.     private int TABLE_SIZE;
  26.     private int size; 
  27.     private LinkedHashEntry[] table;
  28.  
  29.      /* Constructor */
  30.     public HashTable(int ts) 
  31.     {
  32.         size = 0;
  33.         TABLE_SIZE = ts;
  34.         table = new LinkedHashEntry[TABLE_SIZE];
  35.         for (int i = 0; i < TABLE_SIZE; i++)
  36.             table[i] = null;
  37.     } 
  38.     /* Function to get number of key-value pairs */
  39.     public int getSize()
  40.     {
  41.         return size;
  42.     }
  43.     /* Function to clear hash table */
  44.     public void makeEmpty()
  45.     {
  46.         for (int i = 0; i < TABLE_SIZE; i++)
  47.             table[i] = null;
  48.     }
  49.     /* Function to get value of a key */
  50.     public int get(String key) 
  51.     {
  52.         int hash = (myhash( key ) % TABLE_SIZE);
  53.         if (table[hash] == null)
  54.             return -1;
  55.         else 
  56.         {
  57.             LinkedHashEntry entry = table[hash];
  58.             while (entry != null && !entry.key.equals(key))
  59.                 entry = entry.next;
  60.             if (entry == null)
  61.                 return -1;
  62.             else
  63.                 return entry.value;
  64.         }
  65.     }
  66.     /* Function to insert a key value pair */
  67.     public void insert(String key, int value) 
  68.     {
  69.         int hash = (myhash( key ) % TABLE_SIZE);
  70.         if (table[hash] == null)
  71.             table[hash] = new LinkedHashEntry(key, value);
  72.         else 
  73.         {
  74.             LinkedHashEntry entry = table[hash];
  75.             while (entry.next != null && !entry.key.equals(key))
  76.                 entry = entry.next;
  77.             if (entry.key.equals(key))
  78.                 entry.value = value;
  79.             else
  80.                 entry.next = new LinkedHashEntry(key, value);
  81.         }
  82.         size++;
  83.     }
  84.  
  85.     public void remove(String key) 
  86.     {
  87.         int hash = (myhash( key ) % TABLE_SIZE);
  88.         if (table[hash] != null) 
  89.         {
  90.             LinkedHashEntry prevEntry = null;
  91.             LinkedHashEntry entry = table[hash];
  92.             while (entry.next != null && !entry.key.equals(key)) 
  93.             {
  94.                 prevEntry = entry;
  95.                 entry = entry.next;
  96.             }
  97.             if (entry.key.equals(key)) 
  98.             {
  99.                 if (prevEntry == null)
  100.                     table[hash] = entry.next;
  101.                 else
  102.                     prevEntry.next = entry.next;
  103.                 size--;
  104.             }
  105.         }
  106.     }
  107.     /* Function myhash which gives a hash value for a given string */
  108.     private int myhash(String x )
  109.     {
  110.         int hashVal = x.hashCode( );
  111.         hashVal %= TABLE_SIZE;
  112.         if (hashVal < 0)
  113.             hashVal += TABLE_SIZE;
  114.         return hashVal;
  115.     }
  116.     /* Function to print hash table */
  117.     public void printHashTable()
  118.     {
  119.         for (int i = 0; i < TABLE_SIZE; i++)
  120.         {
  121.             System.out.print("\nBucket "+ (i + 1) +" : ");
  122.             LinkedHashEntry entry = table[i];
  123.             while (entry != null)
  124.             {
  125.                 System.out.print(entry.value +" ");
  126.                 entry = entry.next;
  127.             }            
  128.         }
  129.     }
  130. }
  131.  
  132. /* Class HashTablesChainingListHeadsTest */
  133. public class HashTablesChainingListHeadsTest
  134. {
  135.     public static void main(String[] args)
  136.     {
  137.         Scanner scan = new Scanner(System.in);
  138.         System.out.println("Hash Table Test\n\n");
  139.         System.out.println("Enter size");
  140.         /* Make object of HashTable */
  141.         HashTable ht = new HashTable(scan.nextInt() );
  142.  
  143.         char ch;
  144.         /*  Perform HashTable operations  */
  145.         do    
  146.         {
  147.             System.out.println("\nHash Table Operations\n");
  148.             System.out.println("1. insert ");
  149.             System.out.println("2. remove");
  150.             System.out.println("3. get");            
  151.             System.out.println("4. clear");
  152.             System.out.println("5. size");
  153.  
  154.             int choice = scan.nextInt();            
  155.             switch (choice)
  156.             {
  157.             case 1 : 
  158.                 System.out.println("Enter key and value");
  159.                 ht.insert(scan.next(), scan.nextInt() ); 
  160.                 break;                          
  161.             case 2 :                 
  162.                 System.out.println("Enter key");
  163.                 ht.remove( scan.next() ); 
  164.                 break;                        
  165.             case 3 : 
  166.                 System.out.println("Enter key");
  167.                 System.out.println("Value = "+ ht.get( scan.next() )); 
  168.                 break;                                   
  169.             case 4 : 
  170.                 ht.makeEmpty();
  171.                 System.out.println("Hash Table Cleared\n");
  172.                 break;
  173.             case 5 : 
  174.                 System.out.println("Size = "+ ht.getSize() );
  175.                 break;         
  176.             default : 
  177.                 System.out.println("Wrong Entry \n ");
  178.                 break;   
  179.             }
  180.             /* Display hash table */
  181.             ht.printHashTable();  
  182.  
  183.             System.out.println("\nDo you want to continue (Type y or n) \n");
  184.             ch = scan.next().charAt(0);                        
  185.         } while (ch == 'Y'|| ch == 'y');  
  186.     }
  187. }

advertisement
Hash Table Test
 
 
Enter size
5
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
1
Enter key and value
water 100
 
Bucket 1 :
Bucket 2 :
Bucket 3 : 100
Bucket 4 :
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
1
Enter key and value
apple 5
 
Bucket 1 : 5
Bucket 2 :
Bucket 3 : 100
Bucket 4 :
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
1
Enter key and value
mango 24
 
Bucket 1 : 5 24
Bucket 2 :
Bucket 3 : 100
Bucket 4 :
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
1
Enter key and value
guava 13
 
Bucket 1 : 5 24
Bucket 2 :
Bucket 3 : 100 13
Bucket 4 :
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
1
Enter key and value
pineapple 17
 
Bucket 1 : 5 24
Bucket 2 : 17
Bucket 3 : 100 13
Bucket 4 :
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
1
Enter key and value
strawberry 37
 
Bucket 1 : 5 24
Bucket 2 : 17
Bucket 3 : 100 13
Bucket 4 : 37
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
3
Enter key
apple
Value = 5
 
Bucket 1 : 5 24
Bucket 2 : 17
Bucket 3 : 100 13
Bucket 4 : 37
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
3
Enter key
mango
Value = 24
 
Bucket 1 : 5 24
Bucket 2 : 17
Bucket 3 : 100 13
Bucket 4 : 37
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
2
Enter key
guava
 
Bucket 1 : 5 24
Bucket 2 : 17
Bucket 3 : 100
Bucket 4 : 37
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
5
Size = 5
 
Bucket 1 : 5 24
Bucket 2 : 17
Bucket 3 : 100
Bucket 4 : 37
Bucket 5 :
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. get
4. clear
5. size
4
Hash Table Cleared
 
 
Bucket 1 :
Bucket 2 :
Bucket 3 :
Bucket 4 :
Bucket 5 :
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.