Hi,

wir sollen eine Hashtabelle implementieren, die die Objekte je nach ihrem Schlüsselwert an einer bestimmten Stelle im Speicher ablegt. Wenn man dann ein Objekt sucht, guckt man an der Stelle im Speicher, wo das Objekt seinem Schlüsselwert zufolge liegen müsste.

Schön und gut, aber in Java hab ich doch gar keinen Einfluss darauf, wo etwas im Speicher abgelegt wird. Wie kann ich das beeinflussen?

Ich bin ziemlich ratlos bei der Aufgabe und wäre für einen Tipp dankbar.

Du verwendest einfach ein Array, dessen Elemente Listen sind. Ich glaube, bei der Aufgabe gibt es bereits eine vorgegebene Klasse, welche eine Liste von Strings realisiert.

private StringList[] hash; // Exemplarvariable

…

hash = new StringList[groesse]; // im Konstruktor initialisieren

Mit "Stelle im Speicher" ist dann einfach ein Index gemeint, mit dem man das Array indiziert.

int index = magischeFunktion(wort);

hash[index] ist dann die Liste, wo Du das Wort hinzufügst, wo Du nachschaust, wo Du löschst etc.

Ansonsten: http://de.wikipedia.org/wiki/Hashtabelle

Hi,

dake für die schnelle Antwort.
Wenn ich den Hashcode als Schlüssel nehme, wären doch alle int-Zahlen als Schlüsselwert möglich. Das sind etwa 4 Milliarden soweit ich weiß. Ich kann doch aber schlecht ein Array mit 4 Mrd. Einträgen anlegen, oder?

Das ist richtig! Dann musst Du einfach den Modulo Operator (Divisionsrest) verwenden, um das ganze "zurechtzubiegen":

x % groesse

Das gibt Dir immer eine Zahl zwischen 0 und groesse-1.

Achso, oder ist es so gemeint, dass ich zB ein Array mit 4000 Einträgen anlege, und den Hashcode dann durch 10^6 teile, so dass ich dann aus 4 Mrd. möglichen Schlüsseln nur noch 4000 mache?
Und im Array sind dann jeweils "Buckets", die die Elemente aufnehmen?

Beim Aufgabenzettel 2, Aufgabe 2 sollen dann Bücher in der Hashtabelle gespeichert werden. Sollen die Bücher als String gespeichert werden (also zb "Autor";"Titel";…), oder sollen die Buckets schon Objekte vom Typ Buch enthalten? Wenn die Bücher nicht als String sondern als Buch gespeichert werden sollen, können die Buckets ja keine StringLists sein, sondenr müssten entweder Arrays von Büchern sein (dann wäre die Anzahl allerdings beschränkt), oder man verwendet zB Hashsets, aber das ist vielleicht auch nicht gerade Sinn der Sache, oder?

Ach so, wir sind bei P3 und nicht SE1 [img]http://www.fb18.de/gfx/7.gif[/img]

Dann sind es wohl schon Buch-Objekte. Aber die haben mit Sicherheit auch eine hashCode() Methode (schliesslich wird die ja von Object geerbt), die muss ggf. nur noch sinnvoll implementiert werden.

Also verwende dann eine Array von Listen von Buch. Klar?

Achso, oder ist es so gemeint, dass ich zB ein Array mit 4000 Einträgen anlege, und den Hashcode dann durch 10^6 teile, so dass ich dann aus 4 Mrd. möglichen Schlüsseln nur noch 4000 mache?
Und im Array sind dann jeweils "Buckets", die die Elemente aufnehmen?

Ist im Prinzip beides richtig, ich würde aber lieber den Modulo Operator verwenden. Das verteilt sich dann besser oder so.

Okay, das ist soweit klar.

Wenn ich eine Liste mit Buch-Objekten alege, ist es der Liste ja erstmal ganz egal, was drin ist, weil sie ja alles als Objecst behandelt.
Ist es egal, was für eine Liste ich dafür nehme? Ist eine ArrayList okay? Eine "allgemeine" Liste kann man ja nicht nehmen, weil List ja nur ein Interface ist.

List[] hash = new List[groesse];
Die einzelnen Array-Elemente musst Du dann noch einzeln initialisieren, die sind noch null:
for (int k=0; k<groesse; k++) { test[k] = new ArrayList(); }

Okay, alles klar. Sollte jetzt was werden.

Vielen Dank!

Ach ja und falls Du Generics verwenden möchtest,

List<Buch>[] hash = new List<Buch>[groesse];

dann bekommst Du einen "generic array creation" error. Also entweder ohne Generics programmieren oder anstatt einem Array von Listen von Buch einfach eine ArrayList von Listen von Buch verwenden. Dann klappt der Indexzugriff allerdings nicht mehr über die gewohnten eckigen Klammern sondern über die entsprechenden Operationen von ArrayList.

Hatten wir damals Hashmaps nicht mit Hilfe von Baumstrukturen implementiert, da sie sequentielle Suche in den Überlaufbehältern den Geschwindigkeitsvorteil der Map zunichte macht?

Da die Anzahl der Elemente in einer Hash-Tabelle immer kleiner sein sollte als die Grösse des Arrays kann man davon ausgehen, dass in jedem Überlaufbehältern nicht mehr als ein paar Elemente drin sein werden. Von daher ist die sequentielle Suche völlig in Ordnung.

Ach ja und falls Du Generics verwenden möchtest,

List<Buch>[] hash = new List<Buch>[groesse];

dann bekommst Du einen "generic array creation" error. Also entweder ohne Generics programmieren oder anstatt einem Array von Listen von Buch einfach eine ArrayList von Listen von Buch verwenden. Dann klappt der Indexzugriff allerdings nicht mehr über die gewohnten eckigen Klammern sondern über die entsprechenden Operationen von ArrayList.

List<Buch>[] hash = new List[groesse];

dann klappts auch mit den generics ;)

Note: Test.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Nach einer sauberen Lösung klingt das aber nicht gerade…

ist aber leider die einzige… in den java klassen (z.b. ArrayList, HashMap) wirds genauso gemacht..
- und die Warnung kommt z.b. auch beim Cast von Objekt auf ArrayList<Irgendwas>. Wenn man nun aber weiss, dass dieses Object vom Typ ArrayList<Irgendwas> ist, ist es ja nicht weiter gefählich. (Und ohne solche Casts kommt man nunmal nicht aus)

Zitat:
"Eine Hashtabelle ist eine Abbildung von Schlüsselwerten auf Datenwerte, wobei jeder Schlüssel nur (maximal) einmal vorkommt, d.h., jeder enthaltene Schlüssel zeigt auf genau einen Datensatz"


Ich frag mich obs bei der Aufgabe auch Schlüssel auf eine Liste von Büchern zeigen darf, als auf ein Buch. Ich finds ziemlich dumm den Verweis vom Buchobjekt ein Paar Arraystellen weiter suchen zu müssen, vorallem könnte man ja eine Freie stelle überschreiben die später von nur genau einen anderen Buchobjekt benötigt werden würde, so das man diese dann wieder verschiebe müsste…

Solange nicht vorgegeben ist, ob ihr offenes oder geschlossenes Hashing verwenden sollt, kannst Du es mit einzelnen Buechern oder aber auch mit Listen von Buechern implementieren.

Also in dem Interface IHashtable steht zu put(Object,Object) der Kommentar:

/** * Einfügen eines Objektes. * @param key Schluessel nach dem das Objekt abgelegt werden soll. * @param value Das abzulegende Objekt. * @return Das Objekt, das bisher unter diesem Schluessel abgelegt wurde oder null. */ public Object put(Object key, Object value);
Da das Objekt zurückgegeben wird, was *bisher* an dieser Stelle abgelehnt wurde, schließe ich, dass man Kollisionen gar nicht beachtet muss sondern bisherige Werte überschrieben werden, ähnlich wie bei einem Array, oder irre ich mich? ;)

Das sieht für mich eher nach einer HashMap als nach einer Hashtable aus…

key ist ja kein hashschlüssel. sondern vermutlich key.hashCode(). (sonst hätte man ja einen unendlich grossen schlüsselraum) Es kann dann jeweils nur zu jedem key-Objekt ein value-Objekt gespeichert werden. Aber es gibt ja trotzdem bei den key-Objekten (weil es ja unendlich viele gibt) Hash-Überschneidungen.

key ist ja kein hashschlüssel. sondern vermutlich key.hashCode()

ja, laut aufgabe soll man auch hashCode() benutzen.