Hallo, ich hab da ein Verständnisproblem zu Hash Tabellen. Wie funktioniert so eine Tabelle? Kann mir jemand ein Beispiel geben, wie diese Hash Tabelle prinzipiell funktioniert?
Einfaches Beispiel... Du hast die Aufgabe Textkommados zu empfangen und je nach Kommando eine Aktion zu machen. Du könntest jede Texteingabe mit einem vorher abgespeicherten Text vergleichen und bei Übereinstimmung das Kommando ausführen. Das frisst allerdings kostbaren Speicherplatz, nämlich den für die Vergleichstexte und für die Textvergleiche. Du könntest aber auch mit Hashes arbeiten. Du berechnest aus dem Textkommando eine besondere Zahl, den Hashwert. Und dann vergleichst du den Hashwert mit den zuvor berechneten und im Programm gespeicherten Hashwerten der im Programm bekannten Kommandos. Der Vorteil ist klar - statt den langen Texten hast du nur noch Platz für die Hashwerte (plus die Hashberechnungsfunktion) zu opfern. Die Hashfunktion muss ein paar Anforderungen erfüllen: Sie sollte eindeutige Hashwerte zurückliefern, d.h. kollisonsfrei sein (beachte obigen Link!). Und in dem µC-Fall besonders wichtig: Sie sollte kleine Hashwerte zurückliefern. Die Tabelle kommt ins Spiel, wenn du viele vordefinierte Hashwerte hast und deine Eingabe (deren Hash) damit vergleichen willst. Das geht prima in einer Schleife (for, while, ...) und dem Vergleich des Suchwertes mit den Tabellenelementen. Bei einem Treffer kannst du den Index in der Tabelle als Kommandowert interpretieren und entsprechende Aktionen auslösen.
Du könntest aber auch mit Hashes arbeiten. Du berechnest aus dem Textkommando eine besondere Zahl, den Hashwert. das versteh ich nicht.. wieso wird denn aus einem Text eine zahl??
Was hast du nach denm Lesen davon nicht daran verstanden? http://de.wikipedia.org/wiki/Hash PS: Zitieren ist nicht so schwer im Forum.
Eine Hash-Tabelle lebt davon, eine große Menge (Text oder einen String) auf eine kleine Menge (die Hashes) abzubilden und zwar so, dass es möglichst wenig Kollisionen gibt. Beispiel, du hast einen String, der 20 Zeichen lang ist, das sind also 2^(8*20) Möglichkeiten. Das ganze bildest du jetzt durch die Hash-Funktion auf eine kleine Zahl, z.B. 16 bit, also 2^(16) ab. Dann hast du einen viel geringeren Aufwand, wenn du die Sachen in einer Tabelle suchen musst, oder aber viele Vergleiche duchzuführen hast. Im obigen Beispiel muss man dann nur noch 2 Bytes vergleichen, anstatt 20 Bytes.
also könnte ich dem text(String): "Ich spreche Deutsch" einfach einen belibigen Hashcode aus Zahlen Buchstabe usw geben? @boldie wieso beinhaltet den der String mit 20 zeichen 2^(8*20) Möglichkeiten das leuchtet mir leider nicht ganz ein:(
Patty schrieb: > also könnte ich dem text(String): "Ich spreche Deutsch" > einfach einen belibigen Hashcode aus Zahlen Buchstabe usw geben? Ja, kannst du. Wobei die Kunst nicht darin besteht, dass man einem Text einen Hash-Code zuweist, sondern eine Formel findet, so dass es in einer kompletten Sammlung von Texten so ist, dass jeder Text in einen anderen HashCode mündet UND diese Hash-Codes nach Möglichkeit auch noch aufsteigend sind (zumindest dann, wenn man eine Restklassenbildung, vulgo Modulo, mit der Arraygröße des Hasharrays macht. > > @boldie wieso beinhaltet den der String mit 20 zeichen 2^(8*20) > Möglichkeiten das leuchtet mir leider nicht ganz ein:( 1 Zeichen ist 1 Byte. 1 Byte hat 8 Bit, von denen jedes entweder 0 oder 1 sein kann. Mit 20 Bytes, oder 160 Bits kann man wieviele verschiedene Zustände bilden? Genau soviele verschiedenen Strings kann es daher geben, so dass sich jeder in mindestens 1nem Bit von allen anderen unterscheidet.
Der Trick bei einem Hash ist, das man einen 'riesengroßen' Text auf
einen 'extrem kleinen' Hashwert abbilden kann. Wenn dann dieser Hashwert
auftaucht, kann man einigermaßen sicher sein das er sich aus dem
Originaltext berechnet.
Ein - zugegebenermaßen wenig zweckmäßiges - Beispiel:
Riesentext: "0"
> echo "0" | sha512sum
kleines Ergebnis:
a546d1300f49037a465ecec8bc1ebd07d57015a5ff1abfa1c94da9b30576933fb68e3898
ff764d4de6e6741da822a7c93adc6e845806a266a63aa14c8bb09ebb
Jetzt mal ernsthaft:
Wenn ich den kompletten ersten Absatz nehme und zB. md5 darauf loslasse,
ergibt sich:
3f6647fca64aca514252a99cb4143d15
Das ist nun wirklich eine Verkürzung!
(PS. MD5 nicht für Kryptografie benutzen!)
Norbert schrieb: > Der Trick bei einem Hash ist, das man einen 'riesengroßen' Text auf > einen 'extrem kleinen' Hashwert abbilden kann. Wenn dann dieser Hashwert > auftaucht, kann man einigermaßen sicher sein das er sich aus dem > Originaltext berechnet. Das ist eigentlich nicht der 'Trick' beim Hashen. Gegeben seien 2 Texte A und B. Für beide berechne man den Hashwert h(A) und h(B). Ist nun h(A) nicht gleich h(B), dann weiss man, dass A und B nicht gliech sein können. Aber die Umkehrung gilt nicht: Aus identischen Hash-Werten folgt noch lange nicht, das A mit B identisch ist. Aber eigentlich hat das noch immer nichts mit einer Hash-Tabelle zu tun. Dort geht es einfach darum, eine Funktion zu haben, mit der man aus dem Suchkriterium errechnen kann, wo in der Tabelle die fraglichen Daten gespeichert sind. Und dieses Errechnen übernimmt die Hash-Funktion. Hash Tabellen haben mit Suchen und Wiederfinden zu tun und weniger mit irgendwelchen Text-Verschlüsselungen oder Verkürzungen.
Karl heinz Buchegger schrieb: > Aus identischen > Hash-Werten folgt noch lange nicht, das A mit B identisch ist. Warum denn das? Ist in der Hashfunktion ein Random eingebaut? Meine Hashfunktionen nutzen gerade das, um 2 gleiche Werte zu identifizieren.
Karl heinz Buchegger schrieb: > Gegeben seien 2 Texte A und B. Für beide berechne man den Hashwert h(A) > und h(B). Ist nun h(A) nicht gleich h(B), dann weiss man, dass A und B > nicht gliech sein können. Aber die Umkehrung gilt nicht: Aus identischen > Hash-Werten folgt noch lange nicht, das A mit B identisch ist. Wenn das der Fall ist, hast Du eine Kollision. Die entsteht wenn die Hash Funktion schlecht funktioniert / fehlerhaft ist, oder Du eine unpassende Hash Funktion gewählt hast. Beides muß auf jeden Fall vermieden werden. Beispiel: Eine hypothetische Hash Funktion, die als Hash-Result nur 00-FF (einen 8Bit Wert) ergibt, ist gänzlich unpassend wenn Du mehr als 256 verschiedene Quellwerte unterscheiden musst. Und selbst 256 wäre schon wirklich ambitioniert ;-)
Samuel K. schrieb: > Karl heinz Buchegger schrieb: >> Aus identischen >> Hash-Werten folgt noch lange nicht, das A mit B identisch ist. > > Warum denn das? Weil du beim Verkürzen logischerweise Information wegwirfst. Wenn du von 2 Stück 200 Bit langen Werten jeweils 100 Bit wegwirfst, hast du viele Möglichkeiten für A und B, wo nach dem Wegwerfen dasselbe rauskommt, obwohl A nicht gleich B war. Information die weg ist, ist weg. Und mit nichts auf der Welt kannst du diese Information restaurieren. > Meine Hashfunktionen nutzen gerade das, um 2 gleiche Werte zu > identifizieren. Dann kennst du jetzt einen Fehler in deinem Programm.
Norbert schrieb: > Karl heinz Buchegger schrieb: >> Gegeben seien 2 Texte A und B. Für beide berechne man den Hashwert h(A) >> und h(B). Ist nun h(A) nicht gleich h(B), dann weiss man, dass A und B >> nicht gliech sein können. Aber die Umkehrung gilt nicht: Aus identischen >> Hash-Werten folgt noch lange nicht, das A mit B identisch ist. > > Wenn das der Fall ist, hast Du eine Kollision. > Die entsteht wenn die Hash Funktion schlecht funktioniert / fehlerhaft > ist, oder Du eine unpassende Hash Funktion gewählt hast. Beides muß auf > jeden Fall vermieden werden. Nur zur Klarstellung: Das klingt jetzt so absolut. So nach dem Muster: man kann es immer vermeiden. Dem ist nicht so. Besonders wenn Hash-Tabellen einen Füllgrad > 90% aufweisen, ist es meistens nicht mehr möglich, alles kollisionsfrei zu halten. Aber es werden immer noch wenige Kollisionen sein bis die Tabelle dann knapp vor 100% voll steht. -> Selbst mit der besten Hash-Funktion und nicht vom Programmierer beeinflussbaren Eingangsdaten, muss man in eine Hash-Tabelle eine Kollisionsstrategie einbauen.
Aus einem anderen Blickwinkel betrachtet fällt mir auf, das wir möglicherweise die Bezeichnung 'Hash-Funktion' unterschiedlich benutzen. Ich meine mit 'Hash-Funktion' eine Funktion, der ich Quellwerte übergebe und die mir die zu den Quellwerten passenden Hashwerte berechnet. Diese Werte würde ich in eine Tabelle eintragen. Bekomme ich dann später einen Datenblob zur Überprüfung, würde ich wiederum den Hashwert berechnen und diesen dann (mit einer beliebigen Funktion) in der Tabelle suchen. Schlussendlich: Zwei gleiche Quelldaten ergeben immer den gleichen Hashwert. Zwei unterschiedliche Quelldaten müssen unbedingt einen unterschiedlichen Hashwert liefern. Tun sie das nicht ==> Hash-Funktion schlecht gewählt. Das uns allen bekannte Kollisionsproblem von MD5 ist genau solch ein Problem: man kann einen Quelltext auf geeignete Art und Weise manipulieren und trotzdem den gleichen Hashwert erhalten. Darum ist MD5 zB. für Kryptografie nicht nur wertlos sondern gefährlich.
Norbert schrieb: > Aus einem anderen Blickwinkel betrachtet fällt mir auf, das wir > möglicherweise die Bezeichnung 'Hash-Funktion' unterschiedlich benutzen. > > Ich meine mit 'Hash-Funktion' eine Funktion, der ich Quellwerte übergebe > und die mir die zu den Quellwerten passenden Hashwerte berechnet. > > Diese Werte würde ich in eine Tabelle eintragen. Dann reden wir tatsächlich von verschiedenen Dingen. Bei einer Hash-Tabelle, so wie ich das verstehe ist der Hash-Wert im Grunde nichts anderes als der Index in ein Array unter dem die Quellwerte zu speichern sind. > Bekomme ich dann später einen Datenblob zur Überprüfung, würde ich > wiederum den Hashwert berechnen und diesen dann (mit einer beliebigen > Funktion) in der Tabelle suchen. Nein. Darum gehts nicht in meinem Verständnis einer Hash-Tabelle. Da gehts darum, dass ich beim Suchen nach dem Berger Hubert eben nicht mit irgendeinem Suchverfahren die Daten suche, sondern aus dem Suchbegriff "Berger Hubert" wieder den Hash-Wert berechne und mit dem ins Array gehe. Und genau an dieser Stelle im Speicher steht dann der komplette Datensatz für diesen Suchbegriff. Sofern es nicht eine Kollision gab und ich an dieser Stelle im Speicher die Daten für den "Kratochwil Franz" widerfinde. Dann muss ich die Kollisionsstrategie anwenden und ausgehend vom "Kratochwil Franz" und der bekannten Kollisionsstrategie weitersuchen. Es geht also um eine Möglichkeit, wie man Daten so abspeichern kann, dass das Suchverfahren möglichst O(1) ist. > > Schlussendlich: Zwei gleiche Quelldaten ergeben immer den gleichen > Hashwert. > Zwei unterschiedliche Quelldaten müssen unbedingt einen > unterschiedlichen Hashwert liefern. Tun sie das nicht ==> Hash-Funktion > schlecht gewählt. Dazu müsstest du die Daten im Vorhinein kennen. Das tust du aber im Allgemeinen nicht. Daher kann man nicht einfach sagen: Hash-Funktion schlecht gewählt
Karl heinz Buchegger schrieb: > Samuel K. schrieb: >> Karl heinz Buchegger schrieb: >>> Aus identischen >>> Hash-Werten folgt noch lange nicht, das A mit B identisch ist. >> >> Warum denn das? > > Weil du beim Verkürzen logischerweise Information wegwirfst. > > Wenn du von 2 Stück 200 Bit langen Werten jeweils 100 Bit wegwirfst, > hast du viele Möglichkeiten für A und B, wo nach dem Wegwerfen dasselbe > rauskommt, obwohl A nicht gleich B war. Information die weg ist, ist > weg. Und mit nichts auf der Welt kannst du diese Information > restaurieren. Äh - Moment, mein Weltbild gerät ins Wanken... Wenn man sich eine Hashfunktion "gewichtete Summe der ersten 100 Bytes" bastelt ist das wohl wahr, aber was ist mit MD5, SHA-1 und den anderen "richtigen" Algorithmen welche den gesamten Inhalt betrachten? Kann man dort etwa nicht davon ausgehen dass ein gleicher Hashwert mit sehr hoher Wahrscheinlichkeit gleiche Eingangsdaten bedeutet? Ich nutze MD5 um doppelte Dateien zu löschen, ist das etwa falsch?
!gast schrieb: > Äh - Moment, mein Weltbild gerät ins Wanken... Wenn man sich eine > Hashfunktion "gewichtete Summe der ersten 100 Bytes" bastelt ist das > wohl wahr, aber was ist mit MD5, SHA-1 und den anderen "richtigen" > Algorithmen welche den gesamten Inhalt betrachten? Ist völlig egal. Du kannst nicht beliebige 100 Bits auf lediglich 50 eindampfen, ohne das irgendetwas auf der Strecke bleibt! > Kann man dort etwa > nicht davon ausgehen dass ein gleicher Hashwert mit sehr hoher > Wahrscheinlichkeit gleiche Eingangsdaten bedeutet? Sehr hohe Wahrscheinlichkeit ist nicht 100% > Ich nutze MD5 um > doppelte Dateien zu löschen, ist das etwa falsch? Kommt auf die Daten an. Aber wenn man keine Annahmen über die Daten treffen darf, ja das ist falsch, solange du nur die MD5 Codes vergleichst. Du solltest zumindest bei identischen MD5 Codes die eigentlichen Daten auch noch miteinander vergleichen. Dann bist du auf der sicheren Seite. D.h. der Vergleich der MD5 Codes liefert dir Kandidaten in Form einer Vorauswahl. Ob diese Kandidaten übereinstimmen, dazu musst du die Kandidaten selber überprüfen.
OK, ich glaube ich weiss jetzt wo das Mißverständnis liegt. Ich bin davon ausgegangen, das wir nach großen Datenmengen suchen wollen ohne diese komplett vorrätig halten zu müssen (Mikrocontrollerdenken ;-) In diesem Fall würde ich nur eine Tabelle mit (vernünftig großen) Hashwerten speichern und habe dementsprechend keine Kollisionsstrategie zur Verfügung. Wenn man aber sowohl die Hash Tabelle als auch die kompletten Originaldaten zur Verfügung hat, dann kann man natürlich deutlich schwächere Hashes verwenden und bei Treffern auf Kollision mit dem Original vergleichen. Jetzt sind wir glaube ich wieder beeinander ;-)
Norbert schrieb: > Jetzt sind wir glaube ich wieder beeinander ;-) Yep. Wir haben einfach von verschiedenen Dingen geredet, auf die derselbe Begriff anwendbar ist.
!gast schrieb: > Äh - Moment, mein Weltbild gerät ins Wanken... Wenn man sich eine > Hashfunktion "gewichtete Summe der ersten 100 Bytes" bastelt ist das > wohl wahr, aber was ist mit MD5, SHA-1 und den anderen "richtigen" > Algorithmen welche den gesamten Inhalt betrachten? Kann man dort etwa > nicht davon ausgehen dass ein gleicher Hashwert mit sehr hoher > Wahrscheinlichkeit gleiche Eingangsdaten bedeutet? Ich nutze MD5 um > doppelte Dateien zu löschen, ist das etwa falsch? MD5 entspricht 128 Bits oder 2^128 Möglichkeiten. Die Wahrscheinlichkeit das zwei unterschiedliche Dateien den gleichen MD5 Hash liefern ist verschwindend gering (wenn auch nicht völlig unmöglich) Aber, selbst wenn du als MD5 Ersatz SHA512 verwenden würdest, wäre die mathematische Möglichkeit einer Kollision immer noch <> 0. Die MD5 Probleme treten eher bei gezielten kryptografischen Angriffen auf bei der Daten auf eine bestimmte Art und Weise modifiziert werden um den gleichen MD5 Hash zu erzeugen. Und selbst das ist nur mit extrem hohem Aufwand möglich.
Norbert schrieb: > Aber, selbst wenn du als MD5 Ersatz SHA512 verwenden würdest, wäre die > mathematische Möglichkeit einer Kollision immer noch <> 0. Man könnte das als eine Variation dessen anschaulich machen, was die Mathematiker das 'Schubladenargument' nennen: Wenn 100 Socken in lediglich 30 Schubladen untergebracht werden müssen, dann muss es Schubladen geben, in denen mehr als 1 Socke liegt. Und zwar völlig unabhängig davon, wie die Verteilung der Socken auf die Schubladen vorgenommen wird. Trägt jede Socke eine Nummer, dann reicht es daher nicht aus, sich einfach nur die Schubladennummer zu merken um jede Socke eindeutig zu identifizieren und wiederzufinden. Die Schubladennummer trifft eine Vorauswahl, in dem sie die Anzahl der weiter zu überprüfenden Socken einschränkt, aber eindeutig in dem Sinne, dass man blind in eine Schublade greifen und mit Sicherheit die gesuchte Socke ohne hinsehen wiederfinden kann, ist sie nicht.
Karl heinz Buchegger schrieb: > Wenn 100 Socken in lediglich 30 Schubladen untergebracht werden müssen, > dann muss es Schubladen geben, in denen mehr als 1 Socke liegt. > Und zwar völlig unabhängig davon, wie die Verteilung der Socken auf die > Schubladen vorgenommen wird. Nicht nur das, es geht noch weiter: Selbst wenn man in 30 Schubladen nur 20, 25 oder 30 Socken deponieren will, muß man mit Kollisionen rechnen. Denn es sind nicht 20...30 vorher bekannte Socken, sondern 20...30 aus mehreren Millionen möglichen Socken. Wenn man mit Füllen anfängt und damit die Hashfunktion festgelegt haben muß, weiß man in aller Regel noch nicht, welche man letztlich speichern muß (sonst wäre es nämlich kein Hashwert, sondern eine eindeutige Id). Daß man nicht 30 Plätze kollisionsfrei an Millionen Socken vergeben kann, sollte auch dem größten Optimisten einleuchten.
Norbert schrieb: > MD5 entspricht 128 Bits oder 2^128 Möglichkeiten. > > Die Wahrscheinlichkeit das zwei unterschiedliche Dateien den gleichen > MD5 Hash liefern ist verschwindend gering (wenn auch nicht völlig > unmöglich) Du meinst so unwahrscheinlich wie es ist bei 23 Leuten, 2 Leute mit demselben Geburtstag zu haben? :)
Nee, weit entfernt. Ich nehme mal die Sockenanalogie <grins> Wobei das hier die Anzahl der MD5 Schubladen ist: 3,402823669e+38 (340.282.366.920.938.463.463.374.607.431.768.211.456) Bei einem RAID6 Array mit - sagen wir mal - 12 Platten a 2TByte hätten wir 20.000.000.000.000 Bytes zur Verfügung. Bei einem Ext2 Filesystem mit kleinstmöglicher Blockgröße von 1024Byte hätten wir (ohne Verwaltungsstrukturen): 1,953125e+10 (19.531.250.000) also gerade mal 19 1/2 Milliarden möglicher Socken ;-) Das hieße, es stehen 17.422.457.186.352.049.329.324.779.900 Schubladen pro Socke zur Verfügung. Damit erscheint eine Sockenkollision unwahrscheinlich.
Jetzt werden hier schon die Socken sortiert, ist diese Welt noch zu retten? ;-) >Ist völlig egal. >Du kannst nicht beliebige 100 Bits auf lediglich 50 eindampfen, ohne das >irgendetwas auf der Strecke bleibt! Natürlich. >Kommt auf die Daten an. Im konkreten Fall waren es Bilder (.jpg), insgesamt ein paar hundert. >Die Wahrscheinlichkeit das zwei unterschiedliche Dateien den gleichen >MD5 Hash liefern ist verschwindend gering (wenn auch nicht völlig >unmöglich) So dachte ich mir das. Die Wahrscheinlichkeit einer Kollision bei einem "richtigen" Algorithmus ist nicht gleich 0, aber für die meisten Anwendungen (z.B. meine Fotodoppelterkennung) kann man das Risiko vernachlässigen. Soweit ich weiss wird SHA-256 z.B. eingesetzt um aus einem Passwort einen Schlüssel zu generieren welcher (mehr oder weniger direkt) für AES und Co. verwendet wird. Wenn es da alle Nase lang zu Kollisionen kommen würde wäre das sehr ungünstig weil es mehrere Passwörter geben würde. Soweit richtig? Die Sockengeschichte hab ich jetzt nicht ganz verstanden...
Das bedeutet einfach gesagt, das bei dem angenommenen Array von 12 riesigen Festplatten maximal 19 1/2 Milliarden Dateien gespeichert werden könnten. Die MD5 Hash Funktion stellt hingegen ca. 3,4e+38 mögliche Hash Werte zur Verfügung. Damit gibt es 17.422.457.186.352.049.329.324.779.900 also 17 Quadrilliarden mehr Hash-Varianten als Dateien auf diesem System. Und die Chance für eine Kollision ist 1:17 Quadrilliarden. Gut genug um sich wohlzufühlen ;-)
Korrektur: 17 Quadrilliarden mal soviele Hash-Varianten wie Dateien auf diesem System. Die Wahrscheinlichkeit Dummheiten einzutippen ist offensichtlich deutlich größer;-)
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.