Objekt aus Hash-Tabelle löschen

[Flummi]

Hallo, ich hab folgendes Problem: Ich soll aus einer Hash-Tabelle ein Objekt löschen. Ich hab den zugehörigen Code auch schon geschrieben, aber irgendetwas haut nicht so hin, wie ich mir das vorgestellt hab. Könnte sich jemand mal anschauen, wo der Fehler liegt, ich finde ihn nämlich nicht. Danke.

Wann man das ausprobiert, mit 7 als Tabellenlänge und den Werten 23, 15, 19 und 16, also:

java TestApp 7 23 15 19 16

Dann sollte die Hash-Tabelle so aussehen:

[_][15][23][16][_][19][_]

23 und 16 haben den selben Hash-Wert, aber da der Platz 2 schon von 23 belegt ist, kommt 16 auf den nächsten freien Platz.

DHSimpleHashSet.java

public class DHSimpleHashSet {

	/** Das Feld, in dem die Objekte gespeichert werden.  */
	private Object[] hashtabelle;

	/** Konstruktor.  */
	public DHSimpleHashSet(int size) {
		hashtabelle = new Object[size];   /*legt Feld mit size Platzen an*/
	}

// Methoden --------------------------------------------------------

	/**
	 * Fugt das angegebene Objekt in diese Menge ein.
	 * Falls es bereits enthalten war, bleibt die Menge unverandert.
	 * @return true  falls das Objekt vorher nicht enthalten war;
	 *         false falls das Objekt nicht eingefugt wurde,
	 *               da es bereits enthalten war.
	 */
	public boolean add(Object o) {
		// wo soll das Objekt im Idealfall hin
		int tabellenplatz = Math.abs(o.hashCode() % hashtabelle.length);
		
		if (hashtabelle[tabellenplatz] == null) {
			hashtabelle[tabellenplatz] = o;
			return true;
		}
		else {
			if (this.contains(o)) return false;

			for (int i = 0; i < hashtabelle.length; i++) {
				if (hashtabelle[tabellenplatz] == null) {
					hashtabelle[tabellenplatz] = o;
					return true;
				}
				else tabellenplatz++;
				
				// damit man, wenn man ueber die Tabellenlaenge hinauskommt, wieder bei 0 beginnt
				if (tabellenplatz > hashtabelle.length) tabellenplatz = 0;
			}
		}
		return false;
	}


	/**
	 * Gibt an, ob das angegebene Objekt in dieser Menge enthalten ist.
	 * @return true falls das Objekt in dieser Menge enthalten ist.
	 */
	public boolean contains(Object o) {
		int tabellenplatz = Math.abs(o.hashCode() % hashtabelle.length);
		if (hashtabelle[tabellenplatz] == o) return true;
		else {
			for (int i = 0; i < hashtabelle.length && hashtabelle[tabellenplatz] != null; i++) {
				if (hashtabelle[tabellenplatz].equals(o)) return true;
				else tabellenplatz++;
				
				// damit man, wenn man ueber die Tabellenlaenge hinauskommt, wieder bei 0 beginnt
				if (tabellenplatz > hashtabelle.length) tabellenplatz = 0;
			}
		}
		return false;	
	}


	/**
	 * Entfernt das angegebene Objekt aus dieser Menge, falls enthalten.
	 * @return true falls das Objekt vorher enthalten war.
	 */
	public boolean remove(Object o) {
		int hash_code = Math.abs(o.hashCode() % hashtabelle.length); //bei 23, hash_code = 2
		int tabellenplatz = hash_code;

		if (hashtabelle[tabellenplatz] == null) return false; //Objekt war nicht enthalten, bei 23 nicht der Fall

		if (hashtabelle[tabellenplatz].equals(o)) { //23 equals 23, also true
			int last_same_hash = tabellenplatz; //das letzte Mal, an dem eine Zahl gesehen wurde, mit dem selben Hash, ist die Zahl selbst
			for (int i = 0; i < hashtabelle.length && hashtabelle[tabellenplatz] != null; i++) { //1. Durchlauf true // 2.Durchlauf, false, denn nachdem auf 16 gezeigt wurde, zeigt man jetzt auf null
				if (Math.abs(hashtabelle[tabellenplatz].hashCode() % hashtabelle.length) == hash_code) last_same_hash = tabellenplatz; //1. Durchlauf: nochmal die selbe Zuweisung wie oben // 2. Durchlauf, jetzt ist 16 last_same_hash
				tabellenplatz++; // 1. Durchlauf: tabellenplatz ist jetzt 3, also die Zahl 16 // 2. Druchlauf: tabellenplatz ist 4, also null
				if (tabellenplatz > hashtabelle.length) tabellenplatz = 0;
			}
			hashtabelle[hash_code] = hashtabelle[last_same_hash]; // auf Platz 2 kommt jetzt 16, da 16 last_same_hash ist
			hashtabelle[last_same_hash] = null; // und auf 16, kommt null.
			return true; // fertig
		} else if (!hashtabelle[tabellenplatz].equals(o)) { //hier das ganze nochmal, nur dass nach dem Objekt, dass equals dem gesuchten ist, erstmal gesucht werden muss, falls der Platz vorher besetzt war.
			for (int i = 0; i < hashtabelle.length && hashtabelle[tabellenplatz] != null; i++) {
				if (!hashtabelle[tabellenplatz].equals(o)) tabellenplatz++;
				else {
					hash_code = tabellenplatz;
					int last_same_hash = tabellenplatz;
					for (int j = 0; j < hashtabelle.length && hashtabelle[tabellenplatz] != null; j++) {
						if (Math.abs(hashtabelle[tabellenplatz].hashCode() % hashtabelle.length) == hash_code) last_same_hash = tabellenplatz;
						tabellenplatz++;
						if (tabellenplatz > hashtabelle.length) tabellenplatz = 0;
					}
					hashtabelle[hash_code] = hashtabelle[last_same_hash];
					hashtabelle[last_same_hash] = null;
					return true;
				}
				if (tabellenplatz >= hashtabelle.length - 1) tabellenplatz = 0;
			}
		}
		return true;
	}
}

Es geht eigentlich nur um die Methode remove, aber damit man sieht, wie die Klasse arbeitet, ist sie hier gesamt.

Und hier ist das Programm, das testen soll, ob alles so läuft wie's laufen soll:

TestApp.java

public class TestApp {
	public static void main(String[] args) {

		DHSimpleHashSet hashtabelle = new DHSimpleHashSet(Integer.parseInt(args[0]));

		System.out.println("Adding Values:");
		for (int i = 1; i < args.length; i++) {
			if (hashtabelle.add(args[i])) System.out.println("\t" + args[i] + " ... OK");
			else System.out.println("\t" + args[i] + " ... FAILED");
		} System.out.println("");

		System.out.println("Searching Values:");
		for (int i = 1; i < args.length; i++) {
			if (hashtabelle.contains(args[i])) System.out.println("\t" + args[i] + " ... OK");
			else System.out.println("\t" + args[i] + " ... FAILED");
		} System.out.println("");

		System.out.println("Adding Values again:");
		for (int i = 1; i < args.length; i++) {
			if (hashtabelle.add(args[i])) System.out.println("\t" + args[i] + " ... OK");
			else System.out.println("\t" + args[i] + " ... FAILED");
		} System.out.println("");

		System.out.println("Searching Values:");
		for (int i = 1; i < args.length; i++) {
			if (hashtabelle.contains(args[i] + "_test")) System.out.println("\t" + args[i] + "_test" + " ... OK");
			else System.out.println("\t" + args[i] + "_test" + " ... FAILED");
		} System.out.println("");

		System.out.println("Removing Values:");
		for (int i = 1; i < args.length; i++) {
			if (hashtabelle.remove(args[i])) System.out.println("\t" + args[i] + " ... OK");
			else System.out.println("\t" + args[i] + " ... FAILED");
		}

		System.out.println("Searching Values:");
		for (int i = 1; i < args.length; i++) {
			if (hashtabelle.contains(args[i])) System.out.println("\t" + args[i] + " ... OK");
			else System.out.println("\t" + args[i] + " ... FAILED");
		} System.out.println("");

		System.out.println("Removing Values again:");
		for (int i = 1; i < args.length; i++) {
			if (hashtabelle.remove(args[i])) System.out.println("\t" + args[i] + " ... OK");
			else System.out.println("\t" + args[i] + " ... FAILED");
		}
	}
}

Könnt ihr mir sagen, was ich falsch mache?

danke,
Flummi.

[mehlvogel]

Ich hab den zugehörigen Code auch schon geschrieben, aber irgendetwas haut nicht so hin, wie ich mir das vorgestellt hab. Könnte sich jemand mal anschauen, wo der Fehler liegt, ich finde ihn nämlich nicht. Danke.

Das ist erstmal eine etwas schwammige Fehlermeldung. Was ist nicht so wie du dir das denkst? Ist das Element nach einem remove() noch vorhanden, oder was passiert?
Falls du es nicht explizit selbstprogrammieren muss sei hier der vollständigkeithalber auf das in Java integrierte HashSet verwiesen.

[Flummi]

Ich sags ja nur ungern, aber ich habe gerade den Fehler entdeckt.

if (tabellenplatz > hashtabelle.length - 1) tabellenplatz = 0;

das -1 hab ich vergessen *auf den Kopf hau*
jetzt geht alles.
Danke trotzdem,
mfg,
Flummi.