Code:
import java.util.Scanner;
/* Node for singly linked list */
class SLLNode
{
SLLNode next;
int data;
/* Constructor */
public SLLNode(int x)
{
data = x;
next = null;
}
}
/* Class HashTableChainingSinglyLinkedList */
class HashTableChainingSinglyLinkedList
{
private SLLNode[] table;
private int size ;
/* Constructor */
public HashTableChainingSinglyLinkedList(int tableSize)
{
table = new SLLNode[ 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 makeEmpty()
{
int l = table.length;
table = new SLLNode[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 = myhash(val);
SLLNode nptr = new SLLNode(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 = myhash(val);
SLLNode start = table[pos];
SLLNode 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;
}
/* Function myhash */
private int myhash(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 + ": ");
SLLNode start = table[i];
while(start != null)
{
System.out.print(start.data +" ");
start = start.next;
}
System.out.println();
}
}
}
/* Class HashTableChainingSinglyLinkedListTest */
public class HashTableChainingSinglyLinkedListTest
{
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 HashTableChainingSinglyLinkedList */
HashTableChainingSinglyLinkedList htcsll = new HashTableChainingSinglyLinkedList(scan.nextInt() );
char ch;
/* Perform HashTableChainingSinglyLinkedList 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");
htcsll.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to delete");
htcsll.remove( scan.nextInt() );
break;
case 3 :
htcsll.makeEmpty();
System.out.println("Hash Table Cleared\n");
break;
case 4 :
System.out.println("Size = "+ htcsll.getSize() );
break;
case 5 :
System.out.println("Empty status = "+ htcsll.isEmpty() );
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/* Display hash table */
htcsll.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:
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
More Java Programs:
