In Java, implement separate chaining hash table into this interface public inter
ID: 3845891 • Letter: I
Question
In Java, implement separate chaining hash table into this 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 V[] getSortedList(V[] list);
}
with these given hash functions
public int additiveHash(char[] key, int TABLE_SIZE) {
int hash = 0;
for (char c: key) {
hash += c;
}
return hash % TABLE_SIZE;
}
public int rotationalHash(char[] key, int TABLE_SIZE) {
int hash = 0;
for (char c: key) {
hash += (c << 7) ^ (c >> (TABLE_SIZE - 7)) ^ hash;
}
hash = Math.abs(hash);
return hash % TABLE_SIZE;
}
Explanation / Answer
Hi Below is your code, I have added code for both additive and rational hashing. Right now my code is running with additive hashing. If you want to run the rationalhashing, uncomment the line for getting index via rational hashing and comment the line for getting index via additive hashing in add,remove and lookup methods...
Below are the classes: -
Hashtbl.java
import java.util.*;
public class Hashtbl<K, V> implements HashTable<K, V> {
ArrayList<HashNode<K, V>> bucket = new ArrayList<>();
int TABLE_SIZE = 10;
int size;
public Hashtbl() {
for (int i = 0; i < TABLE_SIZE; i++) {
bucket.add(null);
}
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public int additiveHash(char[] key, int TABLE_SIZE) {
int hash = 0;
for (char c : key) {
hash += c;
}
return hash % TABLE_SIZE;
}
public int rotationalHash(char[] key, int TABLE_SIZE) {
int hash = 0;
for (char c : key) {
hash += (c << 7) ^ (c >> (TABLE_SIZE - 7)) ^ hash;
}
hash = Math.abs(hash);
return hash % TABLE_SIZE;
}
public void add(K key, V value) {
String a = key.toString();
char[] b = a.toCharArray();
int index = additiveHash(b, TABLE_SIZE);
//int index = rotationalHash(b, TABLE_SIZE);
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) / TABLE_SIZE > 0.7) {
// do something
ArrayList<HashNode<K, V>> tmp = bucket;
bucket = new ArrayList<>();
TABLE_SIZE = 2 * TABLE_SIZE;
for (int i = 0; i < TABLE_SIZE; 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 = additiveHash(b, TABLE_SIZE);
//int index = rotationalHash(b, TABLE_SIZE);
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 = additiveHash(b, TABLE_SIZE);
//int index = rotationalHash(b, TABLE_SIZE);
HashNode<K, V> head = bucket.get(index);
while (head != null) {
if (head.key.equals(key)) {
return head.value;
}
head = head.next;
}
return null;
}
@SuppressWarnings({ "unchecked", "rawtypes" })
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 < TABLE_SIZE; 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 < TABLE_SIZE; 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 / TABLE_SIZE) + " " + "Longest Chain: " + longestBucket
+ " collisions" + " " + "Density Factor: " + (1.0 * size / TABLE_SIZE) + " " + "Chaining Factor: "
+ (1.0 * totalBucketLen / TABLE_SIZE));
}
}
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();
}
Sample Run:
Queue size:2
Scrambled String: soJauh
+++++++++++++++++ Printing HashTable ++++++++++++
Index 0: this(1) =>
Index 1:
Index 2:
Index 3: array(3) =>
Index 4: please(3) =>
Index 5:
Index 6: Java(5) =>
Index 7: WiFi(5) => Hi(5) => blah(2) =>
Index 8:
Index 9:
++++++++++++++++++++++++++++++++++++++++++++++++++++
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: [1, 3, 3, 5, 5, 5, 2]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.