Modify the hashFunction method

$($

from the previous module

$)$

$.$

$1$

$$Refactor the method name to hashFunction

$2$

$.$

$2$

$$Return

$1$

$$plus the floor modulus of the hash code and the capacity minus

$1$

$,$

$$which excludes

$0$

$$from the output range.

$3$

$$This becomes your secondary hash function.

B A private hashFunction

$1$

$$method which takes a key parameter.

$1$

$$Define a salt which is a string literal containing your full name, then concatenate the salt with the given key.

$2$

$$Compute a hash code from the salted key above using a cryptographic hash function.

i Either call a java.security.MessageDigest algorithm or translate a published algorithm from pseudocode.

ii Use a cryptographic hash function which isn

$$

t compromised, such as SHA

$-$

$256$

$.$

$3$

$$Return that hash code modulo the capacity as an index, using the floor modulus instead of the modulus operator.

$4$

$$This becomes your primary hash function.

C Modify the put and get methods

$($

from the previous module

$)$

$.$

$1$

$$Use your primary hash function and double hashing with your secondary hash function instead of linear probing.

$2$

$$This replaces linear probing with double hashing, which is equivalent to linear probing with a deterministic but variable

offset based on the key from

$1$

$$to capacity minus

$1$

$$instead of a constant offset of

$1$

$.$

page

$2/2$

$3$

RD QUARTER: REHASHING

J Modify the following private fields:

$1$

$$Reinitialize the initial capacity

$($

from the previous module

$)$

$$to an odd prime number between

$10$

$$and

$50$

$.$

$2$

$$A static constant floating point number for the load factor bound, initialized to

$75$

$\%$

$.$

K Still in the HashTable class

$($

not in the DataTable interface

$)$

$,$

$$override the loadFactor method:

$1$

$$Return the ratio of the size plus the contamination to the capacity. This adds the contamination to the numerator.

$2$

$$Don

$$

t use integer division. Use floating point division.

L A private rehash method.

$1$

$$Keep a backup reference to the old array which the array field currently references.

$2$

$$Reassign the array field to reference a new array with a length equal to the new capacity.

$3$

$$Reinitialize the size, fingerprint, and contamination to

$0$

$.$

$$Don

$$

t call the clear method.

$4$

$$For each row in the old array

$($

skipping nulls and tombstones

$)$

$,$

$$call put and pass it the corresponding key and list of fields,

which rehashes that row into the new array. Don

$$

t use the table

$$

s iterator.

$5$

$$When the method terminates, the backup reference becomes unreachable, so the old array is garbage collected.

M Modify the put method.

$1$

$$Before returning from a miss, if the load factor exceeds the load factor bound, dynamically expand the array.

i Reassign the capacity field to be the next odd prime number which is at least twice the previous, either by generating

it using an original algorithm or by retrieving it from a static constant array of eligible primes.

ii Call the rehash method.

$4$

TH QUARTER: SET THEORY OPERATIONS

N In the Table interface, a default union method which takes another table parameter

$($

referred to as that table

$)$

$.$

$1$

$$If this table and that table don

$$

t have equal degrees, throw an illegal argument exception.

$2$

$$For each row in that table, call put on this table and pass it the corresponding key and list of fields from that table.

O In the Table interface, a default intersect method which takes another table parameter

$($

referred to as that table

$)$

$.$

$1$

$$If this table and that table don

$$

t have equal degrees, throw an illegal argument exception.

$2$

$$For each row in this table, if that table doesn

$$

t contain the corresponding key, add it to a list of keys to be removed.

$3$

$$Then$,$ for each key in the list of keys to be removed, call remove on this table and pass it that key.

P In the Table interface, a default minus method which takes another table parameter

$($

referred to as that table

$)$

$.$

$1$

$$Repeat like step O above, but when the table does

$($

not doesn

$$

t

$)$

$$contain the corresponding key in step

$2$

$.$

Q In the Table interface, a default keep method which takes a column parameter

$($

string

$)$

$$and a target parameter

$($

object

$)$

$.$

$1$

$$Call filter on this table and pass it the given parameters.

$2$

$$Call intersect on this table and pass it the partition which filter returned.

R In the Table interface, a default drop method which takes a column parameter

$($

string

$)$

$$and a target parameter

$($

object