Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Hashing
Hab mir gerade mal den ganzen Kram zum Hashing durchgelesen, weil das kommt ja recht oft dran so. Eigentlich alles ganz easy, aber ich habe nicht ganz verstanden wieso ich beim geschlossenen Hash Verfahren beim Löschen den Behälter als gelöscht markieren muss.
zB Folie25 vom 14.1 Paket.
Wenn ich jetzt zB die 21 suche und sehe, das der Behälter0 leer ist, könnte ich doch wie beim Sondierverfahren weiterschauen wo meine 21 geblieben ist. Wieso ist die denn dann unerreichbar?
genau das is glaub ich der punkt, wenn du was (physisch!!!) löschst dann sieht du gar nichts mehr deshalb musst du behälter als gelöscht frei oder belegt markieren
Es ist ja auch möglich dass es die 21 gar nicht gibt. Du müsstest dann jeden Behälter durchschauen um am Ende festzustellen dass sie gar nicht da ist. Ist aber der Behälter wo sie eigentlich drin wäre als gelöscht markiert weißt du dass sie möglicherweise im nächsten ist. Wäre der Behälter nicht markiert, also komplett leer, könntest du gleich mit der Suche aufhören weil sie dann nicht da ist.
Okay, ich schaue mir das gerade nochmal in der Musterlösung von Blatt 7 an, und hab da noch einige Fragen:
-Die Hashfunktion:
private int h(int x, int i) {
return ((x + 3 * i) % maxElements);
}
wird so aufgerufen: a = h(newElement.getId(), i) während i die ganze Zeit hochgezählt wird, bis es den Max Wert des HashTables erreicht. Dh ich suche eine neue Position im HashTable. Aber in der Aufgabe steht etwas von wegen Offendem Hashing, also müsste man ja wenn der Eintrag voll ist eigentlich eine Liste anlegen, anstelle eine neue Position zu suchen.
Naja, und die andere Frage hat sich jetzt so langsam erübrigt, während ich das Zeug die ganze Zeit gelesen hab…
Aber das oben würde mich schon interessieren :rolleyes:
also diese loesung sieht wirklich sehr verwirrend aus. ich hatte das glaube ich ganz anders gemacht.
zu deiner frage: das ist wirklich geschlossen gehasht und und nicht offen, wie in der fragestellung eigentlich vorgegeben. also einfach fehler seitens der uebungssteller /-loeser.
btw: zum hashen kommt oft die frage:
gegeben sei die hashfunktion h(x) = x mod m.
welche bedeutung haben die groessen x und m?
ich wuerde da sagen, dass
m = groesse der hashtable / anzahl der buckets
x = schluessel des datums
ist. was wuerdet ihr da schreiben?