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
119
120
121
122
| package com.chung;
import java.util.ArrayList;
public class LinearProbing {
String[] hashTable;
int noOfCellsUsedInHashTable;
// Constructor
LinearProbing(){
hashTable = new String[13];
noOfCellsUsedInHashTable = 0;
}
// Hash function to be used on keys
public int simpleASCIIHashFunction(String x, int M){
char ch[];
ch = x.toCharArray();
int i, sum;
for(sum =0, i = 0; i < x.length(); i++){
sum = sum + ch[i];
}
return sum % M;
}
// Returns LoadFactor of HashTable
public double getLoadFactor(){
double loadFactor = noOfCellsUsedInHashTable * 1.0 / hashTable.length;
return loadFactor;
}
// Insert key in hash table
public void insertKeyInHashTable(String value){
double loadFactor= getLoadFactor();
if(loadFactor >= 0.75){
rehashKeys(value);
} else {
System.out.println("Inserting \"" + value + "\" in HashTable...");
int index = simpleASCIIHashFunction(value, hashTable.length);
for(int i = index; i < index+ hashTable.length; i++){
int newIndex = i % hashTable.length;
if(hashTable[newIndex] == null){
hashTable[newIndex] = value;
System.out.println("Successfully insert the value on the index " + newIndex);
break;
} else{
System.out.println("Failed to insert the value on the index " + newIndex);
}
}
}
noOfCellsUsedInHashTable++;
}
// Create a new HashTable and Rehashing
public void rehashKeys(String newStringToBeInserted){
noOfCellsUsedInHashTable = 0;
ArrayList<String> data = new ArrayList<String>();
for(String s : hashTable){
if(s != null){
data.add(s);
}
}
data.add(newStringToBeInserted);
hashTable = new String[hashTable.length * 2];
for(String s : data){
insertKeyInHashTable(s);
}
}
// Search for a given key in Hash Table
public boolean searchKeyInHashTable(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("The key is found on the index of " + newIndex);
return true;
}
}
System.out.println("Not Found");
return false;
}
// Delete Key from HashTable
public void deleteKeyInHashTable(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 you want");
return;
}
}
System.out.println("Failed to delete the key");
}
// Display the Hash Table
public void displayHashTable(){
if(hashTable == null){
System.out.println("No hashTable");
return;
}
for(int i = 0; i < hashTable.length; i++){
System.out.println(hashTable[i] + "\n");
}
}
// Deletes entire Hash table
public void deleteEntireHashTable(){
if(hashTable == null){
System.out.println("No hash table!! Check again!!");
return;
}
hashTable = null;
System.out.println("Completely deleted!");
}
}
|