This is for a Java program You are to implement 2 different hash tables, with di
ID: 3845948 • Letter: T
Question
This is for a Java program
You are to implement 2 different hash tables, with different hashing functions. All of them should implement the following interface:
public interface HashTable {
public void add(String key, V value);
public V remove(String key);
public V lookup(String key);
public Object[] getValuesList();
public void printReport();
}
The printReport() method should print to the console the following statistics:
The Load Factor, that is, the ratio of used to total number of buckets.
The longest chain in the table, that is, the maximum number of collisions for a particular bucket.
The Density Factor, that is, the ratio of elements stored elements to total number of buckets.
The Chanining Factor, that is, the average length of any chain in the table.
The 2 types of hashing functions you are to implement are:
Additive Hashing
XOR-Shift (Rotational) Hashing
The hash tables should implement resizing and rehashing. The V[] getSortedList(V[] list) method should return a sorted list with all the elements in the array.
This is for a JAVA PROGRAM also required to use interface also needs to be a String.
public class addHash, V> implements HashTable{
@Override
public void add(String key, V value) {
// TODO Auto-generated method stub
}
@Override
public V remove(String key) {
// TODO Auto-generated method stub
return null;
}
@Override
public V lookup(String key) {
// TODO Auto-generated method stub
return null;
}
@Override
public Object[] getValuesList() {
// TODO Auto-generated method stub
return null;
}
@Override
public void printReport() {
// TODO Auto-generated method stub
}
public V[] getSortedList(V[] list){
}
Explanation / Answer
Hi Below is your code, I have added code for both additive and rational hashing. Right now my code is running with xorShiftHashing, If you want to run the xorHashing or addititve hashing, uncomment the line for getting index via rational hashing and comment the line for getting index via additive hashing/xorHashing in add,remove and lookup methods...
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;
}
}
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();
}
addHash.java
import java.util.*;
public class addHash<K, V> implements HashTable<K, V> {
ArrayList<HashNode<K, V>> bucket = new ArrayList<>();
int numBuckets = 10;
int size;
public addHash() {
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) {
addHash<String, Integer> map = new addHash<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(" +++++++++++++++++ Printing HashTable ++++++++++++ ");
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) + " " + "Longest Chain: " + longestBucket
+ " collisions" + " " + "Density Factor: " + (1.0 * size / numBuckets) + " " + "Chaining Factor: "
+ (1.0 * totalBucketLen / numBuckets));
}
}
Sample Output: -
Queue size:2
Scrambled String: soJauh
+++++++++++++++++ Printing HashTable ++++++++++++
Index 0:
Index 1: please(3) =>
Index 2:
Index 3: Hi(5) => Java(5) => array(3) =>
Index 4:
Index 5: this(1) =>
Index 6:
Index 7: WiFi(5) =>
Index 8:
Index 9: blah(2) =>
++++++++++++++++++++++++++++++++++++++++++++++++++++
Load factor: 0.5
Longest Chain: 3 collisions
Density Factor: 0.7
Chaining Factor: 0.7
Trying to find value of key "this": 1
Values: [3, 5, 5, 3, 1, 5, 2]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.