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 Entry {

private K key;

private V value;

public HashMapEntry(K key, V value) {

this.key = key;

this.value = value;

}

@Override

public K getKey() {

return key;

}

@Override

public V getValue() {

return value;

}

public void setKey(K key) {

this.key = key;

}

public void setValue(V value) {

this.value = value;

}

}

private static final int DEFAULT_CAPACITY = 16;

// Use this entry to signify defunct cells.

private final HashMapEntry DEFUNCT = new HashMapEntry(null, null);

// The entry table

private List> entries;

// Actual number of entries in map

private int numberOfEntries;

public LinearHashMap() {

entries = new ArrayList<>(Collections.nCopies(DEFAULT_CAPACITY, null));

numberOfEntries = 0;

}

private int hash(K key) {

int h = key.hashCode() % entries.size();

if (h < 0) {

h += entries.size();

}

return h;

}

// Resizes the table to double its prior capacity.

private void ensureCapacity() {

// Won't be tested, but we encourage you to attempt to implement this!

}

@Override

public int size() {

// TODO: Implement this.

return numberOfEntries;

}

@Override

public boolean isEmpty() {

// TODO: Implement this.

if(numberOfEntries == 0){

return true;

}else{

return false;

}

}

@Override

public boolean containsKey(K key) {

// TODO: Implement this.

return false;

}

@Override

public V get(K key) {

// TODO: Implement this.

return null;

}

@Override

public void put(K key, V value) {

// TODO: Implement this.

}

@Override

public V remove(K key) {

// TODO: Implement this.

return null;

}

public static void main(String[] args) {

/* This is here for you to optionally use for your own

* testing / running. This method will NOT be tested.

*/

System.out.println("Running the main method in LinearHashMap.java");

}

}