This is a comparison of the number of collisions caused by inserting keypairs in a hashtable with respect to Linear Probing and Double Hashing methods.
If the hash index was empty/available, it would insert the keypair; if there was a collison, it would go and check the next hash index on the right and repeat until it found a hash index that was empty/available.
The same type of premise as Linear probing, but instead of going to the next hash index if there was a collision, it would go to a calculated hash index and repeat the process until a hash index was found to be empty/available.
The double hashing function:
(Q can be set to any integer, I just used 211.)
public int hashFunc2(K k) {
int Q = 211;
int hashVal;
while (Q >= N) {
Q--;
}
hashVal = Q - (h.hashIndex(k) % Q);
if (hashVal < 0) {
hashVal += N;
}
return hashVal;
}
The keypair structure (the objects being inserted in the hashtables) have a unique key and random element.
public class Item<K,E> implements IItem<K, E>
{
private K key;
private E elem;
//Purpose: Takes as input a key and element and sets them to the private variables
public Item(K k, E e){
key = k;
elem = e;
}
// Purpose: To get the key or left side of the item
public K getKey() {
return(key);
}
// Purpose: To get the element or right side of the item
public E getElem() {
return(elem);
}
}
