Autor Beitrag
IhopeonlyReader
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: 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 :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 114
Erhaltene Danke: 14



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
ausblenden Delphi-Quelltext
1:
2:
type
  T2dBolFeld  = array[0..255,0..255of 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.
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: Do 22.08.13 12:39 
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
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
ausblenden Delphi-Quelltext
1:
2:
type
  T2dBolFeld  = array[0..255,0..255of Boolean;


ja, wobei es nicht statisch ist!
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
T2DBoolFeld = Array of Array of Boolean;

//aber bei setlength verwende ich Byte und somit werden die Arrays nicht größer als 255*255 sein 
var x:Byte;
X := "neueBreite";
setlength( T2DBoolFeld, X );

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: 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:
ausblenden 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
  //Allokieren und belegen
  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;
  //MD5 berechnen
  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 user profile iconjfheins ist zwar richtig, aber in der Praxis dürfte der Overhead aufwendiger sein als der Gewinn.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 174
Erhaltene Danke: 43



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: Do 22.08.13 15:51 
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:
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);
ausblenden 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
ausblenden volle Höhe 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:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
uses Math;

{type
  Boolean2DArray = Array of Array of Boolean;
  THash = Array[1..4] of Byte;}

function HashIt( Booleans: Boolean2DArray ): THash;
var Bytes: Array of Byte;
    Hash: Array of Byte;
    C: Word; // (255*255 / 8) wird maximal benötigt
    X,Y : Byte;
begin
//Booleans Bitweise in Hash schreiben
setlength( Hash, Ceil( Length(Booleans)*Length(Booleans[0])/8) );
//letztes Byte initialisieren, alle anderen werden vollkommen "überschrieben"
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;

//Hashen ?!
while Length(Hash)>4 do
  begin
  setlength(Bytes, Length(Hash)-1);
  For C:=1 to High(Hash) do
    begin
      case (C mod 3of
      0:    Bytes[C-1] := Hash[C-1and Hash[C];
      1:    Bytes[C-1] := Hash[C-1or Hash[C];
      2:    Bytes[C-1] := Hash[C-1xor Hash[C];
      else  Bytes[C-1] := Hash[C-1and not Hash[C]; //trifft nie ein !
      end;
    end;

  //Hash in Bytes schreiben !
  setlength(Hash, Length(Bytes));
  For C:=0 to High(Bytes) do
    Hash[C] := Bytes[C];
  end;
For C:=0 to High(Hash) do //Wenn es nur wenige booleans sind (<25) dann sinds <3 Bytes !
   Result[C+1] := Hash[C];
//Falls "zu wenig" booleans übermittelt wurde Ergebnis-unbenutzte-Bytes-initialisieren
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 :D
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Do 22.08.13 16:07 
user profile iconIhopeonlyReader hat folgendes geschrieben Zum zitierten Posting springen:
Zu deinem Code: müsste es nicht in Zeile 24
ausblenden Quelltext
1:
for j:=low(arr[i]) to high(arr[i]) do MD5Update(Context,@arr[i,j],1); //heißen?					
Richtig, es ist schon ein Kreuz mit Pointer und fehlenden Fehlermeldung :(
user profile iconIhopeonlyReader hat folgendes geschrieben Zum zitierten Posting springen:
Problem 2: Es liegen KEINE Hashunits etc. vor !
Verstehe ich nicht. Was heißt nicht vorliegen? Darfst/willst Du keinen fremden Code benutzen? Meine verwendete MD5 liegt selbstverständlich im Quellcode vor.
IhopeonlyReader Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: 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 :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
Blup
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 174
Erhaltene Danke: 43



BeitragVerfasst: 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.