I need help implementing in Java the #int probeOffset(int i). I appreciate any h
ID: 3752147 • Letter: I
Question
I need help implementing in Java the #int probeOffset(int i). I appreciate any help
LinearProbingHT -int N -int M -Entry Key, Value entries +LinearProbingHTO +LinearProbingHT(int M) -int hash(Key key, int i) int probeOffset(int i) o+void put(Key key, Value val) O+Value get(Key key) o+boolean contains(Key key) entries +void delete(Key key) +boolean isEmpty0 o+ int size +Iterable Key keys0 Entry EntryKey, EntryValue> -EntryKey key -EntrWalue value QuadProbingHT +EntryWalue Entry(EntryKey key, EntryValue +QuadProbingHTO sint probeOffset(int i)Explanation / Answer
public class HashedDictionary<K, V>
{
public TableEntry<K, V>[] hashTable; // dictionary entries
private int numberOfEntries;
private int locationsUsed; // number of table locations not null
private static final int DEFAULT_SIZE = 101; // must be prime
private static final double MAX_LOAD_FACTOR = 0.5; // fraction of hash table that can be filled
public HashedDictionary()
{
this(DEFAULT_SIZE); // call next constructor
} // end default constructor
public HashedDictionary(int tableSize)
{
// ensure that table is prime size at least as big as user wants;
// if tableSize is prime, do not change it
int primeSize = getNextPrime(tableSize);
hashTable = new TableEntry[primeSize];
numberOfEntries = 0;
locationsUsed = 0;
} // end constructor
// -------------------------
// We've added this method to display the hash table for illustration and testing
// -------------------------
public void display()
{
for (int index = 0; index < hashTable.length; index++)
{
if (hashTable[index] == null)
System.out.println("null ");
else if (hashTable[index].isRemoved())
System.out.println("notIn ");
else
System.out.println(hashTable[index].getKey() + " " + hashTable[index].getValue());
} // end for
System.out.println();
} // end display
// -------------------------
// 20.14
public V add(K key, V value)
{
V oldValue;
if (isHashTableTooFull())
rehash();
int index = getHashIndex(key);
index = quadraticProbe(index, key);
assert (index >= 0) && (index < hashTable.length);
if ( (hashTable[index] == null) || hashTable[index].isRemoved())
{ // key not found, so insert new entry
hashTable[index] = new TableEntry<K, V>(key, value);
numberOfEntries++;
locationsUsed++;
oldValue = null;
}
else
{ // key found; get old value for return and then replace it
oldValue = hashTable[index].getValue();
hashTable[index].setValue(value);
} // end if
return oldValue;
} // end add
// 20.12
public V remove(K key)
{
V removedValue = null;
int index = getHashIndex(key);
index = locate(index, key);
if (index != -1)
{
// key found; flag entry as removed and return its value
removedValue = hashTable[index].getValue();
hashTable[index].setToRemoved();
numberOfEntries--;
} // end if
// else not found; result is null
return removedValue;
} // end remove
// 20.11
public V getValue(K key)
{
V result = null;
int index = getHashIndex(key);
index = locate(index, key);
if (index != -1)
result = hashTable[index].getValue(); // key found; get value
// else not found; result is null
return result;
} // end getValue
// 20.15
private int quadraticProbe(int index, K key)
{
boolean found = false;
int removedStateIndex = -1; // index of first location in
// removed state
int i=0;
while ( !found && (hashTable[index] != null) && i< hashTable.length)
{
if (hashTable[index].isIn())
{
if (key.equals(hashTable[index].getKey()))
found = true; // key found
else // follow probe sequence
{
index = (index + i*i) % hashTable.length; // linear probing
i++;
}
}
else // skip entries that were removed
{
// save index of first location in removed state
if (removedStateIndex == -1)
removedStateIndex = index;
index = (index + i*i) % hashTable.length; // linear probing
i++ ;
} // end if
} // end while
// Assertion: either key or null is found at hashTable[index]
if (found || (removedStateIndex == -1) )
return index; // index of either key or null
else
return removedStateIndex; // index of an available location
} // end probe
// 20.13
public int locate(int index, K key)
{
boolean found = false;
int i=0;
while ( !found && (hashTable[index] != null) && i<hashTable.length)
{
if ( hashTable[index].isIn() && key.equals(hashTable[index].getKey()) )
found = true; // key found
else // follow probe sequence
{
index = (index + i*i) % hashTable.length; // linear probing
i++;
}
} // end while
// Assertion: either key or null is found at hashTable[index]
int result = -1;
if (found)
result = index;
return result;
} // end locate
public boolean contains(K key)
{
return getValue(key) != null;
} // end contains
public boolean isEmpty()
{
return numberOfEntries == 0;
} // end isEmpty
public boolean isFull()
{
return false;
} // end isFull
public int getSize()
{
return numberOfEntries;
} // end getSize
public final void clear()
{
for (int index = 0; index < hashTable.length; index++)
hashTable[index] = null;
numberOfEntries = 0;
locationsUsed = 0;
} // end clear
public int getHashIndex(K key)
{
int hashIndex = key.hashCode() % hashTable.length;
if (hashIndex < 0)
{
hashIndex = hashIndex + hashTable.length;
} // end if
return hashIndex;
} // end getHashIndex
/** Task: Increases the size of the hash table to a prime > twice its old size. */
private void rehash()
{
TableEntry<K, V>[] oldTable = hashTable;
int oldSize = hashTable.length;
int newSize = getNextPrime(oldSize + oldSize);
hashTable = new TableEntry[newSize]; // increase size of array
numberOfEntries = 0; // reset number of dictionary entries, since
// it will be incremented by add during rehash
locationsUsed = 0;
// rehash dictionary entries from old array to the new and bigger
// array; skip both null locations and removed entries
for (int index = 0; index < oldSize; index++)
{
if ( (oldTable[index] != null) && oldTable[index].isIn() )
add(oldTable[index].getKey(), oldTable[index].getValue());
} // end for
} // end rehash
/** @return true if lambda > MAX_LOAD_FACTOR for hash table;
* otherwise returns false. */
private boolean isHashTableTooFull()
{
return locationsUsed > MAX_LOAD_FACTOR * hashTable.length;
} // end isHashTableTooFull
private int getNextPrime(int integer)
{
// if even, add 1 to make odd
if (integer % 2 == 0)
{
integer++;
} // end if
// test odd integers
while(!isPrime(integer))
{
integer = integer + 2;
} // end while
return integer;
} // end getNextPrime
private boolean isPrime(int integer)
{
boolean result;
boolean done = false;
// 1 and even numbers are not prime
if ( (integer == 1) || (integer % 2 == 0) )
{
result = false;
}
// 2 and 3 are prime
else if ( (integer == 2) || (integer == 3) )
{
result = true;
}
else // integer is odd and >= 5
{
assert (integer % 2 != 0) && (integer >= 5);
// a prime is odd and not divisible by every odd integer up to its square root
result = true; // assume prime
for (int divisor = 3; !done && (divisor * divisor <= integer); divisor = divisor + 2)
{
if (integer % divisor == 0)
{
result = false; // divisible; not prime
done = true;
} // end if
} // end for
} // end if
return result;
} // end isPrime
// 20.09
class TableEntry<S, T>
{
private S key;
private T value;
private boolean inTable; // true if entry is in table
private TableEntry(S searchKey, T dataValue)
{
key = searchKey;
value = dataValue;
inTable = true;
} // end constructor
public S getKey()
{
return key;
} // end getKey
private T getValue()
{
return value;
} // end getValue
private void setValue(T newValue)
{
value = newValue;
} // end setValue
private boolean isIn()
{
return inTable;
} // end isIn
private boolean isRemoved() // opposite of isIn
{
return !inTable;
} // end isRemoved
// state = true means entry in use; false means entry not in use, ie deleted
private void setToRemoved()
{
key = null;
value = null;
inTable = false;
} // end setToRemoved
private void setToIn() // not used
{
inTable = true;
} // end setToIn
} // end TableEntry
} // end HashedDictionary
HashedDictionaryTest.java
import java.io.*;
import java.util.*;
public class HashedDictionaryTest
{
String method;
String key;
String value;
public HashedDictionaryTest(String method, String key, String value){
this.method = method;
this.key = key;
this.value = value;
}
public static void main(String[] args)
{
// declaring nameList as HashedDictionary instead of DictionaryInterface enables display method in HashedDictionary
HashedDictionary<Name, String> nameList = new HashedDictionary<Name, String>(11);
String line[]= new String[100];
String subline[]=new String[100];
String[] tokens=new String[100];
String subtoken[] =new String[100];
int i=0,j=0,k=0;
try{
Scanner scanner = new Scanner(new File("userfile.txt")).useDelimiter(" ");
while (scanner.hasNext()) {
line[i] = scanner.nextLine();
Scanner scanner1 = new Scanner(line[i]).useDelimiter(" ");
while (scanner1.hasNext()) {
subline[j] = scanner1.nextLine();
j++;
} i++;
}
String strLine;
while ((strLine = subline[k]) != null) {
tokens = strLine.split(" ");
for(int m=0; m<tokens.length;m++){
subtoken[m]=tokens[m];
}
if(tokens.length==1)
{
subtoken[1]=null;
subtoken[2]=null;
}
else if (tokens.length==2)
subtoken[2]=null;
HashedDictionaryTest record = new HashedDictionaryTest(subtoken[0],subtoken[1],subtoken[2]);//process record , etc
chooseMethod(subtoken[0],subtoken[1],subtoken[2],nameList);
k++;
}
}
catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public static void chooseMethod(String s , String s1 , String s2 ,HashedDictionary<Name, String> nameList )
{
if (s.equals("add"))
nameList.add(new Name(s1),s2);
else if (s.equals("print"))
nameList.display();
else if(s.equals("locate"))
nameList.locate( nameList.getHashIndex(new Name(s1)),new Name(s1));
else if (s.equals("remove"))
{
int index =nameList.getHashIndex(new Name(s1));
index=nameList.hashTable.length-index;
Name m= (Name)nameList.hashTable[index-1].getKey();
nameList.remove(m);
}
}
}
// end HashedDictionaryTest
Name.java
/** This class is like the one in the folder Comparable,
* but adds a constructor and hashCode for testing purposes. */
public class Name
{
private String first; // first name
private String last; // last name
public Name()
{
this("","");
} // end default constructor
public Name(String firstName) // for testing ***************
{
this(firstName, "");
} // end constructor
public Name(String firstName, String lastName)
{
first = firstName;
last = lastName;
} // end constructor
@Override
public int hashCode() // for testing ***************
{
// this hash code causes collisions
int h = 0;
for (int i = 0; i < first.length(); i++)
{
h = h + first.charAt(i);
}
return h;
// a reasonable hash code follows:
// return first.hashCode() + last.hashCode();
} // end hashCode
public void setName(String firstName, String lastName)
{
setFirst(firstName);
setLast(lastName);
} // end setName
public String getName()
{
return toString();
} // end getName
public void setFirst(String firstName)
{
first = firstName;
} // end setFirst
public String getFirst()
{
return first;
} // end getFirst
public void setLast(String lastName)
{
last = lastName;
} // end setLast
public String getLast()
{
return last;
} // end getLast
public void giveLastNameTo(Name aName)
{
aName.setLast(last);
} // end giveLastNameTo
@Override
public String toString()
{
return first + " " + last;
} // end toString
@Override
public boolean equals(Object other)
{
boolean result;
if ((other == null) || (getClass() != other.getClass()))
result = false;
else
{
Name otherName = (Name)other;
result = first.equals(otherName.first) &&
last.equals(otherName.last);
} // end if
return result;
} // end equals
} // end Name
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.