Use HashTable.java and HashFunction.java from below Write a driver program and m
ID: 3816110 • Letter: U
Question
Use HashTable.java and HashFunction.java from below Write a driver program and modify the HashTable.java to build a Hash table with the specifications as follows: (a)A table size is 128 slots. (b)The input data are randomly generated UNIQUE upper case data names with eight characters in length (Each name has to be unique). (c)Use the generated name for both key and Element value (KVpair.) (d)Use the same name as the key for sfold function in HashFunction class to create the hash code for the table entry. (e)Add those data names to the table start with empty table until the table is 40% full. (f)Display the percentage of table had been occupied during the insertion.
HashTable.java import java.io.*; public class HashTable, E> { private int M; private KVpair[] HT; private int h(Key key) { return M - 1; } private int p(Key key, int slot) { return slot; } @SuppressWarnings("unchecked") // Generic array allocation HashTable(int m) { M = m; HT = (KVpair[])new KVpair[M]; } /** Insert record r with key k into HT */ void hashInsert(Key k, E r) { int home; // Home position for r int pos = home = h(k); // Initial position for (int i=1; HT[pos] != null; i++) { pos = (home + p(k, i)) % M; // Next pobe slot assert HT[pos].key().compareTo(k) != 0 : "Duplicates not allowed"; } HT[pos] = new KVpair(k, r); // Insert R } /** Search in hash table HT for the record with key k */ E hashSearch(Key k) { int home; // Home position for k int pos = home = h(k); // Initial position for (int i = 1; (HT[pos] != null) && (HT[pos].key().compareTo(k) != 0); i++) pos = (home + p(k, i)) % M; // Next probe position if (HT[pos] == null) return null; // Key not in hash table else return HT[pos].value(); // Found it } }
HashFunction.java import java.io.*; import java.math.*; public class HashFunction { int sfold(String s, int M) { int intLength = s.length() / 4; int sum = 0; for (int j = 0; j < intLength; j++) { char c[] = s.substring(j*4,(j*4)+4).toCharArray(); int mult = 1; for (int k = 0; k < c.length; k++) { sum += c[k] * mult; mult *= 256; } } char c[] = s.substring(intLength * 4).toCharArray(); int mult = 1; for (int k = 0; k < c.length; k++) { sum += c[k] * mult; mult *= 256; } return(Math.abs(sum) % M); } int h(String x, int M) { char ch[]; ch = x.toCharArray(); int xlength = x.length(); int i, sum; for (sum=0, i=0; i sum += ch[i]; return sum % M; } int h(int x) { return(x % 16); } }
Explanation / Answer
package chegg.hashing;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
public class HashTable<E> {
private int M = 0;
private int count = 0;
private KVpair[] HT;
private int loading = 0;
// Generic array allocation
public HashTable(int m) {
M = m;
HT = new KVpair[m];
}
boolean isFull() {
loading = (count * 100) / M;
return (loading >= 40) ? true : false;
}
void hashInsert(E k) {
hashInsert(k, k);
}
void hashInsert(E k, E r) {
// (e)Add those data names to the table start with empty table until the
// table is 40% full.
// Make sure the value is not null
if (r == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
KVpair[] tab = HT;
int hash = new HashFunction().sfold((String) k, M);
// int hash = hash(k);
// int index = (hash & 0x7FFFFFFF) % tab.length;
for (KVpair<E, E> e = tab[hash]; e != null; e = e.next) {
if ((e.hash == hash) && e.key.equals(k)) {
E old = e.value;
e.value = r;
return;
}
}
// Creates the new entry.
KVpair<E, E> e = tab[hash];
tab[hash] = new KVpair<>(hash, k, r, e);
count++;
}
E search(E k) {
KVpair tab[] = HT;
int home = new HashFunction().sfold((String) k, M);
int index = (home & 0x7FFFFFFF) % tab.length;
for (KVpair<E, E> e = tab[index]; e != null; e = e.next) {
if ((e.hash == home) && e.key.equals(k)) {
return e.value;
}
}
return null;
}
void printTable() {
System.out.println(" Hashtable Contents : ");
for (int indx = 0; indx < HT.length; indx++) {
System.out.println(HT[indx]);
}
}
public static void main(String[] args) {
// (a)A table size is 128 slots.
// Configure the slot size using tableSize variable and HashTable class
// constructor
int tableSize = 5;
HashTable<String> hashFunction = new HashTable<String>(tableSize);
// (b)The input data are randomly generated UNIQUE upper case data names
// with eight characters in length (Each name has to be unique).
RandomStringGenerator msr = new RandomStringGenerator();
for (int indx = 0; indx < tableSize; indx++) {
// (c)Use the generated name for both key and Element value
// (KVpair.) you can use different key and value pair, in that case
// you have
// to invoke hashInsert(E k, E v) method.
if (!hashFunction.isFull()) {
hashFunction.hashInsert(msr.getRandomString());
// (f)Display the percentage of table had been occupied during the insertion.
System.out.println(" Table is " + hashFunction.loading
+ "% full.....");
} else {
// (e)Add those data names to the table start with empty table until the table is 40% full.
System.out.println(" table is " + hashFunction.loading
+ "% full now ");
break;
}
}
hashFunction.printTable();
}
private static class KVpair<K, V> implements Map.Entry<K, V> {
int hash;
final K key;
V value;
KVpair<K, V> next;
protected KVpair(int hash, K key, V value, KVpair<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@SuppressWarnings("unchecked")
protected Object clone() {
return new KVpair<>(hash, key, value, (next == null ? null
: (KVpair<K, V>) next.clone()));
}
// Map.Entry Ops
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
@SuppressWarnings("rawtypes")
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?, ?> e = (Map.Entry) o;
return key.equals(e.getKey()) && value.equals(e.getValue());
}
public int hashCode() {
return (Objects.hashCode(key) ^ Objects.hashCode(value));
}
public String toString() {
return key.toString() + "=" + value.toString();
}
}
}
class HashFunction {
// (d)Use the same name as the key for sfold function in HashFunction class
// to create the hash code for the table entry.
int sfold(String s, int M) {
int intLength = s.length() / 4;
int sum = 0;
for (int j = 0; j < intLength; j++) {
char c[] = s.substring(j * 4, (j * 4) + 4).toCharArray();
int mult = 1;
for (int k = 0; k < c.length; k++) {
sum += c[k] * mult;
mult *= 256;
}
}
char c[] = s.substring(intLength * 4).toCharArray();
int mult = 1;
for (int k = 0; k < c.length; k++) {
sum += c[k] * mult;
mult *= 256;
}
return (Math.abs(sum) % M);
}
}
class RandomStringGenerator {
private static final String CHAR_LIST_ALLOWED = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
private static final int STRING_LENGTH = 8;
public String getRandomString() {
StringBuffer randStr = new StringBuffer();
for (int i = 0; i < STRING_LENGTH; i++) {
int number = getRandomNumber();
char ch = CHAR_LIST_ALLOWED.charAt(number);
randStr.append(ch);
}
return randStr.toString();
}
private int getRandomNumber() {
int randomInt = 0;
Random random = new Random();
randomInt = random.nextInt(CHAR_LIST_ALLOWED.length());
if (randomInt - 1 == -1) {
return randomInt;
} else {
return randomInt - 1;
}
}
}
Output : size of table or slot is taken 5 in below case
-------------
Table is 20% full.....
Search : HWESTQWE HWESTQWE
table is 40% full now
Hashtable Contents :
IQYPPPVR=IQYPPPVR
null
null
null
HWESTQWE=HWESTQWE
Description :
---------------------
1. Please refer the main method to find all the answers of quesries which are mentioned in actual question ( point a to f).
2. There are several mehtod in code writtten in question are not usefull or were not being used so i have removed the same. like h() and p().
3. i have introduced following new stuff in attached code.
RandomStringGenerator.java class to genrate random eight character length string.
isFull() method in hashtable to check the table capacity while inserting string.
hashInsert(E k) method is used when key and value will have to be inserted as same key = value
please let me know if you find any difficulties to make understanding on above code.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.