Instructions
Objective
Write a java assignment program to work with various functions in hash table.
Requirements and Specifications
Summary
This project will require you to create a program to input, remove, and display items in a hash table, as well as search and resize the table.
The purpose of this project is to demonstrate a working knowledge of:
- Hash tables
- Hash functions
- Add and remove hash entries
- Search a hash table
- Resize a hash table
main() method
The main method will first need to collect data to create the hash table:
Enter table size:
Enter initial hash value:
Enter hash multiplier:
Enter relative prime value:
These values will be used to initialize your hash table. The main function will then display a menu:
- Search String
- Add String
- Remove String
- Display Table
- Resize Table
Q. Quit
Choice:
The user will enter one of the options (1,2,3,4,5,Q). If any other character is entered, the menu should redisplay. Once the choice is entered the program will perform the action. Options 1, 2, and 3 should prompt for an additional string:
Source Code
public class StringHash {
private final int initialValue;
private final int hashMultiplier;
private final int relativePrime;
private String[] table;
private boolean[] removed;
public StringHash(int size, int initialValue, int hashMultiplier, int relativePrime) {
table = new String[size];
removed = new boolean[size];
this.initialValue = initialValue;
this.hashMultiplier = hashMultiplier;
this.relativePrime = relativePrime;
}
public boolean contains(String data) {
return contains(data, true);
}
private boolean contains(String data, boolean printEnabled) {
int size = table.length;
StringBuilder line = new StringBuilder("Searching \"" + data + "\"");
for (int i = 0; i < size; i++) {
int index = calculateIndex(data, i);
line.append(" -> ").append(index);
if (table[index] != null && table[index].equals(data)) {
if (printEnabled) {
System.out.println(line);
}
return true;
} else if (table[index] == null && !removed[index]) {
if (printEnabled) {
System.out.println(line + " -> FAILED");
}
return false;
}
}
if (printEnabled) {
System.out.println(line + " -> FAILED");
}
return false;
}
public boolean add(String data) {
return add(data, true);
}
private boolean add(String data, boolean printEnabled) {
if (contains(data, false)) {
return false;
}
int size = table.length;
StringBuilder line = new StringBuilder();
if (printEnabled) {
line.append("Adding \"").append(data).append("\"");
}
for (int i = 0; i int index = calculateIndex(data, i);
line.append(" -> ").append(index);
if (table[index] == null) {
System.out.println(line);
table[index] = data;
removed[index] = false;
return true;
}
}
System.out.println(line + " -> FAILED");
return false;
}
public boolean remove(String data) {
if (!contains(data, false)) {
return false;
}
int size = table.length;
StringBuilder line = new StringBuilder();
line.append("Removing \"").append(data).append("\"");
for (int i = 0; i int index = calculateIndex(data, i);
line.append(" -> ").append(index);
if (table[index] == null && !removed[index]) {
System.out.println(line + " -> FAILED");
return false;
}
if (table[index] != null && table[index].equals(data)) {
table[index] = null;
removed[index] = true;
System.out.println(line);
return true;
}
}
System.out.println(line + " -> FAILED");
return false;
}
public void displayTable() {
int size = table.length;
for (int i = 0; i String line = i + " : ";
if (table[i] != null) {
line += table[i];
}
else if (removed[i]) {
line += "";
}
else {
line += "";
}
System.out.println(line);
}
}
public void resize() {
int oldSize = table.length;
String[] oldTable = table;
int newSize = 2 * oldSize;
table = new String[newSize];
removed = new boolean[newSize];
for (int i = 0; i if (oldTable[i] != null) {
System.out.print("Rehashing \"" + oldTable[i] + "\"");
add(oldTable[i], false);
}
}
}
private int calculateIndex(String s, int i) {
int size = table.length;
return (hash1(s) + i * hash2(s)) % size;
}
private int hash1(String s) {
return hash(s);
}
private int hash2(String s) {
return relativePrime - (hash(s) % relativePrime);
}
private int hash(String s) {
int size = table.length;
int result = initialValue;
for (char c : s.toCharArray()) {
result = hashMultiplier * result + c;
}
return result >= 0 ? (result % size) : (-result % size);
}
}