Practice-It

On your homework, you implemented a class called HashMap, a map of key/value pairs implemented using a hash table with separate chaining. Assume that the class is implemented in the following way:

public class HashMap implements Map {
    private Node[] elements;
    private int size;
    ...

    private int hash(K key) {...}

    private class Node {
        private K key;
        private V value;
        private Node next;
        ...
    }
}

Add a method to this class named trimChains that accepts an integer k as a parameter and ensures that the linked list of nodes in every index of the internal hash table is no longer than k nodes at most. If a given linked list is longer than k elements, you should shorten it by removing nodes from the front of the chain. For example, if a map named map has an inner hash table storing the linked lists in the picture at left, and the client makes the call of map.trimChains(2);, your method should change the inner hash table to store the lists in the picture at right.

   +---+
 0 |   |→ 50=21
   +---+
 1 | / |
   +---+
 2 |   |→ -2=43 → 77=3  → 82=5 → 22=66
   +---+
 3 |   |→ 43=15 → 98=-2 → -8=1
   +---+
 4 |   |→ 74=21
   +---+
size = 9

   +---+
 0 |   |→ 50=21
   +---+
 1 | / |
   +---+
 2 |   |→ 82=5  → 22=66
   +---+
 3 |   |→ 98=-2 → -8=1
   +---+
 4 |   |→ 74=21
   +---+
size = 6

If the value of k passed is 0 or negative, you should completely empty each chain of all nodes. Your map's size field should store the correct value after your method, so if you remove any nodes, update the size. Do not recreate the internal hash table or copy it entirely. You don't need to consider load factor or rehashing on this problem.

You should not create any arrays or temporary data structures. This method should run in O(N) time, where N is the total number of nodes in the map. For full credit, do not walk the entire length of any linked list chain more than once. Don't call any of the existing methods on your hash map, since they would hurt the efficiency of your method.

(NOTE: To be compatible with Practice-It and avoid conflicting with Java's java.util.HashMap, our HashMap is renamed HashMap2 here.)