alternierendes Probing-Verfahren für Hash-Tabellen implementieren

[javarex]

Hallo zusammen,

ich habe eine HashTabelle zu entwerfen, in der key/value-Paare gespeichert sind. Die Klasse HashTable enthält ein zweidimensionales Array, in dessen "Unter-Arrays" als vorderes Element jeweils der key (table[][0]) und als hinteres Element jeweils der value (table[][1]) gespeichert wird. In welchem "Unter-Array" dieses key/value-Paar gespeichert wird, gibt der aus dem key errechnete hashWert an.

Unter anderem ist für die HashTable-Klasse eine Methode Object put(Object key, Object value) zu implementieren. Das übergebene key/value-Paar wird in der HashTable(HT) gespeichert. Es soll null zurückgegeben werden, wenn anfangs der Schlüssel noch nicht vorhanden war. Befand sich der Schlüssel schon mit einem anderen value in der HT, so wird der value überschrieben und der alte value returnt.

Zu Beginn muss ja die Position des keys (also das Bucket in der HT) festgelegt werden. Dies geschieht über den Hash-Wert. Befindet sich bereits ein key an der ermittelten Stelle, so mit einem Probingverfahren eine alternative Position gefunden werden. Der Nutzer kann wählen, ob dies via alternierendem Linearprobing (alternierender Linearsondierung) oder alternierendem QuadratProbing erfolgt.

Ich habe es zunächst mit dem LinearProbing versucht. Das Probing muss allerdings über die Methoden folgender Klasse erfolgen:

public class LinearProbing implements Probing {

    @Override
    public int nextNum() {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public void startProbing() {
        // TODO Auto-generated method stub
        
    }

}

Das alternierende Linearprobing soll bspw. so erfolgen:

h(a) = 27
falls 27 besetzt, ...27 –1*7 = 20
falls 20 besetzt, ...20 + 2*7 = 34
falls 34 besetzt, ...34 –3*7 = 13

Statt der 7 kann natürlich allgemein auch eine andere Zahl die Sprunggröße bestimmen.

Ich habe es trotzdem in der put-Methode mit der 7 zu Testzwecken durchgeführt, was meines Erachtens auch funktioniert.
Allerdings habe ich überhaupt keine Ahnung, wie ich dieses Verfahren mit den vorgegebenen Methoden umsetze, zumal diese ja keine Parameter entgegennehmen.

Hier der Auszug aus meiner HashTable-Klasse inklusive put-Methode:

public class HashTable {

    Object[][] table;
    int size;
    
    public Object put(Object key, Object value) {

        // überprüfen, ob key vom Typ StringElement ist
        if (key instanceof StringElement) {
            key = (StringElement) key;
        } else {
            throw new Exception("key muss vom Typ StringElement sein");
        }

        // überprüfen ob value String oder Song ist
        if (value instanceof String || value instanceof Song) {
        } else {
            throw new Exception("value muss vom Typ String oder Song sein");
        }

        // null zurückgeben, wenn Schlüssel noch nicht in der Hashtable gespeichert ist
        // Schlüssel wird mit seinem value eingetragen
        if (containsKey(key) == false) {
            
            //überprüfen, ob das Bucket noch leer ist, in diesem Fall wird das key-value Paar an dieser Stelle gespeichert
            if(table[key.hashCode()][0].equals(null)) {
            table[key.hashCode()][0] = key;
            table[key.hashCode()][1] = value;
            return null;
            }
            
            //mit Probing ein neues Bucket finden, falls am ermittelten Hashwert schon ein anderer key gespeichert ist
            //der Teil der im else-Block steht soll mit den Methoden der LinearProbing-Klasse implementiert werden
            else {
                int c = 7;
                int index=-1;
                int neuerHashwert = key.hashCode()+(index*c);
                while(!table[neuerHashwert][0].equals(null)) {
                    index=(Math.abs(index)+1)*-1;
                    neuerHashwert=index+c+key.hashCode();
                }
            
            //key-value-Paar an neu berechneter Stelle speichern
            table[neuerHashwert][0]=key;
            table[neuerHashwert][1]=value;
            
            return null;
            }
        }

        // der alte Wert wird zurückgegeben und der neue Wert wird eingetragen
        else {
            Object alterValue = get(key);
            
            //ist der zum key gehörige value unbedingt am Hashwert gespeichert?
            //wenn nicht: Probing
            table[key.hashCode()][1] = value;
            return alterValue;
        }
    }

Ich zerbreche mir schon seit 2 Stunden über diese Aufgabe, komme aber einfach nicht weiter.

Ich wäre sehr dankbar, wenn mir jemand eine Hilfestellung gibt.

Vielen Dank im Voraus!