CSC1020 Homework 11

Overview

Using the provided SJHashMap implementation, which uses open addressing with linear probing, implement the methods described below.

This implementation does not support null keys.

public V remove(Object key)

Remove the entry with the given key and return the value that was associated with it. If the key is not present, return null.

When removing an entry, replace it with the provided deletedKey marker rather than setting the array location to null. A deleted location must remain distinguishable from a location that has never been occupied so that later searches can continue through the probe sequence.

public int size()

Return the number of active key/value mappings currently stored in the map. Deleted entries do not count toward the size.

public String toString()

Return a String representation of the map in this form:

{key=value, key=value, ...}

You must use a StringJoiner to construct the result. Examine the backing array from the lowest index to the highest index and add each active entry to the StringJoiner. Do not include unused array locations or entries marked with deletedKey.

An empty map must return:

{}

private int find(Object key)

This method was mostly implemented in class. Complete its probe-counting behavior and ensure that a search cannot continue forever if every array location has been occupied.

A probe occurs whenever find() examines an occupied array location that does not contain the requested key and must advance to the next location. The initial index calculated from the hash code does not count as a probe unless find() must move past it.

Each call to find() must increment the find counter exactly once, whether or not probing is required.

Linear probing must wrap from the end of the backing array to index 0. If find() returns to the index where the search began without finding the key or an unused array location, the search must terminate and return -1.

public double averageProbes()

Return the average number of probes per call to find(). If find() has not yet been called, return 0.0.

Analysis

Answer the following questions in a text document named HW11.txt and place the file in the root of your repository.

  1. What does the hashCode() method of the Integer class return? How is that value determined?
  2. Why do we take the modulus of the hash code by the capacity of the table before choosing the initial array index?
  3. What is the LOAD_THRESHOLD constant used for? Why does an open-addressed hash table need to resize before it becomes completely full?
  4. Consider the following sequence. Assume these are the only map operations that have occurred.
final int capacity = 5;
final int firstKey = 1;
final int secondKey = 6;
final int thirdKey = 11;
SJHashMap<Integer, String> map = new SJHashMap<>(capacity);
map.put(firstKey, "one");
map.put(secondKey, "six");
map.put(thirdKey, "eleven");

a. What initial array index is calculated for each key?

b. At what final array index is each key stored?

c. How many probes occur while inserting each key? Explain why.

d. After the three calls to put(), how many total probes have occurred and how many times has find() been called?

e. What value should averageProbes() return at this point? Show the calculation.

f. Explain how linear probing resolves the collisions in this example.