Hash implementieren

[Lukases2]

Hallo!

Aufgabe
Am 24. Juli 2015 findet die Klausur statt. Leider ist der Raum zu klein und Sie müssen in Schichten schreiben. Der uns zur Verfügung stehende Raum hat M = 27 Plätze, nummeriert von 0 bis 26. Zugewiesen werden Sie per Hashing über die Quersumme QS(n) der letzten drei Stellen Ihrer Matrikelnummer n. Wird eine Teilnehmende einem Platz zugeordnet der bereits belegt ist, muss sie warten bis ihre Vorgängerin die Klausur abgeschlossen hat. Helfen Sie uns bei der Zuteilung!

Implementieren Sie in ExamTable.java eine Hashtabelle mit Verkettung. Nutzen Sie die hasher.hash(T) Methode, um den Hash eines Objektes zu berechnen.

Folgenden Code habe ich bekommen

package bP;

import java.security.GeneralSecurityException;
import java.util.Iterator;
import java.util.Random;
import java.util.NoSuchElementException;

public class ExamTable<T> {
	public interface Hasher<T> {
		// Berechnet den Hash eines Elements
		// Man beachte, dass die "modulo Tabellengröße" Operation
		// bereits von der Hashtabelle an sich durchgeführt werden sollte.
		public int hash(T object);
	}

	public static class Position {
		// Fach, in dem sich ein Element befindet
		private final int bucket;
		// Index innerhalb eines Eimers, an dem ein Element liegt
		private final int index;

		public Position(int bucket, int index) {
			this.bucket = bucket;
			this.index = index;
		}

		public int getBucket() {
			return bucket;
		}

		public int getIndex() {
			return index;
		}
	}

	private Hasher<T> hasher;

	// Benutzt T.hashCode() um den Hash zu berechnen
	public ExamTable(int capacity) {
		this(capacity, new Hasher<T>() {
			@Override
			public int hash(T object) {
				return object.hashCode();
			}
		});
	}

	// Benutzt eine beliebige Funktion, um den Hash zu berechnen
	public ExamTable(int capacity, Hasher<T> hasher) {
		this.hasher = hasher;
		
	}
	
	// Fügt ein Element in die Hashtabelle ein
	// Man beachte, dass Elemente an das Ende des Faches angefügt werden sollen!
	// Gibt die Position zurück, an der sich das Element nun befindet!
	public Position add(T object) {
		// bitte implementieren Sie diese Methode!
		return null;
	}

	// Gibt die Position eines Elements innerhalb der Hashtabelle zurück.
	// Gibt null zurück, wenn das geforderte Element nicht existiert
	// Hinweis: Diese Methode ist nicht Teil des Interfaces
	// einer gewöhnlichen Hash-Tabelle, wie z.B. java.util.HashSet,
	// wird aber für die Aufgabenstellung benötigt.
	public Position findIndex(T object) {
		// bitte implementieren Sie diese Methode!
		return null;
	}

	// Überprüft, ob ein Element in der Tabelle existiert
	public boolean contains(T object) {
		return findIndex(object) != null;
	}

	// Entfernt ein Element aus der Hashtabelle
	// Wirft eine NoSuchElementException, wenn das geforderte Element nicht
	// existiert
	public void remove(T object) {
		// bitte implementieren Sie diese Methode!
	}

	public static void testHashTable() {
		System.out.println("Testing hash table");

		int num_elems = 15;
		int range = 100;

		Random random = new Random();

		System.out.print("Sequence: ");
		int[] sequence = new int[num_elems];
		for (int i = 0; i < num_elems; i++) {
			int element = random.nextInt(range);
			sequence[i] = element;
			if (i > 0)
				System.out.print(", ");
			System.out.print(element);
		}
		System.out.println();

		ExamTable<Integer> table = new ExamTable<Integer>(5);

		for (int i = 0; i < num_elems; i++)
			table.add(sequence[i]);

		for (int i = 0; i < num_elems; i++)
			if (!table.contains(sequence[i]))
				throw new RuntimeException("Element " + sequence[i]
						+ " is not in the hash table");

		for (int i = 0; i < num_elems; i++)
			table.remove(sequence[i]);

		for (int i = 0; i < num_elems; i++)
			if (table.contains(sequence[i]))
				throw new RuntimeException("Element " + sequence[i]
						+ " should have been removed");

		System.out.println("Hash table seems to work!");
	}

	// Berechnet die Belegung und gibt sie auf der Konsole aus.
	// num_seats ist die Anzahl der Sitzplätze in der Klausur und
	// der Iterator erwährt Zugriff auf die Matrikelnummern.
	public static void allocateExam(int num_seats, Iterator<Integer> iterator) {
		// bitte implementieren Sie diese Methode!
	}
	
	public static void main(String[] args) {
		testHashTable();
		
		class IdIterator implements Iterator<Integer> {
			private Random random;
			private final int minRange;
			private final int maxRange;
			private int remaining;

			IdIterator(int count, Random random, int min_range, int max_range) {
				this.remaining = count;
				this.random = random;
				this.minRange = min_range;
				this.maxRange = max_range;
			}

			@Override
			public boolean hasNext() {
				return remaining > 0;
			}

			@Override
			public Integer next() {
				if (remaining <= 0)
					throw new NoSuchElementException();
				remaining--;
				return random.nextInt(maxRange - minRange) + minRange;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		}
		;

		int num_students = 200;
		int table_size = 27;
		int min_range = 1000000;
		int max_range = 9999999;

		Iterator<Integer> iterator = new IdIterator(num_students, new Random(
				4711), min_range, max_range);
		allocateExam(table_size, iterator);
	}
};

Meine Idee
Mir fehlt leider noch der Ansatz. In diesem Aufgabenteil (es gibt auch noch eine b) und eine c) ) soll ich ja eine Hashtabelle implementieren, d.h. eine neue erstellen. Heißt das, dass ich die Methode

public Position add(T object) {
		// bitte implementieren Sie diese Methode!
		return null;
	}

zunächst implementieren soll, oder ist die Methode

public ExamTable(int capacity, Hasher<T> hasher) {
		this.hasher = hasher;

		// bitte implementieren Sie den Rest dieser Methode!
	}

gemeint?

Welche Methoden kann ich hier für was verwenden?