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