Autor |
Beitrag |
IhopeonlyReader
      
Beiträge: 600
Erhaltene Danke: 23
Delphi 7 PE
|
Verfasst: Mi 21.08.13 20:31
Guten Tag,
da Hashs vorwiegend in Datenbanken und dem Vergleich/ suchen verwendet wird, habe ich für diesen Thread hier unter Datenbanken eingeordnet, hoffe dass ich nicht falsch...
Wie die Überschrift schon sagt, möchte ich einen Hash von einem Boolean-2D-Array erstellen...
Das Array besitzt zwischen 4 und 65025 Booleans (insgesamt)
Jede Dimension ist auf 255 (durch Counter vom Typ Byte) begrenzt, das reicht auch vollkommen
wie kann ich daraus einen Hash erstellen?
Wenn ich nur 4 Booleans habe, möchte ich trotzdem einen Hash in derselben Größe wie bei 65025 Booleans...
Die Größe des Hashes sollte 16 Byte nicht übersteigen
Dabei ist es vollkommen egal, ob die Daten (Booleans) aus dem Hash regenerierbar sind oder nicht
freue mich auf eure Antworten,
mfG IhopeonlyReader
_________________ Sucht "neueres" Delphi
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
|
|
jfheins
      
Beiträge: 918
Erhaltene Danke: 158
Win 10
VS 2013, VS2015
|
Verfasst: Mi 21.08.13 21:54
Du könntest immer 8 Booleans zu einem Byte verwurschteln und dann MD5 drüberlaufen lassen. Der hat genau 16 Bytes.
|
|
Mr_Emre_D
      
Beiträge: 114
Erhaltene Danke: 14
|
Verfasst: Mi 21.08.13 22:28
Die Größe eines Hashes ist immer konstant.
MD5 besteht aus 16 Bytes - immer!
Zitat: |
Dabei ist es vollkommen egal, ob die Daten (Booleans) aus dem Hash regenerierbar sind oder nicht
|
Per Definition ist ein Hash eine Einwegsfunktion - somit sowieso nicht "regenerierbar"!
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: IhopeonlyReader
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 22.08.13 10:10
Hallo,
Nur mal kurz aus Interesse, was gemeint ist:
Zitat: | Wie die Überschrift schon sagt, möchte ich einen Hash von einem Boolean-2D-Array erstellen...
Das Array besitzt zwischen 4 und 65025 Booleans (insgesamt) |
Du hast ein 2D Feld
Delphi-Quelltext 1: 2:
| type T2dBolFeld = array[0..255,0..255] of Boolean; |
Und du möchtest einen HashWert für die Anzahl der wahren Bool-Werte und! deren Anordnung?
Anzahl der Anordnungen = (N über k). Das ist für k= n/2 ist das am größten.Hier ca. 10^19726 oder so.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:
| program LogNueberK; var i: integer; k,S:extended; begin S:= 1.0; For i := 1 to 32768 do begin k := 65536-i; S := S+ln(k)-ln(i); writeln(i:8,' e^ ',s:0:4); end; end. |
MD5 ist mit 3.4e38 dabei. Es könnte also ein paar Kollisionen geben.
Gruß Horst
|
|
IhopeonlyReader 
      
Beiträge: 600
Erhaltene Danke: 23
Delphi 7 PE
|
Verfasst: Do 22.08.13 12:39
_________________ Sucht "neueres" Delphi
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
|
|
Gammatester
      
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 22.08.13 13:44
Wahrscheinlich fasse ich die Frage falsch auf, aber wo ist da ein Problem? Jede Hashunit, die ihr Geld wert ist, hat eine inkrementelle Updatefunktion. Deshalb wäre die naheliegende Implementation etwa analog zu dem folgenden Beispiel, daß die mir bekannte MD5-Unit verwendet:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27:
| program t_ba_md5;
{$APPTYPE CONSOLE}
uses hash,md5; type T2DBoolFeld = Array of Array of Boolean; var arr: T2DBoolFeld; i,j: integer; var Context: THashContext; Digest : TMD5Digest; begin setlength(arr,40,200); for i:= low(arr) to high(arr) do begin for j:=low(arr[i]) to high(arr[i]) do arr[i,j] := random(2)=1; end; MD5Init(Context); for i:= low(arr) to high(arr) do begin for j:=low(arr[i]) to high(arr[i]) do MD5Update(Context,@arr[i],1); end; MD5Final(Context,Digest); end. | Falls es Probleme gibt mit booleans, deren Byte-Cast nicht 0 oder 1 sind, sollte man zur Sicherheit über temporäre Bytes mit 0/1 gehen; der Vorschlag von jfheins ist zwar richtig, aber in der Praxis dürfte der Overhead aufwendiger sein als der Gewinn.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 22.08.13 14:46
Hallo,
natürlich hat ein Hashwert in der Regel einen kleineren Wertebereich als die Möglichkeiten der Ausgangsmenge.
Ich hatte nur MD5 mit seinen 16 byte in den falschen Hals bekommen.
Man würde MD5 bestimmen und durch ein mod Primzahl Rechnung auf eine Listennummer umrechnen, an deren Stelle in der Liste dann die MD5 und die Stellung gespeichert ist.
Dann kann man bei Kollision anders weiter verfahren.
Mit 32500 gesetzten Booleans im 255x255 Feld können sich bei gleicher MD5 trotzdem ~10^19000 unterschiedliche Stellungen ergeben.
Damit kann man sich nur 5E5 ( 65kBit ~ 8kByte )Stellungen in 4 Gbyte merken.
Lange Rede, keinen Sinn, bei so einer großen Anzahl an Möglichkeiten bekommt man einfach Speicherprobleme.
Gruß Horst
|
|
Blup
      
Beiträge: 174
Erhaltene Danke: 43
|
Verfasst: Do 22.08.13 15:28
@Horst_H
2 ^ (16Byte * 8Bit)
Das sind etwa 3,4 * 10^38 verschiedene Stellungen die unterschieden werden könnten.
Selbst wenn er heute anfängt und bis zum Ende des Universums jede Sekunde eine neue zufällige Stellung speichert, ich glaube nicht das eine Kollision auftritt.
|
|
IhopeonlyReader 
      
Beiträge: 600
Erhaltene Danke: 23
Delphi 7 PE
|
Verfasst: Do 22.08.13 15:51
Gammatester hat folgendes geschrieben : | Wahrscheinlich fasse ich die Frage falsch auf, aber wo ist da ein Problem? Jede Hashunit, die ihr Geld wert ist, hat eine inkrementelle Updatefunktion. |
Ja,
Problem 1: Auch aus 3 Bit einen 4 Byte hash machen !
Problem 2: Es liegen KEINE Hashunits etc. vor !
Zu deinem Code: müsste es nicht in Zeile 24
for j:=low(arr[i]) to high(arr[i]) do MD5Update(Context,@arr[i],1);
Quelltext 1:
| for j:=low(arr[i]) to high(arr[i]) do MD5Update(Context,@arr[i,j],1); //heißen? |
Natürlich sollten möglichst wenig Kollisionen vorkommen!
Ich überlege ob ich alle "Datenlagen" die kleiner als 4 Byte sind, gar nicht erst zu hashen.., wenn ich das auf beiden Seiten so mache (Hash 1 und Hash 2) dann macht es ja keinen Unterschied, und diese Dateien sind dann 100 % Kollisionsfrei
Wobei diese 100% zu Diskussionen führen könnten, da ja auch aus >4 Byte Dateien derselbe Hash entstehen könnte, aber egal.. Innerhalb der <4Byte ist es 100 % kollisionsfrei !
Ihr könnt auch mehrere Möglichkeiten liefern!, für kleine Dateien Hash 1, für größere Hash 2 und für ziemlich große Hash 3..
ich dachte an sowas
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49:
| uses Math;
function HashIt( Booleans: Boolean2DArray ): THash; var Bytes: Array of Byte; Hash: Array of Byte; C: Word; X,Y : Byte; begin setlength( Hash, Ceil( Length(Booleans)*Length(Booleans[0])/8) ); Hash[ High(Hash) ] := 0; For X:=0 to High(Booleans) do For Y:=0 to High(Booleans[X]) do begin C := Y*(Length(Booleans)+1) +X; if Booleans[X,Y] then Hash[ C div 8 ] := Hash[ C div 8 ] or (1 shl (C mod 8)); end;
while Length(Hash)>4 do begin setlength(Bytes, Length(Hash)-1); For C:=1 to High(Hash) do begin case (C mod 3) of 0: Bytes[C-1] := Hash[C-1] and Hash[C]; 1: Bytes[C-1] := Hash[C-1] or Hash[C]; 2: Bytes[C-1] := Hash[C-1] xor Hash[C]; else Bytes[C-1] := Hash[C-1] and not Hash[C]; end; end;
setlength(Hash, Length(Bytes)); For C:=0 to High(Bytes) do Hash[C] := Bytes[C]; end; For C:=0 to High(Hash) do Result[C+1] := Hash[C]; For C:=High(Hash)+1 to 3 do Result[C+1] := 0;
end; |
aber ich denke, dieser "aus dem kopf geschriebene" hash, ist nicht das Optimale...
Könntet ihr ihn bitte mal unter die Lupe nehmen und ggf. testen?
_________________ Sucht "neueres" Delphi
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
Zuletzt bearbeitet von IhopeonlyReader am Do 22.08.13 17:01, insgesamt 3-mal bearbeitet
|
|
Gammatester
      
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 22.08.13 16:07
|
|
IhopeonlyReader 
      
Beiträge: 600
Erhaltene Danke: 23
Delphi 7 PE
|
Verfasst: Do 22.08.13 16:10
dein Satz
Zitat: | Jede Hashunit, die ihr Geld wert ist, hat eine inkrementelle Updatefunktion
|
Hatte ich so verstanden, dass deine verwendete MD5 Unit etwas kostet und mir somit nicht zur Verfügung steht
_________________ Sucht "neueres" Delphi
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
|
|
Blup
      
Beiträge: 174
Erhaltene Danke: 43
|
Verfasst: Do 22.08.13 16:26
Vergiss es deinen eigenen Hash-Algo zu erfinden. Mathematiker haben lange dafür studiert, damit diese Dinger gut und schnell sind.
Wichtig ist nur, wenn die Prüfsumme aus mehr Bytes besteht, ist die Wahrscheinlichkeit einer Kollision geringer.
Ich würde zu MD5 raten, aber CRC32 würde in diesem Fall mit ca. 4 Milliarden Möglichkeiten wahrscheinlich auch reichen.
Fertige frei verfügbare Bibliotheken gibts für jeden Algo und vermutlich auch für jede gängige Programmiersprache.
|
|
|