Implement a Hash Map With Linear Probing

Implement a map using a hash table, handling collisions via linear probing.

The scaffold supplies a method which provides a suitable hash function for this exercise. The scaffold also supplies a DEFUNCT entry (which distinguishes itself from other entries by having nulls for both key and value), available from within the methods you need to implement via DEFUNCT in Java and self.DEFUNCT in Python.

You need to implement all of the map ADT methods. See the tutorial sheet for an overview of the linear probing strategy for collision handling. Reminder: you need to make sure to handle DEFUNCTs correctly, and you need to make sure to "wrap around" to the start of the entry table rather than going off the edge.

ensureCapacity, which should expand the capacity of the hash map by creating a new backing table and reinserting every entry, has also been left blank. It won't be tested, but we encourage you to attempt to implement this!

In both programming languages, there is an empty main function in the Linear Hash Map file. The main function is not being tested and it is there as an option for you to use for your own testing / running.

import java.util.Collections; import java.util.List; import java.util.ArrayList; public class LinearHashMap implements Map private static class HashMapEntry implements Entryck, V> private K key; private V value; public HashMapEntry (K key, V value) [ this.keykey; this.valuevalue; @Override public K getKey (O return key @Override public V getValue) return value