Answered! Use a stack and a queue to implement a scambled version of the rotational hashing function. Before applying the…

Use a stack and a queue to implement a scambled version of the rotational hashing function. Before applying the rotational hash to the string, implement a function that will scramble the characters in the string so that every 3 successive characters in the string are inverted. For example, if the string to be hashed is “Jonathan”, then the function should turn the string into “noJhtana” before applying the rotational hash. This function can be easily implemented using a stack and a queue.

Here is the code for the hash table you must use(ignore the code in main, it was just there for testing purposes):

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.ArrayList;
import java.util.Arrays;

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 static void main(String[] args) {
Hashtbl<String, Integer> map = new Hashtbl<String, Integer>();
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(“The Load factor is: ” + (1.0 * usedBuckets / numBuckets));
System.out.println(“The longest Chain in table is of ” + longestBucket + ” collisions.”);
System.out.println(“The Density Factor is: ” + (1.0 * size/numBuckets));
System.out.println(“The Chainig Factor is: ” + (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;
}
}