Question

Java: Reimplement separate chaining hash tables using singly linked lists instead of using java.util.LinkedList.

Answer 1

import java.util.Scanner;

//single linked list node..
class SingleLinkedList
{
int data;
    SingleLinkedList next;
   

    //Constructor
    public SingleLinkedList(int x)
    {
        data = x;
        next = null;
    }
}

//hash table class
//hashing using chainging...
class HashTable
{
    private SingleLinkedList[] table;
    private int size ;

    /* Constructor */
    public HashTable(int tableSize)
    {
        table = new SingleLinkedList[ nextPrime(tableSize) ];
        size = 0;
    }
    /* Function to check if hash table is empty */
    public boolean isEmpty()
    {
        return size == 0;
    }
    /* Function to clear hash table */
    public void clear()
    {
        int l = table.length;
        table = new SingleLinkedList[l];
        size = 0;
    }
    /* Function to get size */
    public int getSize()
    {
        return size;
    }
    /* Function to insert an element */
    public void insert(int val)
    {
        size++;
        int pos = hash_code(val);       
        SingleLinkedList nptr = new SingleLinkedList(val);               
        if (table[pos] == null)
            table[pos] = nptr;           
        else
        {
            nptr.next = table[pos];
            table[pos] = nptr;
        }   
    }
    /* Function to remove an element */
    public void remove(int val)
    {
        int pos = hash_code(val);   
        SingleLinkedList start = table[pos];
        SingleLinkedList end = start;
        if (start.data == val)
        {
            size--;
            table[pos] = start.next;
            return;
        }
        while (end.next != null && end.next.data != val)
            end = end.next;
        if (end.next == null)
        {
            System.out.println("\nElement not found\n");
            return;
        }
        size--;
        if (end.next.next == null)
        {
            end.next = null;
            return;
        }
        end.next = end.next.next;
        table[pos] = start;
    }
//hash function
    private int hash_code(Integer x )
    {
        int hashVal = x.hashCode( );
        hashVal %= table.length;
        if (hashVal < 0)
            hashVal += table.length;
        return hashVal;
    }
    /* Function to generate next prime number >= n */
    private static int nextPrime( int n )
    {
        if (n % 2 == 0)
            n++;
        for ( ; !isPrime( n ); n += 2);

        return n;
    }
    /* Function to check if given number is prime */
    private static boolean isPrime( int n )
    {
        if (n == 2 || n == 3)
            return true;
        if (n == 1 || n % 2 == 0)
            return false;
        for (int i = 3; i * i <= n; i += 2)
            if (n % i == 0)
                return false;
        return true;
    }
    public void printHashTable ()
    {
        System.out.println();
        for (int i = 0; i < table.length; i++)
        {
            System.out.print ("Bucket " + i + ": ");            
            SingleLinkedList start = table[i];
            while(start != null)
            {
                System.out.print(start.data +" ");
                start = start.next;
            }
            System.out.println();
        }
    }  
}

//class to test hash table..
public class HashTableTest
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        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. clear");
            System.out.println("4. size");
            System.out.println("5. check empty");

            int choice = scan.nextInt();           
            switch (choice)
            {
            case 1 :
                System.out.println("Enter integer element to insert");
                ht.insert( scan.nextInt() );
                break;                         
            case 2 :                
                System.out.println("Enter integer element to delete");
                ht.remove( scan.nextInt() );
                break;                       
            case 3 :
                ht.clear();
                System.out.println("Hash Table Cleared\n");
                break;
            case 4 :
                System.out.println("Size = "+ ht.getSize() );
                break;
            case 5 :
                System.out.println("Empty status = "+ ht.isEmpty() );
                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');
    }
}

output:

run:
Enter size
10

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
Bucket 3:
Bucket 4:
Bucket 5:
Bucket 6:
Bucket 7:
Bucket 8:
Bucket 9:
Bucket 10:

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
4

Bucket 0:
Bucket 1:
Bucket 2: 2
Bucket 3:
Bucket 4: 4
Bucket 5:
Bucket 6:
Bucket 7:
Bucket 8:
Bucket 9:
Bucket 10:

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
55

Bucket 0: 55
Bucket 1:
Bucket 2: 2
Bucket 3:
Bucket 4: 4
Bucket 5:
Bucket 6:
Bucket 7:
Bucket 8:
Bucket 9:
Bucket 10:

Do you want to continue (Type y or n)

n
BUILD SUCCESSFUL (total time: 49 seconds)