Im Prinzip geht es mir darum einen möglichst kurzen Hash erzeugen zu können, um die daraus resultierende Gesamtdatenmenge möglichst klein zu halten.
Das Problem dabei ist ja nun, dass je geringer die Anzahl der möglichen Werte ist, desto höher ist die Wahrscheinlichkeit, dass sich die Hash-Codes zweiter Ursprungswerte überschneiden.

Nun brauche ich das aber im Endeffekt nur für eine statistische Zuordnung und nicht für einen Security-Bereich. Es geht also nicht darum, Überschneidungen so gut wie möglich auszuschließen, sondern nur diese unter eine möglichst geringe prozentuale Wahrscheinlichkeit zu bringen. (Es wäre also z.B. nicht schlimm, wenn etwa 1% dabei wegen Überschneidungen verloren geht)

Leider weiß ich nicht so recht wie ich das berechnen soll und so hoffe ich, dass mir hierbei jemand gedankliche Hilfe leisten kann.

Eine denkbare Möglichkeit: Ich verwende die ersten 8 Stellen von einem MD5 Hash und habe damit 16^8 = ~4,3 Mrd Kombinationsmöglichkeiten. Angenommen ich habe nun 1 Mio Werte, die ich speichern möchte. Wie wahrscheinlich ist dann, dass sich zwei Werte überschneiden?

Moin!

Was spricht gegen CRC32?

cu
Narses

Nichts, aber was spricht dafür? Ändert an der Problemstellung ja auch nichts. Das Problem könnte ja sein, dass mir 8 Stellen nicht reichen und ich dann noche ine neunte oder zehnte nehmen würde. Bei CRC32 wird das nicht gehen, bei MD5 wäre das kein Problem. Aber dazu müsste ich erst einmal wissen, wie es denn mit der Kollisionswahrscheinlichkeit aussieht. Deshalb das Rechenbeispiel. Wäre schön, wenn mir das jemand berechnen könnte und sagen könnte, wie das geht, damit ich das auch mit anderen Zahlen testen kann.

Grob gesagt: Anzahl Testwerte / Mögliche Hashwerte

Genau kann man das (wenn ich mich grad nicht vertan hab) über das Geburtstagsparadoxon lösen: de.wikipedia.org/wik...Tag_Geburtstag_haben

Grob gesagt: Man brauch quadratisch so viele Hashwerte, wie man Testwerte abspeichern will, wenn man weniger als 50% Kollissionen haben will. Erstmal zur Kollissionswahrscheinlichkeit. 8 Byte dürften daher für den Hash eigentlich bereits ausreichend sein.

Alternativ: Warum verwendest Du nicht eine Linked-Hashmap für die Zwischenspeicherung? Dmit können Dir Kollissionen egal sein, da du jegliche Werte am Ende wiederbekommst.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

BenBE hat folgendes geschrieben:

Grob gesagt: Anzahl Testwerte / Mögliche Hashwerte

Äh, das kann aber nicht ganz sein, oder? Das mit dem Geburtstagsparadoxon stimmt wohl eher. Wenn ich das für meinen Fall doch nur mal eben schnell ausrechnen könnte.

BenBE hat folgendes geschrieben:

Grob gesagt: Man brauch quadratisch so viele Hashwerte, wie man Testwerte abspeichern will, wenn man weniger als 50% Kollissionen haben will. Erstmal zur Kollissionswahrscheinlichkeit. 8 Byte dürften daher für den Hash eigentlich bereits ausreichend sein.

Dann widersprichst Du Dir aber doch wieder. Wenn das mit den quadratisch vielen Hashwerten stimmt, dann reichen mir bei 1*10^6 Werten keine 4,3*10^9 Hash-Möglichkeiten aus.

Zudem möchte ich eigentlich nicht wissen, ob zwei Werte wahrscheinlich kollidieren oder nicht, sondern wieviele der 1Mio Werte bei zB CRC32 wahrscheinlich verloren gehen werden.

BenBE hat folgendes geschrieben:

Alternativ: Warum verwendest Du nicht eine Linked-Hashmap für die Zwischenspeicherung? Dmit können Dir Kollissionen egal sein, da du jegliche Werte am Ende wiederbekommst.

Ich bin damit nicht vertraut, glaube aber nicht, dass mir das hilft, da die Hashwerte am Ende von verschiedenen Quellen kommen werden, nachträglich nicht geändert werden dürfen und dennoch beim Erneuten senden aus der Quelle erkannt werden soll, dass genau diese Quelle schon Informationen gesendet hat. Ich glaube, das ist mit Tricks wie Linklisten nicht machbar, deshalb bin ich bereit einen gewissen Satz von etwa 1% an Informationen zu "opfern", möchte aber entsprechend wissen, wieviele Hash-Stellen ich benötige, um diese Prozentzahl erreichen zu können.

CodexX hat folgendes geschrieben:

BenBE hat folgendes geschrieben: ...Linked-Hashmap für die Zwischenspeicherung? ... Ich bin damit nicht vertraut, glaube aber nicht, dass mir das hilft, da die Hashwerte am Ende von verschiedenen Quellen kommen werden, nachträglich nicht geändert werden dürfen und dennoch beim Erneuten senden aus der Quelle erkannt werden soll, dass genau diese Quelle schon Informationen gesendet hat. Ich glaube...

"Glaube" heißt: Nicht Wissen.

Genau dafür ist eine Hashmap der ideale Kandidat: Du hast ja nichts anderes als Schlüssel/Wert-Paare (Schlüssel=Hash+Quelle, Wert=Daten). Du prüfst einfach, ob der Hash schon in der Map ist. Wenn nicht, fügst Du ihn ein. Wenn ja, hat die Quelle diese Information schon gesendet. Mehr willst Du ja nicht wissen, oder?

Zur Verdeutlichung: 8 Byte = 64 Bit = 2^64 ~ 10^20 > 10^12 ... Wer Rechnen kann, ist klar im Vorteil

@Kollissionswahrscheinlichkeit: Eben genau die Wahrscheinlichkeit brauchst Du aber, weil Du anhand dieser auf den Erwartungswert an Kollissionen schließen kannst.

@Hashmap: Für große Hashmaps bietet sich u.U. die Realisierung als balancierter Baum an. Die Schlüssel-Zuordnung bleibt aber gleich.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

BenBE hat folgendes geschrieben:

@Hashmap: Für große Hashmaps bietet sich u.U. die Realisierung als balancierter Baum an. Die Schlüssel-Zuordnung bleibt aber gleich.

Warum?

Weil man dann nicht die gesamte Map im Speicher behalten muss, sondern nur ddie Werte im RAM hat, die auch zugewiesen sind. Ich glaub nämlich nicht, dass Du ein Array mit 2^64 Einträgen mal eben in deinem RAM abgelegt bekommst

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

BenBE hat folgendes geschrieben:

Weil man dann nicht die gesamte Map im Speicher behalten muss, sondern nur die Werte im RAM hat, die auch zugewiesen sind.

Eine gute Hashmap wächst mit den Erfordernissen.

Aber vielleicht nochmal zur Aufgabenstellung: Wir haben also diverse Quellen, aus denen Daten ankommen. Es soll sichergestellt werden, das ein Datum von einer Quelle nur 1x erfasst wird, korrekt?

Wir bilden also aus der Kombination Quelle-Datum einen Schlüssel. Dann benötigen wir ein 'Nachschlagewerk', in das wir sehr schnell Schlüssel einfügen und auch wiederfinden können. Die Vorgehensweise ist so:

Die Wahl des Nachschlagewerkes:
Sofern wir genügend RAM haben, verwenden wir eine Hashmap.

Wenn wir nicht genügend RAM haben, verwenden wir eine Datenbank, wobei wir einen Index auf das Quelle-Datum-Tupel legen und damit auch eine ordendliche Performance haben.

Und wenn wir über genügend Zeit verfügen, dann basteln wir uns eine Bayer-Baum-Map inklusive Page-Cache.

Die Kombination aus Hash-Datum geht leider nicht...

OK, also wenn das jetzt so spezifiziert wird, dann hol ich doch weiter aus, obwohl mir wirklich einfach schon die Information ausreichen würde, wieviele Hashstellen ich benötige, wenn ich ~1Mio Werte habe und diese mit einer Wahrscheinlichkeit von <1% kollidieren...

Also das Problem genauer:
Eine Quelle schickt ein Paket an Informationen. Diese Informationen können sich mit der Zeit ändern. Der Hash der Quelle wird immer gleich bleiben.
Es kann sein, dass sich die Informationen einer Quelle ändern, dann würde sie erneut senden. Dann soll das aber im gleichen Datensatz gespeichert bzw. geändert werden und kein neuer angelegt werden! Es wird also definitiv nur so viele verschiedene Datensätze geben wie unterschiedliche Hashwerte vorhanden sind. Sendet nun eine andere Quelle mit dem gleichen Hash werden die Informationen der ersten Quelle verloren gehen! Das ist aber wie gesagt nicht tragisch, solange sich das bei unter einem Prozent aller Daten bewegt.
Ich glaube, die fehlende Information war hier, dass die Werte eventuell aktualisiert werden, das würde bei Hash-Datum-Kombinationen den gesamten Datensatz mit der Zeit vervielfältigen, was nicht passieren darf.

Dann nimm als Schlüssel eben 'Quelle-Hash'. Die Nutzinformation sind dann deine gesendeten Daten. Das ist doch nicht schwer. Die Implementierung dauert ca. 5 Minuten.

In der Hashmap kannst Du die Daten auch austauschen. Du suchst dazu den Schlüssel, wobei ein Zeiger auf die mit dem Schlüssel gespeicherte Nutzinformation geliefert wird. Und hier überschreibst Du die Daten einfach.

CodexX hat folgendes geschrieben:

wieviele Hashstellen ich benötige, wenn ich ~1Mio Werte habe und diese mit einer Wahrscheinlichkeit von <1% kollidieren...

Welche Hashfunktion? Woraus wird der Hash gebildet? Mit welcher Wahrscheinlichkeit willst Du eine Kollisionswahrscheinlichkeit < 1%?

Achso.... du willst also eigentlich gar nichts Hashen, sondern eine GUID mit möglichst wenig Stellen für die Quelle generieren können.

Die einfache Variante wäre, dass sich jede Quelle vor dem Senden anmelden muss und dabei eine Eindeutige ID kriegt. Für 1Mio Quellen reicht ja eine laufende Nummer im 32Bit-Bereich (theoretisch 19bit...).

Aber wenn das mit dem Anmelden so einfach wäre, würdest du wahrscheinlich nicht fragen...

Martok hat folgendes geschrieben:

Aber wenn das mit dem Anmelden so einfach wäre, würdest du wahrscheinlich nicht fragen...

Richtig. Und deswegen verstehe ich nicht, warum hier alle um das eigentliche Problem versuchen herumzureden.
Ich habe weder gefragt, ob Hashing hier das richtige ist, noch ob ich andere Schlüssel definieren kann oder was auch immer, sondern nur, wieviele Hash-Stellen ich für meine Anforderungen brauche.

Da ich die Frage aber nun schon zum fünften Mal formuliere ohne dass jemand drauf eingeht (bis auf das Geburtstagsparadoxon, was eventuell in die richige Richtung geht), wird das hier wohl nichts mehr. Ist OK, ich frag in einem Matheforum ...

Ist ja gut... nur meistens kann man sowas einfacher lösen

Aber bitte: ein guter Hash ist gleichverteilt im kompletten Schlüsselraum. Damit ist eigentlich alles gesagt.

Nach dem was BenBE gesagt hat, müssten also (10^6)^2 = 10^12 Werte rein, das sind 5 Byte. Lieber noch etwas mehr. Du bräuchtest also einen Hash der mindestens so viele Werte hat. Das suchen bleibt jetzt dir überlassen, ich denke mal für 64bit sollte sich was finden lassen.

Von MD5 nur ein paar Stellen nehmen müsste wegen der Gleichverteilung auch funktionieren, allerdings wird der Schlüsselraum sinnlos um Größenordnungen kleiner. Was das für Auswirkungen hat, weiß ich nicht.

Deine Kritik an der 'Unfähigkeit', deine Frage zu beantworten, empfinde ich aber als unhöflich. BenBE hat Dir einen Link/Wink gegeben sowie eine Alternative aufgezeigt, auf die Du dann auch gerne eingegangen bist. Dann zu behaupten, wir würden um das Problem herumreden ist schon grenzwertig. Die Lösung ist bereits genannt, haber für Dich sei sie hier nochmals skizziert:
Sei X der Zahlenraum der Ergebnisse deiner Hashfunktion , n die Anzahl der durchzuführenden Proben (hier: 1 Mio), sowie P die gewünschte Kollisionswahrscheinlichkeit (0.001 = 1%), dann ergibt sich:

P < 1- X!/[(X-n)! * X^n]

Das lässt sich mit der Stirling-Formel doch sehr leicht ausrechnen bzw. nähern.

Wieso Du aber partout Kollisionen haben willst, weiss ich immer noch nicht. Das es auch ohne geht, haben wir Dir gezeigt. Das Verfahren wäre in 1-10 Minuten implementiert.

Danke. Mit den letzten beiden Antworten komme ich klar.