Allgemeine Hashtabelle - wie?

[Xyarvius]

Hallo,
ich möchte gerne folgendes Problem lösen:
Man implementiere eine allgemeine Hashtabelle, die
• komplett unabhängig von den gespeicherten Daten implementiert ist,
• geschlossenes Hashing zur Konfliktauflösung verwendet,
• doppelt hasht und
• auf eine Suchanfrage mehrere Ergebnisse zurückliefern kann

Letztlich soll das dann genutzt werden um eine Reihe, in einem Array vorliegernder, Objekte (in diesem Fall Fußballspieler), bestehend aus zwei String-Variablen (Name des Spielers und Verein) in zwei Hashtabellen einzuordnen (einmal nach Name und einmal nach Verein gehasht). Zusätzlich soll dann eine Funktion vorliegen der ein Spielername übergeben wird und die einem dann mittels der beiden Tabellen alle Spieler ausgibt, die im gleichen Verein spielen, wie dieser Spieler.

Meine Basis für die Fußballspieler sieht so aus:

public class Player {
    protected String name;
    protected String club;
  
    public Player(String name, String club) {
        this.name = name;
        this.club = club;

    public String getName() {
        return name;
    }
    public String getClub() {
        return club;
}

public class Euro2008 {
    public static Player[] allTeamPlayer = {
        new Player("Diego Benaglio", "VfL Wolfsburg"),
        //und noch 367 andere Spieler
        };
}

Wo es jetzt bei mit hapert ist:
Wie bastle ich eine Funktion, die jeden beliebigen Datenwert in meine Tabelle einordnen kann?
Angenommen ich wüsste, dass ich in meine Hashtabellen ausschließlich meine Fußballspieler-Objekte einordne (was ich letztlich ja auch tue, aber die Anforderungen sind nun mal anders), dann würde ich mir einfach den Anfangsbuchstaben des Spielers/Clubs nehmen, davon den Ascii-Wert ermitteln, also grob etwa so:

int key = (int) Euro2008.allTeamPlayer[0].getName().charAt(0);

und danach dann mittels der Hashfunktion (oder bei Kollision mit der Sondierungsfunktion) in die Tabelle einordnen.

Aber wenn das völlig unabhängig des der gespeicherten Daten sein soll? Puh, wie könnte man das lösen? Ich brauche doch letztlich immer einen int-Wert, also den Schlüssel, den ich dann in meiner Hashfunktion verwende um die Stelle des zu speichernden Objekts in der Hashtabelle zu ermitteln. Die Hash-Funktionen der Java-Klassenbibliothek darf ich nicht nutzen.

Vielleicht habe ich dann noch andere Fragen, aber ich will erstmal diese Sache verstehen.
Danke

 

[JCODA]

Aber wenn das völlig unabhängig des der gespeicherten Daten sein soll? Puh, wie könnte man das lösen? Ich brauche doch letztlich immer einen int-Wert, also den Schlüssel, den ich dann in meiner Hashfunktion verwende um die Stelle des zu speichernden Objekts in der Hashtabelle zu ermitteln. Die Hash-Funktionen der Java-Klassenbibliothek darf ich nicht nutzen.

Ich verstehe die Aufgabe so, dass du Generics verwenden sollst, um deine HashTable zu implementieren.
Die Hashfunktion ist "Teil" der Daten, meiner Meinung nach.

 

[Xyarvius]

Hallo JCODA,

danke für deine Antwort. Ich bin gerade dabei, mich über Generics zu informieren, damit ich das in der Aufgabe anwenden kann.
Mein bisheriger Code (noch ohne Generics und Suchfunktion) sieht so aus:

/**
 * Die Klasse enthält Funktionen um Objekte in eine Hashtabelle einzutragen, insbesondere Player-Objekte.
 */
public class emHashing {
    /**
     * Die Funktion fügt ein Objekt mit zugehörigem Schlüssel in eine Hashtabelle ein.
     * @param k Schlüssel des einzufügenden Objektes
     * @param object Das einzufügende Objekt
     * @param hashTable Die Hashtabelle in der das Objekt eingefügt werden soll
     */
    public static void hashTableInsert (int k, Object object, Object[] hashTable){
        //Die Größe des übergebenen Arrays
        int m = hashTable.length;
       
        //Die Zählvariable für die Sondierungsfunktion
        int i = 0;
       
        //Die primäre Hashfunktion
        int hashPrim = k % m;
       
        //Die sekundäre Hashfunktion
        int hashSek = 1 + (k % (m - 2));
       
        /*Die Schleife versucht so lange das Objekt an der von der Sondierungsfunktion berechneten Stelle einzufügen,
        bis eine freie Stelle gefunden wurde (hashTable[hashSond]==null) oder die Hashtabelle voll ist (i==m)*/
        while (true){
            //Die Sondierungsfunktion
            int hashSond =(hashPrim + (i*hashSek))% m;
           
            //Prüft, ob die Stelle noch frei ist und fügt in dem Falle das Objekt an der Stelle ein und bricht ab
            if (hashTable[hashSond]==null){
                hashTable[hashSond] = object;
                break;
            // Ansonsten wird die Zählervariable erhöht und überprüft ob die Tabelle voll ist und bricht in diesem Falle ab
            } else {
                i++;
                if (i==m){
                    System.err.println("Fehler: Die Hashtabelle ist voll. Das Objekt konnte nicht eingefügt werden");
                    break;
                }
            }
        }
    }
   
    /**
     * Die Funktion berechnet den Schlüssel eines Playerobjektes anhand des ersten Buchstaben des Namens.
     * @param player Das Player-Objekt dessen Schlüssel berechnet werden soll
     * @return Der berechnete Schlüssel
     */
    public static int getNameKey (Player player){
        return (int) player.getName().charAt(0);
    }
   
    /**
     * Die Funktion berechnet den Schlüssel eines Playerobjektes anhand des ersten Buchstaben des Vereins.
     * @param player Das Player-Objekt dessen Schlüssel berechnet werden soll
     * @return Der berechnete Schlüssel
     */
    public static int getClubKey (Player player){
        return (int) player.getClub().charAt(0);
    }
   
    public static void main(String[] args) {
        //Größe des Arrays in Euro2008
        int playerCount = Euro2008.allTeamPlayer.length;
        //Größe der beiden Hashtabellen
        int m = 499;
        //Erstellen der beiden Hashtabellen, eine für die Namen, die andere für die Vereine
        String [] hashTableNames = new String [m];
        String [] hashTableClubs = new String [m];
        //alle Spielernamen-Strings in die Hashtabelle für Namen und alle Vereins-Strings in die Hashtabelle für Vereine einfügen
        for (int i=0; i<playerCount; i++){
            hashTableInsert(getNameKey(Euro2008.allTeamPlayer[i]),Euro2008.allTeamPlayer[i].getName(), hashTableNames );
            hashTableInsert(getClubKey(Euro2008.allTeamPlayer[i]),Euro2008.allTeamPlayer[i].getClub(), hashTableClubs );
        }
        //beide Hashtabellen anzeigen
        System.out.println("Hashtabelle - Spielernamen");
        for (int j=0; j<m; j++){
            System.out.println(j + " - " + hashTableNames[j]);
        }
        System.out.println("Hashtabelle - Vereine");
        for (int j=0; j<m; j++){
            System.out.println(j + " - " + hashTableClubs[j]);
        }
    }
}

Als Laie habe ich sicher sehr viele unschöne Sachen da verzapft, also bitte verbessert mich, wo ich Quatsch gemacht habe.

Was mir erst mal aufgefallen ist, dass ich je nachdem wie groß ich meine Hashtabellen mache, ich nicht alle Spieler/Vereine in die Hashtabellen bekomme.
Ich habe 368 Player-Objekte im allTeamPlayer-Array.
Mache ich die beiden Hashtabellen 499 Einträge groß, können alle Spieler und Vereine eingetragen werden.
Mache ich sie aber 500 Einträge groß, bekomme ich bei einigen Spielern/Vereinen die Meldung, dass die Hashtabelle voll ist (was sie natürlich nicht ist).

Also müssen sich bei Berechnung der Werte von der Sondierungsfunktion Werte wiederholen. Wo liegt da der oder die Fehler?

 

[chemical201]

Hallo Xyarvius,

Kannst du deine Quellcode teilen?
Ich habe auch dieselbe Aufgabe als Übung bekommen komme aber damit nicht ganz klar.

Danke im voraus

 

[mihe7]

Meine erste Frage wäre, ob man den Schlüssel zu den "gespeicherten Daten" zählt oder anders formuliert, ob es möglich sein muss, für den Schlüssel beliebige Objekte zu verwenden?