extendible hashing + sortierverfahren?

hallo!
ich habe eine mich verwirrende aufgabe im zuge meines studiums erhalten.
ich soll einen container entwerfen, der extendible hashing zur indexierung verwendet. soweit so gut, nach ein bisschen einlesen ist alles klar und ich hab auch schon eine implementierung dafür zusammengebracht.
es geht, kurz gesagt, darum, dass eine bestimmte anzahl von bits des (hash)schlüssels (genannt: "globale tiefe") als index in einem verzeichnis (in meinem fall std::vector) verwendet werden, welches zeiger auf die einzelnen buckets enthält, die die tatsächlichen elemente enthalten. sollte ein bucket voll sein, dann kann sich das verzeichnis vergrößen, die globale tiefe wächst und das neue element findet platz in einem neuen bucket. die anderen buckets werden nicht verändert, aber nun von mehreren verzeichniseinträgen referenziert. (ich denke, ihr wisst alle, was extendible hashing bedeutet, ich schreibe das nur, weil ich ja vielleicht in dem konzept schon einen fehler drin habe, der mich den rest der aufgabe nicht verstehen lässt) - soweit so gut.

nun muss ich die einträge in dieser hashmap durch quicksort sortieren. ich weiß widerum, wie quicksort prinzipiell funktioniert, aber ich verstehe nicht, wie diese hashmap sinnvollerweise sortiert werden kann? ich meine, ich könnte höchstens die einzelnen einträge in einem bucket mit quicksort sortieren und dann eine möglichkeit überlegen, sortiert durch die einträge im verzeichnis durchzulaufen. aber ich verstehe einfach nicht, wie ich diese hashmap mit quicksort sortieren kann, in meinen augen sind das einfach zwei konzepte, die nicht zueinander passen...

lg

mazal

, in meinen augen sind das einfach zwei konzepte, die nicht zueinander passen...

Stimmt eigentlich. Und auch wieder nicht. Kommt drauf an, ob ihr ganz oft Lookups/Einfügen macht und ihr die Sortierung selten braucht. Dann ist eine Hashtable das mittel der Wahl. Wenn ihr aber oft die Sortierung braucht und nicht so oft Lookups/Einfügen macht könnte man erwägen zu Suchbäumen zu switchen. Aber funktionieren tuts trotzdem: Lauf einfach durch alle Buckets, haue alle Elemente der Buckets in einen frischen std::vector und sortier diesen.

Gruß

naja, die konkrete aufgabe lautet, eine hashmap mit extendible hashing zu implementieren, auf deren einzelne werte sortiert zugegriffen werden können muss (mittels funktoren, also z.b. hashmap.apply(Print(), order::ascending) ) und dieses sortieren mittels eines bestimmten (vorgegebenen) algorithmus zu geschehen hat (in meinem fall quicksort).
also von daher kein switch zu bäumen; auch, wie die hashmap verwendet wird, ist nicht angegeben. es steht nur fest, dass zum ersten abgabetermin einfügen und finden von elementen möglich sein muss, beim zweiten termin sortieren und löschen.

hustbaer

Also so wie ich die Aufgabenstellung verstehe ist das nicht ganz sinnvoll, aber naja.
Du sollst eine Hashmap bauen, die eine "convenience method" bereitstellt, mit der man einen Funktor auf alle Elemente anwenden kann, und zwar in Reihenfolge X. Da dir der Sortieralgorithmus vorgegeben wird, scheidet eine Lösung mit einem zweiten, sortierten Index schonmal aus.

Die "Apply" Funktion wird also genau das machen was mazal schon beschrieben hat: alle Einträge in einem Array (std::vector) sammeln, dann sortieren, und dann die Funktion drüberlaufen lassen.

Natürlich musst du dabei nicht die Einträge selbst kopieren, das wäre ja ziemlich ineffizient, sondern du wirst vermutlich Zeiger auf die Einträge verwenden. Auch kannst du das sortierte Array "aufbehalten", falls Apply ein weiteres mal aufgerufen wird, ohne dass die Hashmap dazwischen verändert wird. Bei Änderungen markierst du das sortierte Array dann einfach als ungültig, damit beim nächsten Apply wieder neu sortiert wird.

Ob sowas Sinn macht sei dahingestellt, aber gehen tut es schon.

Aber frag ruhig nochmal nach wie die Aufgabe genau zu verstehen ist. Viele Profs freuen sich wenn jmd. Fragen stellt, aus denen hervorgeht, dass derjenige mitgedacht hat

Hallo,

ich habe die selbe Aufgabe für die Uni, extendible hashing mit quicksort und ich war auf verwirrt wie ich das genau machen soll..

@verwirrt - schreib mir email - niona9@yahoo.com, wir können zusammenarbeiten