HOW DO I FIND THE AVERAGE PROBE COUNT? import java.util.ArrayList; public class
ID: 3865232 • Letter: H
Question
HOW DO I FIND THE AVERAGE PROBE COUNT?
import java.util.ArrayList;
public class HashTable<K, V> {
private HashObject<K, V> hashTable[]; // linear probing table
char typeOfHashTable;
int tableSize;
int n; // number of objects stored in hashTable
// create hashTables and choose between liner probing and double hashing
@SuppressWarnings("unchecked")
public HashTable(int indicator) {
tableSize = HashTest.tableSize;
//tableSize =8;
n = HashTest.numberOfObjects;
//n = 5;
HashObject.probe = 0;
hashTable = new HashObject[tableSize];
if (indicator == 1) {
typeOfHashTable = 'L';
} else if (indicator == 2) {
typeOfHashTable = 'D';
}
}
void insert(K key, V value) {
if (typeOfHashTable == 'L') {
LinearProbing(key, value);
} else if (typeOfHashTable == 'D') {
DoubleHashing(key, value);
}
}
private void LinearProbing(K key, V hashValue) {
HashObject<K, V> hashObject = new HashObject<K, V>(key, hashValue);
int home = getHashCode(key);
int index = home;
for (int i = 0; i < tableSize; i++) {
if (hashTable[index] == null) {
hashTable[index] = hashObject;
HashObject.probe++;
return;
} else if (hashTable[index].equals(hashObject)) {
HashObject.duplicate++;
return;
}else{
HashObject.probe++;
index = getNextProbe(home, i);
}
}
}
private void DoubleHashing(K key, V hashValue) {
HashObject<K, V> hashObject = new HashObject<K, V>(key, hashValue);
int home = getHashCode(key);
int index = home;
for (int i = 0; i < tableSize; i++) {
if (hashTable[index] == null) {
HashObject.probe++;
hashTable[index] = hashObject;
return;
} else if (hashTable[index]== hashObject) {
HashObject.duplicate++;
return;
}else{
HashObject.probe++;
index = getNextProbe(key, home, i);
}
}
}
private int getNextProbe(int home, int i) {
return (home + i) % tableSize;
}
private int getHashCode(K key) {
int i = key.hashCode();
int value = i % tableSize;
if (value < 0) {
value += tableSize;
return value;
}
return value;
}
private int getNextProbe(K key, int home, int i) {
return (home + (i * getSecondHashCode(key)) )% tableSize;
}
private int getSecondHashCode(K Key) {
int i = Key.hashCode();
int value = 1+(i % (tableSize-2));
if (value < 0) {
value += tableSize;
return value;
}
return value;
}
// all keys in the table
public Iterable<K> keys() {
ArrayList<K> keys = new ArrayList<K>();
for (int i = 0; i < tableSize; i++) {
if (hashTable[i] != null) {
keys.add(hashTable[i].getKey());
}
}
return keys;
}
}
Explanation / Answer
Your Dependency class defination of HashObject is missing, so I could ot test your code!
What you can do is:
//count non-null objects in hashTable[]
int countObject = 0;
for (int i = 0; i < tablesize; i++)
if (hashTable[i] != null)
countObject++;
//We have total probe as HashObject.probe
//So avg probe = HashObject.probe/countObject/
double avgProbe = (double)HashObject.probe/countObject;
//If duplicates are aslo considered as probing count we do the followig:
double avgProbe = (double)(HashObject.probe+HashObject.duplicate)/countObject;
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.