Answer must be in Java Rehashing requires recomputing the hash function for all
ID: 3696174 • Letter: A
Question
Answer must be in Java
Rehashing requires recomputing the hash function for all items in the hash table. Since computing the hash function is expensive, suppose objects provide a hash member function of their own, and each object stores the result in an additional data member the first time the hash function is computed for it. Show how such a scheme would apply for the Employee class in Figure 5.8
Thank you!
1 public class Employee 3 public boolean equals( Object rhs) freturn rhs instanceof Employee && name.equals( ((Employee)rhs).name); 6 public int hashCode) return name.hashCode); 1 private String name; private double salary; private int seniority; 10 12 13 14 /Additional fiel // Additional fields and methods Figure 5.8 Example of Employee class that can be in a hash tableExplanation / Answer
Demo.java
import java.util.Hashtable;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;
public class Demo {
public static void main(String[] args)
{
System.out.println("Starting demo.");
//instantiate a few example employees and add them to a hashTtable.
Hashtable map1 = new Hashtable();
Employee a = new Employee("Ash",60000, 5);
Employee b = new Employee("Briana",100000, 20);
Employee c = new Employee("Chun",30000, 1);
Employee d = new Employee("Daria",10000, 4);
Employee e = new Employee("Espinoza",75000, 8);
Employee f = new Employee("Farah",50000, 4);
Employee g = new Employee("Giuseppe",160000, 15);
map1.put(a, a);
map1.put(b, b);
map1.put(c, c);
map1.put(d, d);
map1.put(e, e);
map1.put(f, f);
map1.put(g, g);
//Time how long it takes to retrieve many random objects when the objects have a precalculated hashcode
long time = System.currentTimeMillis();
for(int i = 0; i < 5000000; i++)
{
Object test = map1.get(a);
test = map1.get(b);
test = map1.get(c);
test = map1.get(d);
test = map1.get(e);
test = map1.get(f);
test = map1.get(g);
}
// this averages about ~240 miliseconds on my computer.
System.out.println("Time in miliseconds to find objects in map using a precalculated hashcode: " + (System.currentTimeMillis() - time));
//Time how long it takes to retrieve many random objects when you have to calcualte the hashcode each time.
//(simulated)
time = System.currentTimeMillis();
for(int i = 0; i < 5000000; i++)
{
//Calculating each hashcode is simulated by calling the objects getHashCode function
//This is to avoid coding an entirelly new file
Object test = map1.get(a);
a.getHashCode();
test = map1.get(b);
b.getHashCode();
test = map1.get(c);
c.getHashCode();
test = map1.get(d);
d.getHashCode();
test = map1.get(e);
e.getHashCode();
test = map1.get(f);
f.getHashCode();
test = map1.get(g);
g.getHashCode();
}
//This averages about ~900 miliseconds on my computer
System.out.println("Time in miliseconds to find objects in map using a calculating hashcode each time: " + (System.currentTimeMillis() - time));
//This section is used to test recalculation of hashcodes.
//The given method of calculating an Employee instance's hashcode is to find the hashcode of the name field.
//The hashcode should change if and only if the name field changes.
System.out.println("Testing recalculation of hashcodes:");
System.out.println("Hashcode of Employee with fields { name = 'Ash', salary = 60000, senority = 5: " + a.hashCode());
a.setEmployee("Ashley", 60000, 5);
System.out.println("Hashcode of Employee with fields { name = 'Ashley', salary = 60000, senority = 5: " + a.hashCode());
a.setEmployee("Ashley", 160000, 15);
System.out.println("Hashcode of Employee with fields { name = 'Ashley', salary = 160000, senority = 15: " + a.hashCode());
System.out.println("As you can see, the hashcode only changes when the name of the employee changes.");
Random r = new Random();
MinMaxHeap<Integer> mmh = new MinMaxHeap();
ArrayList<Integer> al = new ArrayList();
for(int i = 1; i < 1000; i++)
{
int x = r.nextInt(100000);
mmh.insert(x);
al.add(x);
}
Collections.sort(al);
P.pp("");
P.pp("Testing MinMaxHeap's deleteMin, should output the numbers in order from least to greatest.");
for(int i = 1; i < 10; i++)
P.pp("MinMaxHeap: "+ mmh.deleteMin() + " ArrayList: " + al.remove(i-1));
P.pp("");
P.pp("Testing MinMaxHeap's deleteMax, should output the numbers in order from greatest to least.");
for(int i = 1; i < 10; i++)
P.pp("MinMaxHeap: "+ mmh.deleteMax() + " ArrayList: " + al.remove(al.size()-1));
}
}
MinMaxHeap.java
public class MinMaxHeap<E extends Comparable<? super E>> {
private int size = 0; // The amount of elements that are in the heap
private E[] a; // The array
final private int INITIAL_SIZE = 100;
/**
* Initializes a heap of capacity 32.
*/
public MinMaxHeap() {
a = (E[]) new Comparable[INITIAL_SIZE];
}
/**
* Inserts data into the tree in heap order. Duplicates are allowed.
*
* @param data the data in which to insert into the tree.
*/
public void insert(E data) {
E e = data; // e is shorthand for the element we want to insert.
//Case 1: The heap is not big enough
if (size == a.length - 1) {
enlargeArray();
}
//case 2: The heap is empty
if (size == 0) {
a[1] = e;
size++;
} //Case 3: The heap is not empty
else {
size++;
int hole = size; //create a hole in the next availble slot.
if (findLevel(hole) % 2 == 0) //the hole is on a min level
{
if (e.compareTo(a[hole / 2]) < 0) {
//the element is less than the parent
//push the parent down and start checking grand parents.
a[hole] = a[hole / 2];
hole /= 2;
for (a[0] = e; //initial spot for e
e.compareTo(a[hole / 4]) < 0; //Run this loop while e is less than it's grandparent.
hole /= 4) //reset the index's position to it's parents.
{
a[hole] = a[hole / 4]; //push the element's data into it's parent's index.
}
a[hole] = e; // Once e is actually more than it's grandparent, set it at it's ideal place.
} else {
//the element is more than the parent
//just start checking the grandparents.
for (a[0] = e; //initial spot for e
e.compareTo(a[hole / 4]) > 0; //Run this loop while e is greater than it's grandparent.
hole /= 4) //reset the index's position to it's parents.
{
a[hole] = a[hole / 4]; //push the element's data into it's parent's index.
}
a[hole] = e; // Once e is actually more than it's grandparent, set it at it's ideal place.
}
} else //Case 3.2 The hole is on a min level.
if (e.compareTo(a[hole / 2]) < 0) {
//the element is less than the parent
//just start checking the grandparents.
for (a[0] = e; //initial spot for e
e.compareTo(a[hole / 4]) < 0; //Run this loop while e is kess than it's grandparent.
hole /= 4) //reset the index's position to it's parents.
{
a[hole] = a[hole / 4]; //push the element's data into it's parent's index
}
a[hole] = e; // Once e is actually less than it's grandparent, set it at it's ideal place.
} else {
//the element is greater than the parent
//push the parent down and start checking grandparents.
a[hole] = a[hole / 2];
hole /= 2;
for (a[0] = e; //initial spot for e
e.compareTo(a[hole / 4]) > 0; //Run this loop while e is greater than it's grandparent.
hole /= 4) //reset the index's position to it's parents.
{
a[hole] = a[hole / 4]; //push the element's data into it's parent's index
}
a[hole] = e; // Once e is actually less than it's grandparent, set it at it's ideal place.
}
}
}
/**
* Returns the smallest entry in the tree.
*
* @return the smallest entry.
*/
public E findMin() {
return a[1]; //The first entry in the array is always the minimum, since we sort it every time we edit the tree.
}
/**
* Returns the largest entry in the tree.
*
* @return the largest entry.
*/
public E findMax() {
//different from findMin, since the largest values are kept in the second row
//we must compare the two, and return the largest.
//Case 1: There is less than 3 elements.
if (size < 3) {
return a[size];
}
//Case 2: There is more than 3 or more elements.
return a[2].compareTo(a[3]) > 0 ? a[2] : a[3];
}
/**
* Deletes the first entry in the heap. This is like 'Dequeueing' in a
* queue.
*
* @return
*/
public E deleteMin() {
E min = findMin();
//Case 1: There are less than 3 elements in the heap.
if (size < 3) {
a[1] = a[2];
a[2] = null;
size--;
return min;
} /*else if (size == 3) //Case 2: there are 3 elements in the heap.
} */else {
a[1] = a[size]; //place the last value on the top...
a[size] = null; //... empty out the last element...
size--; //... subtract one from the size...
percolateDownMin(1); //... and percolate that value down into the right spot
return min;
}
}
public E deleteMax() {
E max = findMax();
//Case 1: There are less than 3 elements in the heap.
if (size < 3) {
a[2] = null;
size--;
return max;
} else {
int index = a[2].compareTo(a[3]) < 0 ? 3 : 2;
a[index] = a[size]; //place the last value on the top and then...
a[size] = null;
size--;
percolateDownMax(index); //percolate that value down into the right spot
return max;
}
}
private void percolateDownMin(int hole) {
E e = a[hole]; //this is element in the hole that we shall be pushing down.
//We need to remove the last element in the list
int grandchild; //designate a variable to choose a child later.
E x = a[size]; //x represents the last element in the array.
for (;
hole * 4 <= size; //Run this loop until there are no grandchildren for the hole
hole = grandchild) { //'traverse down'
grandchild = 4 * hole; //find the index of the left-most child, first.
if (grandchild != size) //if the child isn't the last element on the heap
{
//Find out which grandchild is the smallest one.
int minGrandchild = grandchild;
for (int i = 1; i <= 3; i++) {
if (a[grandchild + i] != null && a[grandchild + i].compareTo(a[minGrandchild]) < 0) {
minGrandchild = grandchild + i;
}
}
grandchild = minGrandchild;
}
if (a[grandchild].compareTo(e) < 0) //if the grandchild is less than the element we're pushing down...
{
a[hole] = a[grandchild]; //push the child up
} else {
break;
}
}
a[hole] = x; // The hole where the loop stopped at, put e in.
}
private void percolateDownMax(int hole) {
E e = a[hole]; //this is element in the hole that we shall be pushing down.
int grandchild; //designate a variable to choose a child later.
E x = a[size]; //x represents the last element in the array.
for (;
hole * 4 <= size; //Run this loop until there are no grandchildren for the hole
hole = grandchild) { //'traverse down'
grandchild = 4 * hole; //find the index of the left-most child, first.
if (grandchild != size) //if the child isn't the last element on the heap
{
//Find out which grandchild is the greatest one.
int maxGrandchild = grandchild;
for (int i = 1; i <= 3; i++) {
if (a[grandchild + i] != null && a[grandchild + i].compareTo(a[maxGrandchild]) > 0) {
maxGrandchild = grandchild + i;
}
}
grandchild = maxGrandchild;
}
if (a[grandchild].compareTo(e) > 0) //if the grandchild is greater than the element we're pushing down...
{
a[hole] = a[grandchild]; //push the grandchild up
} else {
break;
}
}
a[hole] = x; // The hole where the loop stopped at, put e in.
}
/**
* Doubles the array size.
*/
private void enlargeArray() {
E[] newArray = (E[]) new Comparable[(size * 2) + 1]; // Double the size
for (int i = 0; i <= size; i++) {
newArray[i] = a[i]; //Copy the data to the new array.
}
a = newArray; //Designate the new array as the instance array.
}
/**
* finds the level the given index is located in.
*
* @param x the index
* @return the level.
*/
private int findLevel(int x) {
int init = x;
x--;
int i = 0;
while (x > 0) {
i++;
x -= Math.pow(2, i);
}
i++;
return i;
}
}
Employee.java
public class Employee
{
private String name; //given
private double salary; //given
private int seniority; //given
private int hash; //We can add the field "hash" of type int
//I've added a constructor for the Employee class, to help demonstration
public Employee(String name, double salary, int seniority)
{
this.name = name;
this.salary = salary;
this.seniority = seniority;
//upon construction of this object, we can predetermine the hash
//this way, the hash is only calculated once, instead of needed to calculate every time we need it.
//a consequence of this is that it adds percisesly 32 bits of memory per object instantiated.
this.hash = getHashCode();
}
//given
public boolean equals( Object rhs )
{
return rhs instanceof Employee && name.equals( ((Employee)rhs).name );
}
//given
public int hashCode( )
{
return hash;
}
/**
* returns the predetermined hash code of the object, to avoid calculating on the spot.
* use this method instead of hashCode for less processor use.
* @return the hash code of the object.
*/
public int getHashCode()
{
return name.hashCode( );
}
//If at anypoint we want to modify the fields of an instance of this class,
//We would need to recalculate the hashcode, since the hash code is calculated
//from the field "name"
public void setEmployee(String name, double salary, int seniority)
{
this.name = name;
this.salary = salary;
this.seniority = seniority;
this.hash = getHashCode();
}
}
P.java
public class P {
public static void p(Object s)
{
System.out.print(s);
}
public static void pp(Object s)
{
System.out.println(s);
}
}
sample output
Starting demo.
Time in miliseconds to find objects in map using a precalculated hashcode: 9073
Time in miliseconds to find objects in map using a calculating hashcode each time: 8257
Testing recalculation of hashcodes:
Hashcode of Employee with fields { name = 'Ash', salary = 60000, senority = 5: 66134
Hashcode of Employee with fields { name = 'Ashley', salary = 60000, senority = 5: 1970305034
Hashcode of Employee with fields { name = 'Ashley', salary = 160000, senority = 15: 1970305034
As you can see, the hashcode only changes when the name of the employee changes.
Testing MinMaxHeap's deleteMin, should output the numbers in order from least to greatest.
MinMaxHeap: 60 ArrayList: 60
MinMaxHeap: 297 ArrayList: 322
MinMaxHeap: 322 ArrayList: 445
MinMaxHeap: 427 ArrayList: 690
MinMaxHeap: 445 ArrayList: 914
MinMaxHeap: 639 ArrayList: 1134
MinMaxHeap: 690 ArrayList: 1280
MinMaxHeap: 694 ArrayList: 1491
MinMaxHeap: 914 ArrayList: 1520
Testing MinMaxHeap's deleteMax, should output the numbers in order from greatest to least.
MinMaxHeap: 99921 ArrayList: 99921
MinMaxHeap: 99641 ArrayList: 99641
MinMaxHeap: 99640 ArrayList: 99640
MinMaxHeap: 99598 ArrayList: 99598
MinMaxHeap: 99375 ArrayList: 99375
MinMaxHeap: 99347 ArrayList: 99347
MinMaxHeap: 99328 ArrayList: 99328
MinMaxHeap: 99110 ArrayList: 99110
MinMaxHeap: 98785 ArrayList: 98785