Hashing - Quadratic Probing

QuadraticProbing.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package com.chung;

import java.util.ArrayList;

public class QuadraticProbing {

     String[] hashTable;
     int noOfCellUsedInHashTable;

     QuadraticProbing(){
         hashTable = new String[13];
         noOfCellUsedInHashTable = 0;
     }

     // Hash Function to be used on keys
    public int simpleASCIIHashFunction(String x, int M){
         char ch[];
         ch = x.toCharArray();
         int sum, i;
         for(i = 0, sum = 0; i < ch.length; i++){
             sum += ch[i];
         }
         return sum % M;
    }

    // Returns load factor of Hash Table
    public double getLoadFactor(){
         double loadFactor = noOfCellUsedInHashTable * 1.0 / hashTable.length;
         return loadFactor;
    }

    // Insert Key in Hash Table
    public void insertKeyInHashTable(String value){
         double loadFactor = getLoadFactor();
         if(loadFactor >= 0.75){
             System.out.println("The hash table is full. Rehash the table");
             rehashing(value);
         } else {
             System.out.println("Inserting key in Hash Table");
             int index = simpleASCIIHashFunction(value, hashTable.length);
             int counter = 0;
             for(int i = index; i < index + hashTable.length; i++){
                 int newIndex = (index + (counter*counter)) % hashTable.length;
                 if(hashTable[newIndex] == null){
                     hashTable[newIndex] = value;
                     break;
                 } else {
                     System.out.println("Index is not blank");
                 }
                 counter++;
             }
         }
         noOfCellUsedInHashTable++;
    }


    // Create a new Hash Table and Rehashing
    public void rehashing(String newString){
        noOfCellUsedInHashTable = 0;
        ArrayList<String> data = new ArrayList<String>();
        for(String s : hashTable){
            if(s != null)
                data.add(s);
        }
        data.add(newString);
        hashTable = new String[hashTable.length *2];
        for(String s : data){
            insertKeyInHashTable(s);
        }
    }

    // Search for a given key in Hash Table
    public boolean searchKeyOnHashTable(String key){

         int index = simpleASCIIHashFunction(key, hashTable.length);
         for(int i = index; i < index + hashTable.length; i++){
             int newIndex = i % hashTable.length;
             if(hashTable[newIndex] != null && hashTable[newIndex].equals(key)){
                 System.out.println("Found the key!!");
                 return true;
             }
         }
         System.out.println("Cannot find the key");
         return false;
    }

    // Delete Key From Hash Table
    public void deleteKeyFromHashTable(String key){
         int index = simpleASCIIHashFunction(key, hashTable.length);

         for(int i = index; i < index + hashTable.length; i++){
             int newIndex = i % hashTable.length;
             if(hashTable[newIndex] != null && hashTable[newIndex].equals(key)){
                 hashTable[newIndex] = null;
                 System.out.println("Delete the key");
                 return;
             }
         }
         System.out.println("Cannot find the key");
    }

    // Display the hash table
    public void displayTheHashTable(){
         if(hashTable == null){
             System.out.println("HashTable is not exist");
         } else{
             for(int i = 0; i < hashTable.length; i++){
                 System.out.println(hashTable[i]);
             }
         }
    }

    // Delete Entire hash table
    public void deleteEntireHashTable(){
         hashTable = null;
        System.out.println("Hash Table is deleted");
    }
}