Hach-Funktionen

[unite]

Kann mir jemand erklären, was Hach-Funktionen sind, wie sie funktionieren, und welche es davon gibt?

danke im voraus

[Crush]

Meinst Du Hash??!?

[Cyrill]

Hi

Es muss fast Hash sein... Ich hab mal geschaut ob ich was mit Google zu Hach-Funktionen finde!

Ne Hastabelle besteht sozusagen aus 2 Spalten. Ein Spalte besitzt immer einen Referenzkey und die andere den Wert!

mit der Funktion put(Object Key, Object Wert) kann man den Hashtable füllen!

Über den Key kommt man dann wieder zu dem Wert!

Ist das so richtig wie ich das erzähle.. Korrigiert mich falls es nicht stimmt!!

Cyrill

[unite]

Ich meinte Hash und zwar unter dem Gesichtspunkt: Verschlüsselung.

[Crush]

Also mit Verschlüsselung .. da weiß ich auch nicht wie man das direkt in Verbindung bringen sollte. Ich bin eigentlich auch kein Java-Mann sondern C++-Programmierer, aber ich versuch´s trotzdem mal:

Eine Hash-Berechnung ist eine Methode um innerhalb eines Datenspeichers möglichst schnell auf die Positionen aufgrund eines Dateinamens oder einer anderen Signatur zu gelangen. Herkömmlich für Festplatten und Disketten erdacht - kann aber heute genauso ein Array, Dequeue oder sonstwas sein.

Hierbei betrachtet man zuerst die Größe des maximalen Datenumfangs. Dann wird eine Formel erdacht, die möglichst eindeutig vom Namen her einen Wert liefert, der einem Eintrag des Datencontainers entspricht. Z.B. wird gerne ein Double genommen. Buchstaben fangen bei hexadezimal 20 an. Also wird nur der Bereich der möglichen Buchstaben für den Dateinamen (ist ja vordefiniert was erlaubt ist) auf diese Zahl dazuaddiert. Der Zweite Buchstabe wird nun mit der maximal möglichen Anzahl an Buchstabenkombinationen multipliziert (sagen wir mal einfach so zum Rechnen mit 100) und auch wieder dazuaddiert. Der Dritte Buchstabe dann mit 100*100, usw.. Zum Schluß wird noch ein Modulo auf die Größe des Containers ausgeführt und man hat eine Einsprungsposition, ab der man schon nach den Daten suchen kann.

Beim Schreiben muß man natürlich berücksichtigen, daß eine solche Position eventuell ausgerechnet durch eine andere Namenskombination auch schon als Ergebnis herauskam und belegt ist.

Ist diese Position schon belegt gibt es mehrere Möglichkeiten für Kollisionsverfahren um den nächsten höchstwahrscheinlich freien Eintrag zu ermitteln. Meist wird von der Position einfach vorwärts gesucht bis der nächste freie Speicher auftaucht (ist aber auch fast immer am langsamsten), eine weitere Berechnung auf die Hash-Formel durchgeführt (am einfachsten führt zu brauchbar schnellen Ergebnissen) oder durch eine sinnvolle Erweiterung der Formel auf die Datengröße und die Möglichen Dateninhalte die die Auslastung optimiert.

Jetzt verstehst Du auch bestimmt, was der Schlüssel und die Daten genau sind. Der Schlüssel ist das Hash-Ergebnis und die Daten sind einfach die Containerinhalte.

Wie man sieht kann es sein, daß der Daten-Container fast vollständig belegt ist und unheimlich viele Kollisionen auftauchen. Zum Ende wird also das finden des letzten freien Speicherplatzes enorm zeitaufwendig. Daher ist ein Container meist optimal ausgelastet, wenn er nur zu ca. der Hälfte bis zu zwei Drittel gefüllt ist. Sind die die Container-Einträge noch mit einer Linked-List verknüpft, kann dieses Problem einfach beseitigt werden. Man macht sich eine Liste, welche die freien Einträge enthält und eine welche die belegten Einträge enthält (wegen dem Freigeben von Inhalten). Das setzt natürlich voraus, daß der Container komplett vorverlinked wurde. Jetzt kann man einfach jeden belegten Eintrag in die "Besetzt"-Liste einlinken und von der "Freien"-Liste auslinken. Bei Kollisionen werden die Ergebnisse der Kollisionsberechnung direkt miteinander verlinkt und man kann wenn zuviel Kollisionen berechnet wurden einfach mit Gewalt freie Datenplätze aus der "Freien"-Liste herausnehmen und diese belegen.

Wie man sieht ein (relativ) komplexes Thema, welches aber mit der richtigen Formel extrem beschleunigten Datenzugriff auf große Datenvolumen ermöglicht.

Gerade bei Logistik-Software hatte ich mich mal mit einem Programmierer unterhalten und der erzählte mir, daß die eigens zum Erstellen der optimalen Hash-Formeln eine eigene Abteilung beschäftigen, die fast nur damit beschäftigt sind. Hier wird dann auf jeden Lagerbestand einer Firma aufgrund der Warenanzahl, -Variationen und Lagerkapazität dann eine spezielle Hash-Formel entworfen, welche in die Ausgabe von deren Programm direkt integriert wird. Also gibt´s sogar die Hasher als Beruf! (hört sich verdächtig nach grasrauchenden Langhaardackeln an, gell?)

Wie man das jetzt mit Verschlüsselungsalgorithmen in Verbindung bringen soll weiß ich auch nicht so genau - ich spekuliere einfach mal. Man könnte aber dann auf eine Verschlüsselung aufgrund der Eingangsdaten für den Hash-Code kommen. Es wird also das Paßwort durch eine Hash-Formel gejagt, welche noch weitere Verschlüsselungsformeln integriert haben könnte (hochrechnen z.B. mit dem Quadrat von Primzahlen, welche auch wieder aufgrund des Hashs ausgewählt werden könnten oder aufgrund des Eingangswortes) und der Hashcode wird dann als Verschlüsselung für das Wort selbst verwendet. Von mir aus wird wieder jeder Buchstabe des Wortes mit dem Hashergebnis addiert, die Bits ausgetauscht, geeort oder sonstwas mit angestellt - gut ist es bei Verschüsselungen immer, wenn für jeden Buchstaben eine wesentlich größerer verschlüsselter Code bei rauskommt! Sinnvoll ist es die Position der zu verschlüsselten Daten auch noch in das Hash-Ergebnis mit reinzurechnen. Am besten ist es, das ganze noch mit einer Datenkompression zu kombinieren, weil dann die Bits nahezu gleich häufig auftreten und ein Entschlüsseln so praktisch unmöglich gemacht wird (da kommen die Verschlüsselungsprofis aber auch erst jetzt drauf - hatte ich mir schon früher gedacht).

Wie man sieht kann man Hashes zu allem möglichen Verwenden, allerdings war gedanklich im Vordergrund die Geschichte mit den Datenzugriffen.

Alles verstanden? Ist auch nicht ganz soooo einfach. Aber wer´s einmal kapiert hat, der plagt sich da nicht weiter mit rum was nun ein Key sein soll - ist ja meist alles in Libs vorgefertigt.

<FONT COLOR="#a62a2a" SIZE="1">[ 27. November 2001 08:53: Beitrag 2 mal editiert, zuletzt von Crush ]</font>

[unite]

ich danke dir vielmals!!!