nicht angemeldet
Tach.
Dann brauch ich jetzt auch noch eine Erklärung (oder Link zu einer), wie man einen Hashwert findet, ohne die Sammlung der Hashwerte (vollständig, teilweise, wie auch immer) durchsuchen zu müssen.
Man steckt den Schlüssel in die Hashfunktion, welche als Ergebnis einen Index in den Hashtable (selber ein Array) liefert. Dort ist die Speicheradresse zu finden, an der sich die gewünschten Daten befinden. Deshalb können diese Datensätze, im Gegensatz zum herkömmlichen Array, auch kreuz und quer im Speicher verteilt sein.
Dadurch, daß man die Schlüssel auf einen festgelegten Bereich abbildet (die Indizes des Hashtables), kann man nun z. B. auch Zeichenketten als Schlüssel verwenden und assoziative Arrays implementieren, wie wir sie auch aus PHP kennen. Die eigentliche Arbeit steckt also im Entwurf einer vernünftigen Hashfunktion. [1]
Eine ziemlich einfache (und nicht besonders gute) Hashfunktion für Strings wäre z. B. eine, die die Länge des Schlüssels bestimmt und mit einer Modulodivision auf die Größe des Hashtables reduziert. Der Schlüssel "dedlfix" verweist dann auf den letzten Eintrag eines 8-Elemente-Hashtables, wärend "Blaubart" zum ersten Eintrag führt.
Nur müssen diese Strukturen eben nicht aufwendig durchsucht werden.
Vielleicht ist es nicht aufwendig, die Hash-Liste zu durchsuchen, aber deutlich komplexer als eine Multiplikation stelle ich mir das schon vor.
Das ist richtig; hängt eben von der Komplexität der Hashfunktion ab. Daß das trotzdem viel "billiger" zu haben ist als eine Suche, bei der erstmal die Arrayelemente aus dem Speicher gelesen werden müssen (im ungünstigsten Fall sogar alle), sollte klar sein.
[1] Mindestens genauso wichtig sind wahrscheinlich die Mechanismen zur Behandlung von Kollisionen. Aber das bringt dieses Thema so langsam an einen Punkt, wo ich die Lektüre eines Fachbuchs vorschlagen würde, anstatt hier im Forum weiter darüber zu referieren. ;)
Once is a mistake, twice is jazz.