Hashtabelle

[Guest]

Hallo,
ich habe folgene Aufgabe bekommen, und weiß leider gar nicht wie ich das anfangen soll.
Vielleicht kann mir jemand ein bisschen weiterhelfen!


Schreiben Sie eine Klasse DHSimpleHashSet, die eine Menge von Objekten mittels einer Hashtabelle (mit double hashing) verwaltet. Ihre Klasse soll zumindest die folgenden Methoden aufweisen:

/**
* Fügt das angegebene Objekt in diese Menge ein.
* Falls es bereits enthalten war, bleibt die Menge unverändert.
* @return true falls das Objekt vorher nicht enthalten war;
* false falls das Objekt nicht eingefügt wurde,
* da es bereits enthalten war.
*/
public boolean add(Object o);

/**
* 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);

(Schreiben Sie ein Hauptprogramm, um Ihre Klasse zu testen. )
[/i]

 

[Roar]

wir machen keine hausuafgaben. hast du keinen ansatz?

 

[bambi]

Noe, die komplette Hausaufgabe macht Dir hier keiner. (Hoffe ich jedenfalls fuer Dich, denn das bringt
Dir rein gar nichts... Sollst ja was lernen :wink: )
Du solltest Dir aber mal die Methoden containsValue() und put() von Hashtable in der API ansehen. Wenn Du
dann Probleme hast, kannst Du Dich ja melden (Code posten nicht vergessen). Da hilft Dir dann ganz sicher
jemand.

 

[Guest]

Habe bis jetzt fogenden code: (noch unvollständig und fehlerhaft...ich weiß)

public class DHSimpleHashSet {


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

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

    public boolean contains(Object o) {
        int tabellenplatz = Math.abs(o.hashCode() % hashtabelle.length);
        return(o.equals(hashtabelle[tabellenplatz])) {
           
    }

    public boolean add(Object o) {
        int tabellenplatz = Math.abs(o.hashCode() % hashtabelle.length);
        if (hashtabelle[tabellenplatz] != null) {
            tabellenplatz = tabellenplatz + 1;
            return false;
        } 
        else {
          hashtabelle[tabellenplatz] = o; 
          return true;   
        }

    }

 }

habe folgende Fagen:
1. contains....wie geh ich weiter vor wenn ich auch noch die nachstehenden tabellenplätzte nach dem objekt durchsuchen will?
2. add.....ich soll zuerst teste ob das Objekt das eingefügt werden soll schon vorhanden ist. Soll ich hier contains anwenden und wenn ja wie?

 

[dark_red]

Hmm... ich dachte du sollst etwas mit Hashtables machen... ?

 

[bambi]

Eine kleine Hilfe:

public class Test
{
        /** Die Hashtable, in dem die Objekte gespeichert werden. */
        private Hashtable hashtabelle;

        /** Konstruktor. */
        public Test() {
             // Objekt initialisieren...
            hashtabelle = ...
        }

        public boolean contains(Object o) {
            // sieh' mal in die API da gibt's auch was mit "contains..."
        }

        public boolean add(Object o) {
            
            if (//Deine contains-Methode kannst Du hier verwenden) {
                ...
            }  else {
                ... // Objekt einfuegen - in die API sehen...
            }
        }
    }

Das sollte Dir auf jeden Fall erst mal weiterhelfen. Wenn Du noch Probleme haben solltest... Melden! :wink:

 

[kopfsalat]

habe folgende Fagen:
1. contains....wie geh ich weiter vor wenn ich auch noch die nachstehenden tabellenplätzte nach dem objekt durchsuchen will?
2. add.....ich soll zuerst teste ob das Objekt das eingefügt werden soll schon vorhanden ist. Soll ich hier contains anwenden und wenn ja wie?

1. Beim Double Hashing wird doch zunächst der Einsprungspunkt bestimmt (bei dir 'tabellenplatz'). Wenn dieser belegt ist, ist normalerweise eine zweite Hashfunktion für die Berechnung eines Offsets zuständig, mit diesem man dann solange durch den Table springt, bis man entweder das gesuchte Element gefunden hat, oder die Position leer ist. Diese zweite Hashfunktion hast einfachheitshalber mit schlicht '+1' in deiner Methode add implementiert. Dieselbe musst Du nun auch in contains übernehmen.
Also contains:
- schaue, ob an Stelle tabellenplatz das gesuchte Objekt liegt,
- wenn nicht, springe solange um 1 weiter (modulo length), bis der aktuell geprüfte Platz leer ist, oder das gesuchte Objekt dort ist.

Also sowas in der Richtung in contains:

        while (hashtabelle[tabellenplatz] != null) {
            tabellenplatz = (tabellenplatz + 1) % hashtabelle.length; // besser als immer +1 wäre hier Wert einer 2. Hashfunktion
            return false;
        }

2. bzgl. add inkl. check auf contains:
- prüfe zunächst auf contains. Wenn Element bereits enthalten, dann füge Element nicht hinzu.
- wenn Element nicht enthalten, dann ist aktuell getestete Position ja leer, dann schreibe das zuzufügende Element hin.

Du könntest bei add einfach die contains-Methode nochmal implementieren, oder aber, ggf. etwas eleganter, rufe zu beginn von add() die contains-Methode auf. Diese füttert zum Ende eine Objektvariable FreierTabellenPlatz mit dem aktuellen Wert tabellenplatz, der ja nun auf eine leere Stelle zeigt.
Diese Objektvariable FreierTabellenPlatz kann dann im Fall, dass contains false liefert, als Punkt genutzt werden, um das Element einzufügen.

Hoffe, das ist so verständlich...