Question

To implement a HashTable class in C++ that allows:

- the definition of the size (M) of the static array for the hash table

- the definition of a hash function HASH(X) suitable for storing string keys (not integers). The student is expected to propose his/her own hash table.

- a method for inserting keys in the hash table. The solution MUST consider chaining (e.g. linked lists, trees, etc.) as the collision response criteria.

- a method for searching keys in the hash table. The solution has also to determine how many comparisons were necessary to find a given key or to decide that the given is absent.

- a method for deleting keys from the hash table.

- The resulting program should insert 10,000 distinct keys in the table and then present a report of the total number of collisions that occurred in the process.

- the resulting program should search 1,000 distinct keys and determine the average number of comparisons while finding these keys

- the resulting program should delete 1,000 distinct keys

- insertions, searches and deletions should occur at random times (meaning not to perform them as sequences).

Answer 1

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package printerjob;

import java.util.Hashtable;
import java.util.Scanner;
import java.util.Set;

/**
*
* @author Harsh
*/
public class HashFunctionDemo {
    // return index of hashtable
    static int collisioncount;
    static int HashFunction(String str,int MAX){
        int index=(str.length()*3)%MAX;// function for hash
       return index;
    }
static boolean ExistElement (Hashtable<Integer,String> hashtable,String str){
     Set<Integer> keys = hashtable.keySet();//print all key and value from hashtable
        for(Integer key: keys){
            if(hashtable.get(key).equals(str))
                return false;
          
        }
        return true;// return true if not exist
   
}

static void SearchinHashtable (Hashtable<Integer,String> hashtable,String str){
     Set<Integer> keys = hashtable.keySet();//print all key and value from hashtable
     int f=0,com=0;
        for(Integer key: keys){
            com++;
            if(hashtable.get(key).equals(str))
                System.out.println("Total Comparison required for searching:"+com);
            f=1;
            break;
          
        }
        if(f==1){
            System.out.println("Not Found in Hashtable");
             System.out.println("Total Comparison required for searching:"+com);
        }
     
}
    public static void main(String[] args) {
        Hashtable<Integer,String> hashtable=new Hashtable<>();
        Scanner scanner=new Scanner(System.in);
        String ch;
        int MAX=10;
        for(int i=0;i<MAX;i++){
            hashtable.put(i, "empty");//insert empty intially
        }
        do{
            System.out.println("1.Insert String 2.Search String 3. Deletion");
            int cho=(int)((Math.random()*10)%3);
            cho++;
            switch(cho){
                case 1:
                    System.out.println("Enter String");
            String str=scanner.next();//accept string
            boolean re=ExistElement(hashtable,str);
            if(re==true){
            int index=HashFunction(str,MAX);
            if(hashtable.get(index).equals("empty")){// insert 1st time
                hashtable.replace(index, str);// replace string
            }
            else{// if collision is there
                System.out.println("Collision Occure");
                collisioncount++;
                for(int i=index+1;i<MAX;i++){
                if(hashtable.get(i).equals("empty")){
                    hashtable.replace(i, str);// replace string
                    System.out.println("Inserted at Location "+i);
                    break;
                }
                collisioncount++;
                System.out.println("Collision Occure again for next");
               }
              
            }
            }
            else{
                System.out.println("Element Alredy Exist try with unique element");
            }
                    break;
                case 2:
                    System.out.println("Enter String to be search");
                    str=scanner.next();//accept string
                    SearchinHashtable(hashtable,str);
                    break;
                case 3:
                    for(int i=0;i<MAX;i++){
                          hashtable.put(i, "empty");//delelte all string
                    }
                    System.out.println("Deleted all String");
                    break;
            }
          
          
            System.out.println("Do you want to continue yes/no");
            ch=scanner.next();
          
        }while(ch.equals("yes") || ch.equals("Yes"));
        Set<Integer> keys = hashtable.keySet();//print all key and value from hashtable
        for(Integer key: keys){
            System.out.println(""+key+" :: "+hashtable.get(key));
        }
        System.out.println("Total collisioncount:"+collisioncount);
    }
  
}

/*

output

1.Insert String 2.Search String 3. Deletion
Enter String to be search
bhushan
Not Found in Hashtable
Total Comparison required for searching:1
Do you want to continue yes/no
yes
1.Insert String 2.Search String 3. Deletion
Enter String to be insert
bhushan
Do you want to continue yes/no
yes
1.Insert String 2.Search String 3. Deletion
Enter String to be search
mahajan
Not Found in Hashtable
Total Comparison required for searching:1
Do you want to continue yes/no
yes
1.Insert String 2.Search String 3. Deletion
Enter String to be search
mahajan
Not Found in Hashtable
Total Comparison required for searching:1
Do you want to continue yes/no
yes
1.Insert String 2.Search String 3. Deletion
Enter String to be search
bhuh
Not Found in Hashtable
Total Comparison required for searching:1
Do you want to continue yes/no
yes
1.Insert String 2.Search String 3. Deletion
Deleted all String
Do you want to continue yes/no
yes
1.Insert String 2.Search String 3. Deletion
Deleted all String
Do you want to continue yes/no
no
9 :: empty
8 :: empty
7 :: empty
6 :: empty
5 :: empty
4 :: empty
3 :: empty
2 :: empty
1 :: empty
0 :: empty
Total collisioncount:0

*/