www.mikrocontroller.net

Forum: PC-Programmierung Wie funktioniert eine Hash Tabelle


Autor: Matze (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Compy (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ist eigentlich ganz einfach:

http://de.wikipedia.org/wiki/Hash

Autor: Stefan B. (stefan) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Patty (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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??

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was hast du nach denm Lesen davon nicht daran verstanden?
http://de.wikipedia.org/wiki/Hash

PS: Zitieren ist nicht so schwer im Forum.

Autor: Sven S. (boldie)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Patty (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:(

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Norbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Sam .. (sam1994)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Norbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Optimistisches Programmieren heißt das.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Norbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: !gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
!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.

Autor: Norbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Norbert schrieb:

> Jetzt sind wir glaube ich wieder beeinander ;-)

Yep.
Wir haben einfach von verschiedenen Dingen geredet, auf die derselbe 
Begriff anwendbar ist.

Autor: Norbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
!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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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? :)

Autor: Norbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: !gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Norbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

Autor: Norbert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Korrektur:
17 Quadrilliarden mal soviele Hash-Varianten wie Dateien auf diesem 
System.

Die Wahrscheinlichkeit Dummheiten einzutippen ist offensichtlich 
deutlich größer;-)

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.