Program to implement Hash Tables in Java

What is Hash Table?

Hash tables are an efficient implementation of a keyed array data structure, a structure sometimes known as an associative array or map. If you’re working in C++, you can take advantage of the STL map container for keyed arrays implemented using binary trees, but this article will give you some of the theory behind how a hash tables works. To know more about Hash Tables read this.

Java Program to implement Hash Tables:

[code]

import java.util.Scanner;

class HashTable
{
int[] arr;
int capacity;

/** constructor **/
public HashTable(int capacity)
{
this.capacity = nextPrime(capacity);
arr = new int[this.capacity];
}

/** function to insert **/
public void insert(int ele)
{
arr[ele % capacity] = ele;
}

/** function to clear **/
public void clear()
{
arr = new int[capacity];
}

/** function contains **/
public boolean contains(int ele)
{
return arr[ele % capacity] == ele;
}

/** function to delete **/
public void delete(int ele)
{
if (arr[ele % capacity] == ele)
arr[ele % capacity] = 0;
else
System.out.println("\nError : Element not found\n");
}

/** 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;
}

/** function to print hash table **/
public void printTable()
{
System.out.print("\nHash Table = ");
for (int i = 0; i < capacity; i++)
System.out.print(arr[i] +" ");
System.out.println();
}
}

/** Class HashTableTest **/
public class HashTableTest
{
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. contains");
System.out.println("4. clear");

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.delete( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to check if present");
System.out.println("Contains : "+ ht.contains(scan.nextInt() ));
break;
case 4 :
ht.clear();
System.out.println("Hash Table Cleared\n");
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/** Display hash table **/
ht.printTable();

System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == ‘Y’|| ch == ‘y’);
}
}
[/code]

Sample Output:

 

Hash Table Test
 
 
Enter size
10
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
1
Enter integer element to insert
28
 
Hash Table = 0 0 0 0 0 0 28 0 0 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
1
Enter integer element to insert
24
 
Hash Table = 0 0 24 0 0 0 28 0 0 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
1
Enter integer element to insert
14
 
Hash Table = 0 0 24 14 0 0 28 0 0 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
1
Enter integer element to insert
19
 
Hash Table = 0 0 24 14 0 0 28 0 19 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
1
Enter integer element to insert
94
 
Hash Table = 0 0 24 14 0 0 94 0 19 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
1
Enter integer element to insert
17
 
Hash Table = 0 0 24 14 0 0 17 0 19 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
3
Enter integer element to check if present
94
Contains : false
 
Hash Table = 0 0 24 14 0 0 17 0 19 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
3
Enter integer element to check if present
17
Contains : true
 
Hash Table = 0 0 24 14 0 0 17 0 19 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
2
Enter integer element to delete
17
 
Hash Table = 0 0 24 14 0 0 0 0 19 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
1
Enter integer element to insert
94
 
Hash Table = 0 0 24 14 0 0 94 0 19 0 0
 
Do you want to continue (Type y or n)
 
y
 
Hash Table Operations
 
1. insert
2. remove
3. contains
4. clear
4
Hash Table Cleared
 
 
Hash Table = 0 0 0 0 0 0 0 0 0 0 0
 
Do you want to continue (Type y or n)
 
n

Leave a Comment