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.

/*
 *    Java Program to Implement Hash Tables Chaining with List Heads
 */ 
import java.util.Scanner;
 
/* Class LinkedHashEntry */
class LinkedHashEntry 
{
    String key;
    int value;
    LinkedHashEntry next;
 
    /* Constructor */
    LinkedHashEntry(String key, int value) 
    {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}
 
/* Class HashTable */
class HashTable
{
    private int TABLE_SIZE;
    private int size; 
    private LinkedHashEntry[] table;
 
     /* Constructor */
    public HashTable(int ts) 
    {
        size = 0;
        TABLE_SIZE = ts;
        table = new LinkedHashEntry[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++)
            table[i] = null;
    } 
    /* Function to get number of key-value pairs */
    public int getSize()
    {
        return size;
    }
    /* Function to clear hash table */
    public void makeEmpty()
    {
        for (int i = 0; i < TABLE_SIZE; i++)
            table[i] = null;
    }
    /* Function to get value of a key */
    public int get(String key) 
    {
        int hash = (myhash( key ) % TABLE_SIZE);
        if (table[hash] == null)
            return -1;
        else 
        {
            LinkedHashEntry entry = table[hash];
            while (entry != null && !entry.key.equals(key))
                entry = entry.next;
            if (entry == null)
                return -1;
            else
                return entry.value;
        }
    }
    /* Function to insert a key value pair */
    public void insert(String key, int value) 
    {
        int hash = (myhash( key ) % TABLE_SIZE);
        if (table[hash] == null)
            table[hash] = new LinkedHashEntry(key, value);
        else 
        {
            LinkedHashEntry entry = table[hash];
            while (entry.next != null && !entry.key.equals(key))
                entry = entry.next;
            if (entry.key.equals(key))
                entry.value = value;
            else
                entry.next = new LinkedHashEntry(key, value);
        }
        size++;
    }
 
    public void remove(String key) 
    {
        int hash = (myhash( key ) % TABLE_SIZE);
        if (table[hash] != null) 
        {
            LinkedHashEntry prevEntry = null;
            LinkedHashEntry entry = table[hash];
            while (entry.next != null && !entry.key.equals(key)) 
            {
                prevEntry = entry;
                entry = entry.next;
            }
            if (entry.key.equals(key)) 
            {
                if (prevEntry == null)
                    table[hash] = entry.next;
                else
                    prevEntry.next = entry.next;
                size--;
            }
        }
    }
    /* Function myhash which gives a hash value for a given string */
    private int myhash(String x )
    {
        int hashVal = x.hashCode( );
        hashVal %= TABLE_SIZE;
        if (hashVal < 0)
            hashVal += TABLE_SIZE;
        return hashVal;
    }
    /* Function to print hash table */
    public void printHashTable()
    {
        for (int i = 0; i < TABLE_SIZE; i++)
        {
            System.out.print("\nBucket "+ (i + 1) +" : ");
            LinkedHashEntry entry = table[i];
            while (entry != null)
            {
                System.out.print(entry.value +" ");
                entry = entry.next;
            }            
        }
    }
}
 
/* Class HashTablesChainingListHeadsTest */
public class HashTablesChainingListHeadsTest
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Hash Table Test\n\n");
        System.out.println("Enter size");
        /* Make object of HashTable */
        HashTable ht = new HashTable(scan.nextInt() );
 
        char ch;
        /*  Perform HashTable operations  */
        do    
        {
            System.out.println("\nHash Table Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. remove");
            System.out.println("3. get");            
            System.out.println("4. clear");
            System.out.println("5. size");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter key and value");
                ht.insert(scan.next(), scan.nextInt() ); 
                break;                          
            case 2 :                 
                System.out.println("Enter key");
                ht.remove( scan.next() ); 
                break;                        
            case 3 : 
                System.out.println("Enter key");
                System.out.println("Value = "+ ht.get( scan.next() )); 
                break;                                   
            case 4 : 
                ht.makeEmpty();
                System.out.println("Hash Table Cleared\n");
                break;
            case 5 : 
                System.out.println("Size = "+ ht.getSize() );
                break;         
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            /* Display hash table */
            ht.printHashTable();  
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');  
    }
}
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

Related posts:

Spring Security OAuth Login with WebFlux
Java Program to Perform the Sorting Using Counting Sort
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Spring Boot - Runners
Kết hợp Java Reflection và Java Annotations
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm
File Upload with Spring MVC
Getting Started with Custom Deserialization in Jackson
Introduction to Spliterator in Java
Spring WebClient and OAuth2 Support
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Java Program to Implement Multi-Threaded Version of Binary Search Tree
A Guide to JUnit 5 Extensions
Luồng Daemon (Daemon Thread) trong Java
Java Program to Implement Gift Wrapping Algorithm in Two Dimensions
Java Program to Implement Threaded Binary Tree
Java Program to Perform Partition of an Integer in All Possible Ways
Using Custom Banners in Spring Boot
Từ khóa throw và throws trong Java
Java Program to Implement Radix Sort
Multi Dimensional ArrayList in Java
Java Program to Implement Nth Root Algorithm
JPA/Hibernate Persistence Context
Dockerizing a Spring Boot Application
Lập trình đa luồng với CompletableFuture trong Java 8
Extract links from an HTML page
Convert String to Byte Array and Reverse in Java
Java Program to Find Minimum Element in an Array using Linear Search
Lớp LinkedHashMap trong Java
Guide To CompletableFuture
Java Program to Implement String Matching Using Vectors
Hướng dẫn Java Design Pattern – Visitor