nicht angemeldet
Hi,
Heißt das, die Arrays nach meinem Beispiel gehend mit Integern
zu adressieren
$root->obj[3][54][132]->...
diese Integers aber wiederum in einem Hash zu haben?
So nach dem Motto
$hash['asd'] = 3;
$hash['qwe'] = 54;
$hash['yxc'] = 132; ?
Die Idee ist, daß Du die Menge der angebotenen Indexwerte der Menge
der benötigten Index-Werte anpaßt.
_Wie_ Du das machst, das hängt von Deinem konkreten Einsatzfall ab.
Ich nehme mal Deine drei Zahlenwerte 3, 54 und 132 als Eingabe.
Wenn Du davon ausgehst, daß Du tatsächlich ungefähr drei Werte haben
wirst, aber nicht genau weißt, wieviele (tendentiell eher etwas mehr),
dann könnte Deine Hash-Funktion einfach den Zahlenwert modulo 10
zurückliefern, also 3 -> 3, 54 -> 4 und 132 -> 2.
Du hältst einen Array mit 10 Elemente vor, kontrollierst also die
erforderliche Speicher-Menge; gleichzeitig erfordert der Zugriff auf
den passenden Speicherort genau einen mathematische Transformation.
Du "kaufst" also sehr viel Speicher durch etwas zusätzliche CPU-
Leistung - ein klassischer Trade-Off der Datenverarbeitung. (Der
Einsatz von mod_gzip für den Apache-Server des Self-Portals ist
letzten Endes dasselbe - der 'kauft' Bandbreite mit CPU-Leistung.)
Natürlich mußt Du damit leben können, daß Deine Hash-Funktion auch
mal "Pech" hat. Sie wird Dir nicht mit Sicherheit lauter disjunkte
Indizes liefern.
Du mußt also unter jeder Deiner Speicheradressen möglicherweise eine
komplexere Struktur (z. B. eine lineare Liste) anlegen, nicht nur
eine atomare Speicherzelle. Und Du mußt Verwaltungsinformationen mit-
führen, um die Einträge der Liste voneinander unterscheiden zu können.
Letzten Endes würde sich Deine Implementierung dem, was Perl oder PHP
für deren interne Realisierung eines Hashes verwenden, stark annähern.
Der Trick besteht darin, daß es sehr unwahrscheinlich ist, daß diese
Liste tatsächlich viele Elemente enthält (dann wäre Deine Hash-Funktion
schlecht); in den allermeisten Fällen wird ein direkter Zugriff sofort
zum Erfolg führen.
Deshalb habe ich die Tabelle auch größer gewählt als nötig. Im Beispiel
mit Deinen drei Zahlen wäre schon "modulo 4" eine optimale Hash-Funktion
gewesen, aber bereits für die 4. Zahl würde die Wahrscheinlichkeit, die
verbliebene Speicherzelle zu treffen, auf nur noch 25% absinken, und bei
der 5. Zahl ist die erste Kollision sicher.
Von den Integer-Zahlen als Eingabewerte in die Hash-Funktion bin ich nur
ausgegangen, um die Sache anschaulicher zu machen.
Du kannst genauso gut den ersten Buchstaben Deiner Adreß-Strings verwen-
den. Das Prinzip gilt für Bitmuster - egal, was sie bedeuten.
Insbesondere kann Deine Hash-Funktion beliebig viele Dimensionen als
Eingabe haben, also beliebig komplexe "Adressen" übersetzen - so wie
die skalare Nummer eines Personalausweises eine beliebig komplexe Person
adressieren kann.
Du kannst also sämtliche Deiner Objekte über einen einzigen linearen
Array speichern, wenn Deine Hash-Funktion die Dimensionen entsprechend
zusammenfalten kann. Damit weißt Du sehr genau, wieviel Arbeitsspeicher
Du Deinem Problem zuordnest - wenn es nicht reicht, dann wird halt die
Kollisionsrate höher und die Verarbeitung langsamer.
(Die Kollisionsrate kannst Du dabei selbst mitschreiben und beim Über-
schreiten eines kritischen Wertes eine Meldung ausgeben, daß Dein Spei-
cher offenbar zu dürftig ausgestattet ist - im Prinzip macht ein Be-
triebssystem etwas Ähnliches, wenn es die Swapping-Rate berechnet.)
Auf diese Weise würde Deine ursprüngliche Idee direkt mit einfließen -
und ein einziger Aufruf einer effizient implementierten Hash-Funktion
ist wömöglich sogar schneller als wiederholtes Deferenzieren Deiner
Objekt-Verkettungen.
Mein Problem ist hier jetzt auch die Informatiker-Begrifflichkeit,
die ich erst mal in mein Learning-by-doing-Programmierer-Deutsch
übersetzen muß ... ;-)
Nur zu - dafür ist das Forum prima geeignet.
Viele Grüße
Michael