I need help converting this code that is using Linear Probing to Quadratic Probing. I am not sue how to accomplish that. Can someone help me? Thanks so much...
import java.util.*;
// A HashMap class which uses linear probing
public class HashMap383<K, V> {
// array-based; this is the array's initial capacity
public static final int INITIAL_CAPACITY = 13;
// each hash entry has one of these statuses
public static final int EMPTY = 0, ACTIVE = 1, DELETED = 2;
// maximum % of ACTIVE cells in the array before we rehash
public static final double MAX_LAMBDA = .5;
// the array in which keys and values are stored
private HashEntry<K, V>[ ] data;
private int capacity = INITIAL_CAPACITY;
// number of currently ACTIVE hash entries in the Map
private int size = 0;
// number of currently ACTIVE or DELETED has entries in the Map -- determines when to rehash
private int occupied = 0;
//The array contains HashEntry objects
private class HashEntry<X, Y> {
private X key;
private Y value;
private int status; // 0 = empty, 1 = active, 2 = deleted
public HashEntry( ) { key = null; value = null; status = EMPTY; }
}
// create an array of EMPTY HashEntry objects
public HashMap383( ) {
data = newTable(INITIAL_CAPACITY);
}
private HashEntry<K,V>[ ] newTable(int capacity) {
HashEntry<K,V>[ ] answer = (HashEntry<K,V>[ ]) new HashEntry[capacity];
for (int i=0; i<capacity; i++)
answer[i] = new HashEntry<K,V>( );
return answer;
}
private int probe(K key) {
int value = Math.abs(key.hashCode( ));
return value%capacity;
}
// this method tries to find a key in the array. It returns the position in the array
// of the HashEntry with this key. It searches for the key starting with an initial probe
// (from the probe method), and then uses linear probing from there.
// It stops and returns a position when it finds a HashEntry with the right key, whether the
// HashEntry is ACTIVE or DELETED. If findPos finds an EMPTY HashEntry, that means it has failed
// to find the key; however, it returns the position of that EMPTY HashEntry.
// Then it is up to put, get, and remove to determine what to do based on whether
// the status of the returned position in the array is ACTIVE, DELETED, or ENTRY.
// This method assumes that MAX_LAMBDA < 1; i.e., there will always be at least one EMPTY
// HashEntry in the array.
private int findPos(K key) {
int initialProbe = probe(key);
int probe = initialProbe;
while (data[probe].status != EMPTY) {
if (data[probe].key.equals(key)) break;
probe++;
if (probe == capacity) probe = 0;
}
return probe;
}
// retrieve a value stored under a key
// this version of get uses linear probing (note the statement "probe++;")
public V get(K key) {
int pos = findPos(key);
if (data[pos].status == ACTIVE) return data[pos].value;
return null;
}
// place a new entry into the Map. If the key already exists,
// its value is overwritten. put returns the old value, if it
// existed (otherwise null)
// put also uses linear probing (note the statement "probe++;")
public V put(K key, V value) {
int pos = findPos(key);
switch (data[pos].status) {
case EMPTY:
if ((occupied + 1)/(double) capacity > MAX_LAMBDA) {
rehash( );
return put(key, value);
}
data[pos].key = key;
data[pos].value = value;
data[pos].status = ACTIVE;
size++;
occupied++;
return null;
case DELETED:
data[pos].value = value;
data[pos].status = ACTIVE;
size++;
return null;
default: // ACTIVE
V answer = data[pos].value;
data[pos].value = value;
return answer;
}
}
// remove an entry from the Map. All that this method has to do is
// to change the status of the right HashEntry object to DELETED.
// again, it uses linear probing
public V remove(K key) {
int pos = findPos(key);
if (data[pos].status == ACTIVE) {
data[pos].status = DELETED;
size--;
return data[pos].value;
}
return null;
}
// if the % of ACTIVE cells in the data array exceeds LAMBDA,
// then the table is rehashed. Its capacity is (approximately) doubled
// (the capacity is always made to be a prime number) and then
// all of the data is re-entered into the table
private void rehash( ) {
System.out.println("Rehashing");
int oldCapacity = capacity;
HashEntry<K,V> oldData[ ] = data;
capacity = nextPrime(capacity*2);
data = newTable(capacity);
size = 0;
occupied = 0;
for (int i=0; i<oldCapacity; i++)
if (oldData[i].status == ACTIVE)
put(oldData[i].key, oldData[i].value);
}
// used by rehash
private static int nextPrime(int x) {
boolean isPrime;
for (x++; ; x++) {
isPrime = true;
for (int i=2; i<=x/2; i++) {
if (x%i == 0) {
isPrime = false;
break;
}
}
if (isPrime) return x;
}
}
// return all of the keys in the Map as a Set.
public Set<K> keySet( ) {
Set<K> answer = new HashSet<K>( );
for (int i=0; i<capacity; i++)
if (data[i].status == ACTIVE)
answer.add(data[i].key);
return answer;
}
// I wrote this primarily for debugging purposes. Note that for each ACTIVE or DELETED HashEntry,
// it prints the position, status (ACTIVE == 1, DELETED == 2), key, and value. Then at the end
// it prints the Map's capacity, size, and number of ACTIVE or DELETED cells.
public String toString( ) {
String answer = "[";
for (int i=0; i<capacity; i++)
if (data[i].status != EMPTY)
answer += " (" + i + ", " + data[i].status + ", " + data[i].key + ", " +
data[i].value + ")";
return answer + " ] capacity " + capacity + " size " + size + " occupied " + occupied;
}
public static void main(String[ ] args) {
// HashMap383<Double, String> m = new HashMap383<Double, String>( );
// double keys [ ] = {1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9,
// 10.0, 11.1, 12.2, 13.3, 14.4, 15.5};
// String values [ ] = {"a", "b", "c", "d", "e", "f", "g", "h", "i",
// "j", "k", "l", "m", "n", "o"};
// for (int i=0; i<keys.length; i++)
// m.put(keys[i], values[i]);
// System.out.println(m);
// for (int i=0; i<keys.length; i+=2)
// m.remove(keys[i]);
// System.out.println("\n" + m + "\n");
// for (int i=0; i<keys.length; i+=4)
// m.put(keys[i], values[i]+"x");
// System.out.println("\n" + m + "\n\nNow to test keyset\n");
// Set<Double> theKeys = m.keySet( );
// for (Iterator<Double> it = theKeys.iterator( ); it.hasNext( ); ) {
// Double d = it.next( );
// System.out.print("(" + d + ", " + m.get(d) + ") ");
// }
// test class for HashMap383 with quadratic hashing
Scanner s = new Scanner(System.in);
HashMap383<String, String> m = new HashMap383<String, String>( );
System.out.println("creating the map...");
for (int i=0; i<5; i++) {
System.out.println("Enter a key and a value");
String key = s.next( );
String value = s.next( );
System.out.println("put returns " + m.put(key,value));
}
System.out.println(m);
System.out.println("Enter 2 keys to remove");
m.remove(s.next( ));
m.remove(s.next( ));
Set<String> theKeys = m.keySet( );
for (Iterator<String> it = theKeys.iterator( ); it.hasNext( ); ) {
String d = it.next( );
System.out.print("(" + d + ", " + m.get(d) + ") ");
}
}
}