HashValue abspeichern und referenzieren?

[FrazeColder]

Guten Tag Community,

Ich habe da ein Problem...
Ich habe soweit die Aufgabe fertig, solange ich nicht mehr als zwei mal auf ein nächstes Feld referenzieren muss...
Wir sollen, falls der HashValue schon vorhanden ist, auf das nächst freie Feld referienzieren.
Doch wie kann ich solange durchchecken, ob dieses Feld auf das schon referenziert wurde, nicht weiter referenziert und von da dann meine neue Referenz setzen?

Key = Deutsche Wort und Value = Englisches Wort.
Soll eine Art Wörterbuch werden.

package Hashtabelle;

public class HashTabelle {

	private Datensatz[] daten;
	private int ordnung;

	public HashTabelle(int kapazitaet, int ordnung) {
		this.ordnung = ordnung;
		this.daten = new Datensatz[kapazitaet];
	}

	private int getHashValue(String key) {

		char[] temp = key.toCharArray();

		int h = 0;
		int n = ordnung;
		for (int i = 0; i < temp.length; i++) {
			h = (h * 256 + temp[i]) % n;

		}
		
		if(h > daten.length){
			int[] newArray = new int[h];
			daten.clone();
		}
		
		return h;
	}

	private Integer getFreeIndex(int belegterIndex) {

		if (daten[belegterIndex] == null) {
			return belegterIndex;
		} else {
			while (daten[belegterIndex] != null) {
				belegterIndex++;
			}
			return belegterIndex;
		}
	}

	public boolean set(String key, String value) { // value == englisches Wort;	// key == deutsches Wort
		
		Integer hashValue = getHashValue(key);

		if (daten[hashValue] == null) {
			daten[hashValue] = new Datensatz(key, value, null);
			return true;
		} else {
			int nextFreePos = getFreeIndex(hashValue);
			daten[hashValue].setReferenz(nextFreePos); //HIER MUSS ICH WAS ÄNDEN!!!
			daten[nextFreePos] = new Datensatz(key, value, null);
			return true;
		}
	}

	public String getValueForKey(String key) {
		if (key.compareTo(daten[getHashValue(key)].getKey()) != 0) {
			Integer newHasValue = daten[getHashValue(key)].getReferenz();
			String value = daten[newHasValue].getValue();
			return value;
		}
		return daten[getHashValue(key)].toString();
	}

	public String toString() {
		for(int i = 0; i < daten.length; i++){
			if(daten[i] == null){
				i++;				
			}else{
				System.out.println(daten[i].toString());
			}
		}
		return null;
	}

}

MfG und Danke

 

[e_Lap]

normalerweise passt man die Hashfunktion an, wenn das Feld bereits belegt ist. Jagt den Wert durch die neue Hashfunktion und schaut sich das entsprechende Feld an. Solange bis ein freies gefunden wurde. Hierbei musst du das Array entsprechend vergrößern. Normalerweise *2.
Alternativ pro Feld eine Liste mit den Values verwalten.

 

[FrazeColder]

Ist halt die Aufgabe... -.-

Bin mittlerweile hier und komme immer noch nicht weiter...

	public boolean set(String key, String value) { // value == englisches Wort;	// key == deutsches Wort
		
		Integer hashValue = getHashValue(key);

		if (daten[hashValue] == null) {
			daten[hashValue] = new Datensatz(key, value, null);
			return true;
		} else {
			if(key.compareTo(daten[hashValue].getReferenz()) != 0){
				
			}
			Integer nextFreePos = getFreeIndex(hashValue);
			
			if(daten[hashValue].getReferenz() != null){
				daten[hashValue].setReferenz(nextFreePos); 
				daten[nextFreePos] = new Datensatz(key, value, null);
			}else{
				Integer vorgaengerRef;
				Integer aktuellerRef;
				
				while(daten[aktuellerRef].getReferenz() != null)
					vorgaengerRef = daten[aktuellerRef].getReferenz();
					aktuellerRef = daten[vorgaengerRef].getReferenz();
					
				
				daten[vorgaengerRef].setReferenz(aktuellerRef); 
				daten[nextFreePos] = new Datensatz(key, value, null);
				
			}
			
			return true;
		}

 

[Spider11]

Vlt hast du es schon selbst gelöst, aber

Integer vorgaengerRef;
Integer aktuellerRef;

while(daten[aktuellerRef].getReferenz() != null)
	vorgaengerRef = daten[aktuellerRef].getReferenz();
	aktuellerRef = daten[vorgaengerRef].getReferenz();

Sieht strange aus.. aktuellerRef wird nicht initialisiert, also auf was soll daten[aktuellerRef] zeigen?
In der Schleife wird a) nur die erste Zeile ausgeführt, weil die geschweiften Klammern fehlen und b) müsstest du zu dem freien Index kommen. Hier siehts so aus, als ob du rückwärts gehst. Also von der letzten zur aller ersten Referenz, was mMn nicht viel Sinn ergibt. Du willst schließlich den 'Zeiger' von der letzten Referenz zum freien Index erstellen: HashValue1 -> HashValue2 -> nextFreePosition; dein Code macht gerade: HashValue2 -> HashValue1 -> Null? (Außer du meinst mit Vorgänger eigentlich den Nachfolger )

Edit: ein Problem ist hier auch, wenn daten[vorgaengerRef].getReferenz(); null zurückgibt, dann wird eine NullPointerException in der Bedingung von der while Schleife geworfen. Also bei der Funktion getReferenz mal schauen, ob der 0 oder null zurückgibt.

Edit2:

if(daten[hashValue].getReferenz() != null)

müsste eigentlich == sein. Bei der ersten Kollision hat man schließlich noch keine Referenz


Ansonsten Anregungen, die du gern überlesen darfst und nicht als böse Kritik aufgefasst werden sollen
-getFreeIndex kann man noch bissl schöner machen, ohne dem ersten if/else
-kein deutsch/englisch mischen (am besten gleich nur englisch). setReferenz oder daten[hashValue] etc. ist einfach nicht schön (wenn das von der Aufgabenstellung so vorgegeben wurde, also die Klassen Datensatz usw. dann den Lehrer anhauen )


So würd ichs machen (ohne die Implementierung von get und setReferenz zu kennen, aber ich vermute das sind einfache getter/setter Methoden ohne Logik (getReferenz gibt null zurück, wenn nichts gesetzt ist).

Integer ref = hashValue;

while(daten[ref].getReferenz() != null)
	ref = daten[ref].getReferenz();

daten[ref].setReferenz(nextFreePos); 
daten[nextFreePos] = new Datensatz(key, value, null);

Kann man schöner machen mit einem daten[].hasReference o.ä. aber sollte funktionieren. Integer anstatt int deshalb, da man sonst nicht auf null prüfen könnte. Hängt aber davon ab, was man von getReferenz zurück bekommt, wenn keine Referenz gesetzt wurde.