Using the hashtbale code provided below create a program that makes a registry for student records. Create a class that keeps students info (name, student ID, and grade). If must do the following.
It must be a persistent record, so the registry should be saved on file when exiting, and after any major changes.
It should give an option to make an new entry with the students name, ID, and grade.
It should give an option to lookup a student from their ID (this will ke the key in the hash table).
It should give an option to remove an entry by providing the student ID.
Lastly an option to print the whole registry sorted by ID.
HashTable.java
public interface HashTable<K,V> {
public void add(K key, V value);
public V remove(K key);
public V lookup(K key);
public Object[] getValuesList();
public V[] getSortedList(V[] list);
public void printReport();
}
Hashtbl.java
import java.util.*;
public class Hashtbl<K, V> implements HashTable<K, V> {
ArrayList<HashNode<K, V>> bucket = new ArrayList<>();
int numBuckets = 10;
int size;
public Hashtbl() {
for (int i = 0; i < numBuckets; i++) {
bucket.add(null);
}
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public int additiveHashing(char[] key, int numBuckets) {
int hash = 0;
for (char c : key) {
hash += c;
}
return hash % numBuckets;
}
public int xorHashing(char[] key, int numBuckets) {
int hash = 0;
for (char c : key) {
hash ^= c;
}
return hash % numBuckets;
}
public int xorShiftHashing(char[] key, int numBuckets){
int hash = 0;
for(char c : key){
hash += (c << 3) ^ (c >> 5) ^ hash;
}
hash = Math.abs(hash);
return hash % numBuckets;
}
public void add(K key, V value) {
String a = key.toString();
char[] b = a.toCharArray();
//int index = additiveHashing(b, numBuckets);
//int index = xorHashing(b, numBuckets);
int index = xorShiftHashing(b, numBuckets);
HashNode<K, V> head = bucket.get(index);
HashNode<K, V> toAdd = new HashNode<>(key, value);
if (head == null) {
bucket.set(index, toAdd);
size++;
} else {
while (head != null) {
if (head.key.equals(key)) {
head.value = value;
// size++; No need to increase the size, as the key is already present in the table
break;
}
head = head.next;
}
if (head == null) {
head = bucket.get(index);
toAdd.next = head;
bucket.set(index, toAdd);
size++;
}
}
// Resizing logic
if ((1.0 * size) / numBuckets > 0.7) {
// do something
ArrayList<HashNode<K, V>> tmp = bucket;
bucket = new ArrayList<>();
numBuckets = 2 * numBuckets;
for (int i = 0; i < numBuckets; i++) {
bucket.add(null);
}
for (HashNode<K, V> headNode : tmp) {
while (headNode != null) {
add(headNode.key, headNode.value);
headNode = headNode.next;
}
}
}
}
public V remove(K key) {
String a = key.toString();
char[] b = a.toCharArray();
//int index = additiveHashing(b, numBuckets);
//int index = xorHashing(b, numBuckets);
int index = xorShiftHashing(b, numBuckets);
HashNode<K, V> head = bucket.get(index);
if (head == null) {
return null;
}
if (head.key.equals(key)) {
V val = head.value;
head = head.next;
bucket.set(index, head);
size–;
return val;
} else {
HashNode<K, V> prev = null;
while (head != null) {
if (head.key.equals(key)) {
prev.next = head.next;
size–;
return head.value;
}
prev = head;
head = head.next;
}
size–;
return null;
}
}
public V lookup(K key) {
String a = key.toString();
char[] b = a.toCharArray();
//int index = additiveHashing(b, numBuckets);
//int index = xorHashing(b, numBuckets);
int index = xorShiftHashing(b, numBuckets);
HashNode<K, V> head = bucket.get(index);
while (head != null) {
if (head.key.equals(key)) {
return head.value;
}
head = head.next;
}
return null;
}
public String scrambleString(String k){
char key[] = k.toCharArray();
Stack stack = new Stack();
Queue<Stack> queue = new LinkedList<Stack>();
//storing
for(int i=0;i<key.length/3;i++){
stack.push(key[i*3]);
stack.push(key[i*3+1]);
stack.push(key[i*3+2]);
queue.add(stack);
stack = new Stack();
}
if(key.length%3==2){
stack = new Stack();
int pos = key.length-2;
stack.push(key[pos]);
stack.push(key[pos+1]);
queue.add(stack);
}
System.out.println(“Queue size:”+queue.size());
//retrieving and scrambling
int i=0;
while(!queue.isEmpty()){
stack = (Stack)queue.poll();
key[i++] = (char)stack.pop();
key[i++] = (char)stack.pop();
if(!stack.empty())
key[i++] = (char)stack.pop();
}
String a = new String(key);
return a;
}
public static void main(String[] args) {
Hashtbl<String, Integer> map = new Hashtbl<String, Integer>();
System.out.println(“Scrambled String: ” +map.scrambleString(“Joshua”) );
map.add(“this”, 1);
map.add(“blah”, 2);
map.add(“please”, 3);
map.add(“array”, 3);
map.add(“Java”, 5);
map.add(“Hi”, 5);
map.add(“WiFi”, 5);
map.printReport();
System.out.println(“Trying to find value of key “this”: ” + map.lookup(“this”));
System.out.println(“Values: ” + Arrays.toString(map.getValuesList()));
}
@Override
public Object[] getValuesList() {
// we have got total size elements
Object result[] = new Object[size];
int count=0;
for (int index = 0; index < numBuckets; index++) {
HashNode<K, V> head = bucket.get(index);
while (head != null) {
result[count++] = head.value;
head = head.next;
}
}
return result;
}
@Override
public V[] getSortedList(V[] list) {
Arrays.sort(list);
return list;
}
@Override
public void printReport() {
int usedBuckets = 0;
int longestBucket = 0;
int totalBucketLen = 0;
System.out.println(“n+++++++++++++++++ Printing HashTable ++++++++++++n”);
for (int index = 0; index < numBuckets; index++) {
System.out.print(“Index ” + index + “: “);
HashNode<K, V> head = bucket.get(index);
int bucketLen = 0;
if(head != null) {
usedBuckets++;
}
while (head != null) {
System.out.print(head.key + “(” + head.value + “)” + ” => “);
head = head.next;
bucketLen++;
}
System.out.println();
if(bucketLen > longestBucket) {
longestBucket = bucketLen;
}
totalBucketLen += bucketLen;
}
System.out.println(“++++++++++++++++++++++++++++++++++++++++++++++++++++”);
System.out.println(“Load factor: ” + (1.0 * usedBuckets / numBuckets) + “n”
+ “Longest Chain: ” + longestBucket + ” collisions” + “n”
+ “Density Factor: ” + (1.0 * size/numBuckets) + “n”
+ “Chaining Factor: ” + (1.0 * totalBucketLen / numBuckets));
}
}
HashNode.java
class HashNode<K, V> {
K key;
V value;
HashNode<K, V> next = null;
public HashNode(K key, V value) {
this.key = key;
this.value = value;
}
}
Edit: This code must be what is used in the main program to create the data structure/registry which stores the student information. The main method which is in HshTbl can be commented out/ignored, the main program should be written in another class.