Ordnung in Hashtable??

hallo zusammen, ich habe folgendes problem, aus dem ich nicht recht schlau werde.
ich habe eine datenbank (access), aus der ich daten per dataReader auslese. der select-command enthält ein 'ORDER BY' auf eines der felder (name).
für jeden datensatz erstelle ich nun eine klasse, in die ich die daten des datensatzes fülle. anschliessend füge ich diese klasse einer hashtable hinzu. als key nehme ich die id-property der klasse.
ich füge sie also quasi nach alphabet geordnet der hashtable hinzu.

wenn ich nun aber mit einer foreach-schlaufe durch die hashtable gehe, und die 'name'-property als node einem treeView hinzufüge, ist das ganze nicht mehr nach name geordnet.

wie sind elemente in einer hashtable geordnet?

Hallo RIDI2005,

die Werte deiner Hashtable sind nach dem Hashwert deines Keys sortiert. Deswegen heißt das Teil auch Hashtable. Deswegen gibt es bei "object" auch die Methode "GetHashCode" welche alle objecte somit erben.

Grüße

Vielleicht hilft dir SortedList weiter. Die Klasse erlaubt die Abfrage per Schlüssel oder per Index. Ich schätze der Interator liefert die Werte per Index sortiert.

Ich würde wahrscheinlich eine ArrayList oder List<T> verwenden, per Iterator iterieren und mit BinarySearch Werte mit einen bestimmten Id-Property suchen.

Gruss
Pulpapex

das mit der List<T> muss ich mir mal anschauen. die kenne ich noch gar nicht 🤔
aber i will ehrlich gesagt nur ungerne auf die hashtable verzichten, da ich als key unbedingt die id-property des enthaltenen elements benötige...

trotzdem danke für die antworten 👍

Original von RIDI2oo5
das mit der List<T> muss ich mir mal anschauen. die kenne ich noch gar nicht 🤔

Gibt es erst ab .NET 2.0.

Original von RIDI2oo5
aber i will ehrlich gesagt nur ungerne auf die hashtable verzichten, da ich als key unbedingt die id-property des enthaltenen elements benötige...

Warum nimmst Du dann niicht SortedList, wie schon vorgeschlagen.

Du kannst auch die Hashtable wie bisher weiter nutzen.

Zum Iterieren müssen die Elemente dann in eine ArrayList umkopiert werden und mit einem selbst geschriebenen IdPropertyComparer vorsortiert werden.

Oder du nimmst wie gesagt SortedList. Das ist eine IDictionary-Implementierung, quasi eine Hashtable, die sich die Reihenfolge der Einträge merkt.

List<T> ist eine normale IList, nur dass man als den Typ der Elemente festlegen kann. Gibt es erst in .Net 2.0.

Hallo zusammen,

in Improving Foreach wird ein interessanter Vorschlag zum Sortieren bzw. allgemeiner zum Iterieren von Hashtables gemacht.

herbivore

PS: Link korrigiert. Danke Pulpapex! Der Abschnitt "Improving Foreach" beginnt nicht ganz am Anfang der Seite, also bitte etwas scrollen.

"die Werte deiner Hashtable sind nach dem Hashwert deines Keys sortiert. Deswegen heißt das Teil auch Hashtable."
Nicht nach meinem Verständnis. Diese Sätze sind nach meinem Verständnis weder nachvollziehbar noch korrekt.

Hallo ikaros,

die beiden Aussagen sind korrekt. Wie ist es denn nach deinem Verständnis?

herbivore

Also die MSDN sagt im ersten Satz zu Hashtable:

"Stellt eine Auflistung von Schlüssel-Wert-Paaren dar, die nach dem Hashcode des Schlüssels organisiert sind."

Denke schon das ich das genau so beschrieben habe.

Grüße
Sven

Wenn man es genau nimmt, sind die Einträge nicht wirklich nach den Hashwerten sortiert (in der natürlichen Reihenfolde der Hashwerte) sondern tatsächlich nur organisiert. Es ist richtig, dass der Hashwert eines Schlüssels die Position des Eintrages in der HT bestimmt, allerdings gilt nicht, dass Einträge mit aufsteigenden Hashwerten auch in der gleichen Reihenfolge in der Hashtable sitzen. Ganz einfach weil aus dem Hashwert erst noch der Index berechnet wird, z.B. mittels Modulo. Und 13%7 > 16%7 obwohl 13 < 16. Ich denke allerdings, dass Cypirinha das auch nicht anders meinte.

Das aber nur nebenbei 😁

MfG VizOne

8owow, da ging ja ganz schön was während meiner abwesenheit 8)
vielen dank für all die vorschläge.
hier werden sie geholfen... 😁
also so wie's aussieht werde ich mir mal die 'SortedList' anschauen. klingt nach dem was ich brauche.
auch herbivore's link schau'ich mir noch an.
was ich mir auch noch überlegt habe ist, dass, da ich ja nach alphabet aus der datenbank lese, eine ordnung nach key automatisch einer ordnung nach alphabet bedeuten würde... 🤔

so, ich habe jetzt einen neuen ansatz gewählt.

alter ansatz:

• datensätze aus der datenbank lesen und in hashtable füllen
• treeview aufgrund der hashtable füllen

neuer ansatz:

• 1. datensatz aus datenbank lesen, in hashtable füllen & treeNode erstellen
• 2. datensatz aus datenbank lesen, in hashtable füllen & treeNode erstellen
     ...und so weiter

so muss ich mir um die ordnung keine sorgen mehr machen, da ich den tree in der reihenfolge fülle, aus der ich auch aus der datenbank lese 8)

Wegen weil...
a)"die Werte deiner Hashtable sind nach dem Hashwert deines Keys sortiert"
Definitiv nicht sonst bräuchte man nicht die Ableitung "SortedHashtable"
b)"Deswegen heißt das Teil auch Hashtable"
Das ist einfach Nonsens. Nonsens find ich manchmal ok, Leute bewusst mit Fehlinformationen zu füttern hingegen nicht(Ich hoffe allerdings dass das nicht so gewesen ist, dh: absichtlich).

Hallo ikaros,

wo gibt es die Ableitung SortedHashtable? In der .NET-Doku habe ich dazu nichts gefunden. Jedoch gehe ich davon aus, dass eine SortedHashtable nach den Keys sortiert ist/wäre. Eine Hashtable ist dagegen nach den Hashwerten der Keys sortiert (in der von VizOne geschilderten Präzisierung, auch nachzulesen unter http://de.wikipedia.org/wiki/Hashtable ). Das ist ja im Allgemeinen (auch ohne die Modulo und auch ohne die Konfliktbereinigung) durchaus eine ganz andere Reihenfolge als die Sortierung nach den Keys selbst (mit den beiden Faktoren aber erst recht). Um es mit deinen Worten zu sagen, ist deine Aussage zu diesem Punkt also Nonsens.

Warum heißt den die Hashtable sonst Hashtable, wenn nicht wegen der Verwendung von Hashwerten zum Zugriff (der ja im geschilderten Sinne über die Sortierung/Ordnung der Hashwerte erfolgt)?

herbivore

Hi Ikaros,

Wenn ich mal kurz weiter ausholen darf was hier die einhellige Meinung zur Funktionweise der Hashtable ist:* die Hashtable organisiert ihre Einträge über Hashwerte (daher der Name).

• ein Hashwert ist eine Int32-Zahl.
• er wird über die GetHashCode-Methode der Schlüssel-Objekte ermittelt. Die Methode ist virtual in System.Object definiert. Deshalb kann theoretisch jedes Objekt als Schlüssel verwendet werden. Praktisch muss noch sichergestellt sein, dass sich der Hashwert und das Verhalten der Equals-Methode zwischendurch nicht ändern kann, wenn ein Objekt als Schlüssel im Einsatz ist.
• die Berechnungsvorschrift für Hashwerte ist nicht festgelegt. Jede Klasse kann ihren eigenen Algorithmus implementieren. Vorteilhaft aber nicht zwingend notwendig wäre es, wenn jeweils zwei Objekte, die beim Equals-Vergleich false liefern auch unterschiedliche Hashwerte zurückgeben. (der umgekehrte Fall wird vorausgesetzt 😉 )
• der Int32-Hashwert dient als Index in ein internes Array der Hashtable. Da der Int32-Wertebereich viel zu gross ist, muss der Hashwert noch geeignet auf die Arraygrenzen heruntergerechnet werden, z.B. per Modulo-Operation.
• da es u.a. durch die Beschränkung des Wertebereichs zu Hash-Kollisionen kommt, zwei verschiedene Schlüssel-Objekte haben den selben Hashwert, müssen mehrere Einträge unter einem Index im internen Arrays möglich sein.
• um den Hashtable-Eintrag zu einem Schlüssel wiederzufinden, wird erneut der Hashwert und aus ihm der Index berechnet. Per Equals-Methode werden alle unter dem Index gespeicherten Schlüssel-Werte-Paare verglichen bis ein identischer Schlüssel gefunden ist. Dessen zugeordneter Wert wird zurückgegeben.

Letztendlich bedeutet das, dass es keine (menschenbegreifbare) Ordnung darin gibt, wie eine Hashtable iteriert wird. Es wird einfach über alle Hashwerte oder genauer gesagt alle belegten Indizes des internen Arrays iteriert.

Gruss
Pulpapex

@Pulpaex: Das ist mir klar, ich habe das auch nie in Frage gestellt.
@Herbivore: eine Hashtable ist unsortiert. Die "SortedHashtable" gibts nicht Framework. Aber da man in die Verlegenheit kommen kann Hashtables sortiert(nach Schlüssel oder Wert) anzuzeigen, ist man quasi gezwungen so etwas selbst zu implementieren(oder runterzuladen). Ich nahm an das es so klar wäre(mein Fehler ich mich missverständlich ausgedrückt)

Ich wollte nur eine Aussage wie: <Eine Hashtable ist sortiert und deshalb heisst sie auch so.> nicht so stehen lassen. Gerade Programmieranfänger haben auch so genug Sorgen. Man stelle sich vor jemand zitiert das bei einem Bewerbungsgespräch weil er/sie die Aussage ungeprüft übernommen hat.

mfg Ikaros

Übrigens, hatte von euch schon mal jemand soviel Langeweile um eine Hashtable gegen einen AVL-Tree im Performancetest gegenübertreten zu lassen(im Framework nat.)? Der Gedanke kam mir mal, ich war bisher nur zu faul bzw. hatte andere Prioritäten.

ikaros
Ich wollte nur eine Aussage wie: <Eine Hashtable ist sortiert und deshalb heisst sie auch so.> nicht so stehen lassen. Gerade Programmieranfänger haben auch so genug Sorgen. Man stelle sich vor jemand zitiert das bei einem Bewerbungsgespräch weil er/sie die Aussage ungeprüft übernommen hat.

Hmm, diese Aussage ist hier aber nie gefallen. Es wurde gesagt, dass die Werte in der Hashtable nach den Hashwerten der Schlüssel sortiert sind. Diese Aussage würde ich so akzeptieren. Es ging ja darum wie die Einträge sortiert sind, bzw. wie sie beim Iterieren zurückgegeben werden. VizOne hat es dann noch weiter präzisiert.

Hm, stimmt. Als ich mein erstes Posting hier im Thread abgeliess habe ich das wohl völlig falsch aufgefasst(Lesefehler? Sind 60hz für einen CRT zuwenig?) und danach versäumt den Thread nochmals genau zu lesen. Ich bitte hiermit um Entschuldigung, insbesondere Cypirinha, für mein dümmliches Gelaber.

mfg ikaros

Original von ikaros
Übrigens, hatte von euch schon mal jemand soviel Langeweile um eine Hashtable gegen einen AVL-Tree im Performancetest gegenübertreten zu lassen(im Framework nat.)? Der Gedanke kam mir mal, ich war bisher nur zu faul bzw. hatte andere Prioritäten.

*aufzeig*
Ja, hab ich mal implementiert. Einmal einen AVL-Tree und ein anderes Mal eine Portierung des Red-Black-Trees der VC++ STL.

Performancemäßig erlebt man natürlich keine echten Überraschungen: AVL/RB-Trees haben fürs Einfügen/Suchen O(log(n)), Hashtables hingegen O(1) (wenn dünn genug besiedelt). In der Regel ist die Hashtable also schneller. Dafür sind die Trees sortiert. Wenn es nur um Schlüssel-Werte-Paare geht, empfehle ich eher Hashtables, wenn man Sortierung braucht die Trees. Ist die Anzahl der Einträge klein, fällt der Unterschied natürlich nur sehr gering aus.

MfG VizOne

Danke für die Info. Dann werd ich wohl mal eine Implementierung ins Auge fassen.

mfg ikaros

Mein lieber Mann da war ja gestern noch ganz schön was los. Wollte sowas hier nicht lostreten, aber das wäre zumindest ausdiskutiert.

Werde mich mit solch lapidaren Antworten demnächst zurückhalten. Aber ich dachte mir das es für einen Anfänger eher zweitranggig ist welche Theorie dahinter steckt und eher die beantwortung der Frage im Vordergrund steht, und die war ja ganz einfach warum die Liste nicht wie erwartet sortiert ist.

@ikaros, kein Problem, hab mich auch nicht genau ausgedrückt, außerdem ist ja so ein Forum dazu da so etwas zu diskutieren.

Grüße

Hallo zusammen,

eine verbesserte und erweiterte Version der Iteratoren aus dem oben genannten Artikel Tips and Tricks (Abschnitt "Improving Foreach") von Eric Gunnerson findet ihr in Hilfreiche Iteratoren / Improving Foreach .

herbivore